Rozdiel medzi úplným binárnym stromom a úplným binárnym stromom

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. Podriadené uzly obsahujú odkaz na ich rodiča. Kompletný binárny strom je binárny strom, v ktorom je úplne naplnená každá úroveň binárneho stromu s výnimkou poslednej úrovne. Na neobsadenej úrovni sú uzly pripojené počnúc krajnou ľavou pozíciou. Celý binárny strom je strom, v ktorom každý uzol stromu má dve deti okrem listov stromu.

Čo je plný binárny strom?

Celý 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 zobrazuje celý binárny strom. V úplnom binárnom strome súvisí počet uzlov (n), počet lávok (l) a počet vnútorných uzlov (i) tak, že ak poznáte niektorého z nich, môžete určiť ďalšie dva hodnoty nasledovne:

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 uzly:

- Počet vnútorných uzlov i = (n-1) / 2

- Počet listov l = (n + 1) / 2

3. Ak má plný binárny strom l listy:

- Celkový počet uzlov n = 2 * l-1

- Počet vnútorných uzlov i = l-1

Čo je kompletný 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á, s výnimkou poslednej úrovne. Na poslednej úrovni by sa mali pripájať aj uzly, ktoré sa začínajú úplne zľava. Kompletný 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 na úrovni nad poslednou úrovňou, potom má a viac detí ako b, iba 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 nulu alebo dve deti, úplný binárny strom je binárny strom, v ktorom je úplne naplnená každá úroveň binárneho stromu s výnimkou 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. V úplnom binárnom strome, ak poznáte počet úplných uzlov alebo počet láv alebo počet vnútorných uzlov, ostatné dva nájdete veľmi ľahko. Úplný binárny strom však nemá špeciálnu vlastnosť súvisiacu s tromi atribútmi.