Úplný binární strom vs. Úplný binární strom
Binární strom je strom, kde každý uzel má jednoho nebo dva potomky. V binárním stromu nemůže mít uzel více než dva potomky. 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ě. V nevyplněné úrovni jsou uzly připojeny od pozice zcela vlevo. Úplný binární strom je strom, ve kterém má každý uzel ve stromu dva potomky kromě listů stromu.
Co je úplný binární strom?
Plný binární strom je binární strom, ve kterém má každý uzel ve stromu přesně nulu nebo dva potomky. Jinými slovy, každý uzel ve stromu kromě listů má právě dvě potomky. Obrázek 1 níže zobrazuje úplný binární strom. V úplném binárním stromu jsou počet uzlů (n), počet lávek (l) a počet vnitřních uzlů (i) spojeny 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 vnitřní uzly i:
– Počet listů l=i+1
– Celkový počet uzlů n=2i+1
2. Pokud má úplný binární strom n uzlů:
– Počet interních uzlů i=(n-1)/2
– Počet listů l=(n+1)/2
3. Pokud má celý binární strom l listů:
– Celkový počet uzlů n=2l-1
– Počet interních uzlů i=l-1
Co je úplný binární strom?
Jak je znázorněno na obrázku 2, úplný binární strom je binární strom, ve kterém je každá úroveň stromu zcela vyplněna kromě poslední úrovně. V poslední úrovni by také měly být uzly připojeny od pozice zcela 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 potomka
– Jsou-li a, b dva uzly v úrovni nad poslední úrovní, pak a má více potomků než b právě tehdy, když a leží 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 nula nebo dva potomky, ú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 haldy, musí být úplnými binárními stromy, zatímco nemusí být úplnými binárními stromy. V plném binárním stromu, pokud znáte počet celkových uzlů nebo počet lave nebo počet interních uzlů, můžete velmi snadno najít další dva. Ale úplný binární strom nemá speciální vlastnost vztahující se k těmto třem atributům.
