Kompletní binární strom vs plný binární strom
Binární strom je strom, kde má každý uzel jedno nebo dvě děti. V binárním stromu nemůže mít uzel více než dvě děti. V binárním stromu jsou děti pojmenovány jako „levé“a „pravé“děti. Podřízené uzly obsahují odkaz na jejich rodiče. Kompletní binární strom je binární strom, ve kterém je každá úroveň binárního stromu zcela vyplněna, kromě poslední úrovně. Na nevyplněné úrovni jsou uzly připojeny počínaje od pozice nejvíce vlevo. Plný binární strom je strom, ve kterém má každý uzel na stromě dvě děti kromě listů stromu.
Co je to Full Binary Tree?
Plný binární strom je binární strom, ve kterém má každý uzel ve stromu přesně nula nebo dvě děti. Jinými slovy, každý uzel ve stromu kromě listů má přesně dvě děti. Obrázek 1 níže zobrazuje plný binární strom. V úplném binárním stromu je počet uzlů (n), počet laves (l) a počet vnitřních uzlů (i) spojen zvláštním způsobem, takže pokud znáte některý z nich, můžete určit další dva hodnoty takto:
1. Pokud má plný binární strom i vnitřní uzly:
- Počet listů l = i + 1
- Celkový počet uzlů n = 2 * i + 1
2. Pokud má plný binární strom n uzlů:
- Počet vnitřních uzlů i = (n-1) / 2
- Počet listů l = (n + 1) / 2
3. Pokud má plný binární strom l listy:
- Celkový počet uzlů n = 2 * l-1
- Počet vnitřních uzlů i = l-1
Co je to Complete Binary Tree?
Jak je znázorněno na obrázku 2, kompletní binární strom je binární strom, ve kterém je každá úroveň stromu zcela vyplněna kromě poslední úrovně. Na poslední úrovni by také měly být připojeny uzly počínaje od pozice nejvíce vlevo. Kompletní binární strom výšky h splňuje následující podmínky:
- Z kořenového uzlu představuje úroveň nad poslední úrovní úplný binární strom výšky h-1
- Jeden nebo více uzlů v poslední úrovni může mít 0 nebo 1 dítě
- Pokud a, b jsou dva uzly v úrovni nad poslední úrovní, pak a má více dětí než b tehdy a jen tehdy, pokud a je umístěno nalevo od b
Jaký je rozdíl mezi Complete Binary Tree a Full Binary Tree?
Úplné binární stromy a plné binární stromy mají jasný rozdíl. Zatímco plný binární strom je binární strom, ve kterém má každý uzel nula nebo dvě děti, úplný binární strom je binární strom, ve kterém je každá úroveň binárního stromu zcela vyplněna kromě poslední úrovně. Některé speciální datové struktury, jako jsou hromady, musí být úplnými binárními stromy, zatímco nemusí být úplnými binárními stromy. Pokud v úplném binárním stromu znáte počet celkových uzlů nebo počet laves nebo počet vnitřních uzlů, můžete snadno najít další dva. Ale kompletní binární strom nemá speciální vlastnost vztahující se k těmto třem atributům.
