Rozdíl mezi úplným binárním stromem a úplným binárním stromem

Kompletní binární strom vs plný binární strom

Binární strom je strom, kde každý uzel má 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 „vlevo“ 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ě. V nenaplněné úrovni jsou uzly připojeny počínaje od pozice nejvíce vlevo. Celý binární strom je strom, ve kterém má každý uzel ve stromu dvě děti kromě listů stromu.

Co je plný binární strom?

Celý binární strom je binární strom, ve kterém má každý uzel ve stromu přesně nulu 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 lávek (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 následovně:

1. Má-li plný binární strom i interní uzly:

- Počet listů l = i + 1

- Celkový počet uzlů n = 2 * i + 1

2. Pokud má plný binární strom uzly:

- Počet interní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 interních uzlů i = l-1

Co je kompletní binární strom?

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ů na poslední úrovni může mít 0 nebo 1 děti

- Jestliže a, b jsou dva uzly na úrovni nad poslední úrovní, pak a má více dětí než b, a pouze tehdy, je-li a vlevo od b

Jaký je rozdíl mezi úplným binárním stromem a úplným binárním stromem??

Ú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 nulu 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é binární stromy, zatímco nemusí být plné binární stromy. V úplném binárním stromu, pokud znáte celkový počet uzlů nebo počet lávek nebo počet vnitřních uzlů, můžete ostatní dva snadno najít. Úplný binární strom však nemá zvláštní vlastnost související s těmito třemi atributy.