Kompletný binárny strom vs úplný binárny strom
Binárny strom je strom, v ktorom má každý uzol jedno alebo dve deti. V binárnom strome nemôže mať uzol viac ako dve deti. V binárnom strome sú deti pomenované ako „ľavé“a „pravé“deti. Podradené uzly obsahujú odkaz na svojho rodiča. Kompletný binárny strom je binárny strom, v ktorom je úplne naplnená každá úroveň binárneho stromu okrem poslednej úrovne. Na nevyplnenej úrovni sú uzly pripojené od polohy úplne zľava. Plný binárny strom je strom, v ktorom má každý uzol na strome dve deti okrem listov stromu.
Čo je to Plný binárny strom?
Plný binárny strom je binárny strom, v ktorom má každý uzol v strome presne nulu alebo dve deti. Inými slovami, každý uzol v strome okrem listov má presne dve deti. Obrázok 1 nižšie zobrazuje úplný binárny strom. V úplnom binárnom strome je počet uzlov (n), počet laves (l) a počet vnútorných uzlov (i) spojený osobitným 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 = 2 * i + 1
2. Ak má plný binárny strom n uzlov:
- Počet vnútorných uzlov i = (n-1) / 2
- Počet listov l = (n + 1) / 2
3. Ak má plný binárny strom 1 listy:
- Celkový počet uzlov n = 2 * l-1
- Počet vnútorných uzlov i = l-1
Čo je to Kompletný binárny strom?
Ako je znázornené na obrázku 2, kompletný binárny strom je binárny strom, v ktorom je úplne naplnená každá úroveň stromu okrem poslednej úrovne. Na poslednej úrovni by tiež mali byť pripojené uzly začínajúce od polohy úplne zľava. Celý binárny strom výšky h spĺňa tieto podmienky:
- Z 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 detí ako b práve vtedy, ak je a 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é binárne stromy, zatiaľ čo nemusia byť úplnými binárnymi stromami. Ak poznáte v úplnom binárnom strome počet celkových uzlov alebo počet laves alebo počet vnútorných uzlov, ďalšie dva nájdete veľmi ľahko. Ale kompletný binárny strom nemá špeciálnu vlastnosť súvisiacu s týmito tromi atribútmi.
