Complete Binary Tree vs Full Binary Tree
Mti wa binary ni mti ambapo kila nodi ina mtoto mmoja au wawili. Katika mti wa binary, nodi haiwezi kuwa na watoto zaidi ya wawili. Katika mti wa binary, watoto huitwa watoto "wa kushoto" na "kulia". Nodi za watoto zina kumbukumbu kwa mzazi wao. Mti kamili wa binary ni mti wa binary ambao kila ngazi ya mti wa binary hujazwa kabisa isipokuwa kiwango cha mwisho. Katika ngazi isiyojazwa, nodi zimeunganishwa kuanzia nafasi ya kushoto-zaidi. Mti kamili wa binary ni mti ambao kila nodi kwenye mti ina watoto wawili isipokuwa majani ya mti.
Je, Full Binary Tree ni nini?
Mti kamili wa binary ni mti wa jozi ambapo kila nodi kwenye mti ina sifuri au watoto wawili haswa. Kwa maneno mengine, kila nodi kwenye mti isipokuwa majani ina watoto wawili haswa. Kielelezo cha 1 hapa chini kinaonyesha mti kamili wa binary. Katika mti kamili wa binary, idadi ya nodi (n), idadi ya laves (l) na idadi ya nodi za ndani (i) inahusiana kwa njia maalum ili ukijua yoyote kati yao unaweza kuamua zingine mbili. maadili kama ifuatavyo:
1. Ikiwa mti kamili wa binary una nodi za ndani:
– Idadi ya majani l=i+1
– Jumla ya idadi ya nodi n=2i+1
2. Ikiwa mti kamili wa binary una nodi n:
– Idadi ya nodi za ndani i=(n-1)/2
– Idadi ya majani l=(n+1)/2
3. Ikiwa mti kamili wa binary una l majani:
– Jumla ya Idadi ya nodi n=2l-1
– Idadi ya nodi za ndani i=l-1
Complete Binary Tree ni nini?
Kama inavyoonyeshwa katika mchoro wa 2, mti kamili wa binary ni mti wa binary ambapo kila ngazi ya mti imejaa kabisa isipokuwa kiwango cha mwisho. Pia, katika ngazi ya mwisho, nodi zinapaswa kuunganishwa kuanzia nafasi ya kushoto zaidi. Mti kamili wa jozi wa urefu h unakidhi masharti yafuatayo:
– Kutoka kwa nodi ya mizizi, kiwango cha juu cha kiwango cha mwisho kinawakilisha mti kamili wa jozi wa urefu h-1
– Nodi moja au zaidi katika ngazi ya mwisho inaweza kuwa na mtoto 0 au 1
– Ikiwa a, b ni nodi mbili katika kiwango kilicho juu ya kiwango cha mwisho, basi a ana watoto zaidi ya b ikiwa na ikiwa tu a iko kushoto kwa b
Kuna tofauti gani kati ya Complete Binary Tree na Full Binary Tree?
Kamilisha miti ya jozi na miti ya binary kamili ina tofauti dhahiri. Wakati mti kamili wa binary ni mti wa binary ambao kila nodi ina sifuri au watoto wawili, mti kamili wa binary ni mti wa binary ambao kila ngazi ya mti wa binary hujazwa kabisa isipokuwa ngazi ya mwisho. Baadhi ya miundo maalum ya data kama lundo inahitaji kuwa miti ya aina mbili ilhali haihitaji kuwa miti ya binary kamili. Katika mti kamili wa binary, ikiwa unajua idadi ya nodi za jumla au idadi ya laves au idadi ya nodi za ndani, unaweza kupata nyingine mbili kwa urahisi sana. Lakini mti kamili wa binary hauna sifa maalum inayohusiana na hizi sifa tatu.
