Úplný binárny strom vs. Úplný binárny strom
Binárny strom je strom, v ktorom má každý uzol jedného alebo dvoch potomkov. V binárnom strome nemôže mať uzol viac ako dve deti. V binárnom strome sú deti pomenované ako „ľavé“a „pravé“deti. Podriadené uzly obsahujú odkaz na svojho rodiča. Kompletný binárny strom je binárny strom, v ktorom je každá úroveň binárneho stromu úplne vyplnená okrem poslednej úrovne. V nevyplnenej úrovni sú uzly pripojené od polohy úplne vľavo. Úplný binárny strom je strom, v ktorom má každý uzol v strome dve deti okrem listov stromu.
Čo je úplný binárny strom?
Úplný binárny strom je binárny strom, v ktorom má každý uzol v strome presne nula alebo dve deti. Inými slovami, každý uzol na strome okrem listov má práve dve deti. Obrázok 1 nižšie zobrazuje úplný binárny strom. V úplnom binárnom strome je počet uzlov (n), počet lávok (l) a počet vnútorných uzlov (i) spojený špeciálnym spôsobom, takže ak poznáte niektorý z nich, môžete určiť ďalšie dva hodnoty takto:
1. Ak má úplný binárny strom i vnútorné uzly:
– Počet listov l=i+1
– Celkový počet uzlov n=2i+1
2. Ak má celý binárny strom n uzlov:
– Počet interných uzlov i=(n-1)/2
– Počet listov l=(n+1)/2
3. Ak má úplný binárny strom l listov:
– Celkový počet uzlov n=2l-1
– Počet interných uzlov i=l-1
Čo je úplný binárny strom?
Ako je znázornené na obrázku 2, úplný binárny strom je binárny strom, v ktorom je každá úroveň stromu úplne vyplnená okrem poslednej úrovne. V poslednej úrovni by mali byť uzly pripojené od polohy úplne vľavo. Kompletný binárny strom výšky h spĺňa nasledujúce podmienky:
– Od koreňového uzla predstavuje úroveň nad poslednou úrovňou úplný binárny strom výšky h-1
– Jeden alebo viac uzlov na poslednej úrovni môže mať 0 alebo 1 dieťa
– Ak a, b sú dva uzly v úrovni nad poslednou úrovňou, potom a má viac potomkov ako b práve vtedy, ak a je umiestnené vľavo od b
Aký je rozdiel medzi úplným binárnym stromom a úplným binárnym stromom?
Úplné binárne stromy a úplné binárne stromy majú jasný rozdiel. Zatiaľ čo úplný binárny strom je binárny strom, v ktorom má každý uzol nula alebo dve deti, úplný binárny strom je binárny strom, v ktorom je každá úroveň binárneho stromu úplne vyplnená okrem poslednej úrovne. Niektoré špeciálne dátové štruktúry, ako sú haldy, musia byť úplnými binárnymi stromami, zatiaľ čo nemusia byť úplnými binárnymi stromami. Ak v úplnom binárnom strome poznáte počet celkových uzlov alebo počet lave alebo počet vnútorných uzlov, ďalšie dva nájdete veľmi ľahko. Ale úplný binárny strom nemá špeciálnu vlastnosť týkajúcu sa týchto troch atribútov.
