Kompletne drzewo binarne kontra pełne drzewo binarne
Drzewo binarne to drzewo, w którym każdy węzeł ma jedno lub dwoje dzieci. W drzewie binarnym węzeł nie może mieć więcej niż dwoje dzieci. W drzewie binarnym dzieci są nazywane „lewymi” i „prawymi” dziećmi. Węzły potomne zawierają odniesienie do swojego rodzica. Kompletne drzewo binarne to drzewo binarne, w którym każdy poziom drzewa binarnego jest całkowicie wypełniony, z wyjątkiem ostatniego poziomu. Na poziomie niewypełnionym węzły są dołączane od skrajnej lewej pozycji. Pełne drzewo binarne to drzewo, w którym każdy węzeł w drzewie ma dwoje dzieci z wyjątkiem liści.
Co to jest pełne drzewo binarne?
Pełne drzewo binarne to drzewo binarne, w którym każdy węzeł w drzewie ma dokładnie zero lub dwoje dzieci. Innymi słowy, każdy węzeł w drzewie oprócz liści ma dokładnie dwoje dzieci. Rysunek 1 poniżej przedstawia pełne drzewo binarne. W pełnym drzewie binarnym liczba węzłów (n), liczba listew (l) i liczba węzłów wewnętrznych (i) jest powiązana w specjalny sposób, tak że znając któryś z nich, możesz określić pozostałe dwa wartości w następujący sposób:
1. Jeśli pełne drzewo binarne ma i wewnętrzne węzły:
– Liczba liści l=i+1
– Całkowita liczba węzłów n=2i+1
2. Jeśli pełne drzewo binarne ma n węzłów:
– Liczba węzłów wewnętrznych i=(n-1)/2
– Liczba liści l=(n+1)/2
3. Jeśli pełne drzewo binarne ma l liści:
– Całkowita liczba węzłów n=2l-1
– Liczba węzłów wewnętrznych i=l-1
Co to jest kompletne drzewo binarne?
Jak pokazano na rysunku 2, kompletne drzewo binarne jest drzewem binarnym, w którym każdy poziom drzewa jest całkowicie wypełniony, z wyjątkiem ostatniego poziomu. Również na ostatnim poziomie węzły należy dołączać zaczynając od skrajnej lewej pozycji. Kompletne drzewo binarne o wysokości h spełnia następujące warunki:
– Od węzła głównego poziom powyżej ostatniego poziomu reprezentuje pełne drzewo binarne o wysokości h-1
– Jeden lub więcej węzłów na ostatnim poziomie może mieć 0 lub 1 dziecko
– Jeśli a, b są dwoma węzłami na poziomie powyżej ostatniego poziomu, to a ma więcej dzieci niż b wtedy i tylko wtedy, gdy a znajduje się na lewo od b
Jaka jest różnica między kompletnym drzewem binarnym a pełnym drzewem binarnym?
Pełne drzewa binarne i pełne drzewa binarne mają wyraźną różnicę. Podczas gdy pełne drzewo binarne jest drzewem binarnym, w którym każdy węzeł ma zero lub dwoje dzieci, pełne drzewo binarne jest drzewem binarnym, w którym każdy poziom drzewa binarnego jest całkowicie wypełniony, z wyjątkiem ostatniego poziomu. Niektóre specjalne struktury danych, takie jak sterty, muszą być kompletnymi drzewami binarnymi, podczas gdy nie muszą być pełnymi drzewami binarnymi. W pełnym drzewie binarnym, jeśli znasz liczbę wszystkich węzłów, liczbę listew lub liczbę węzłów wewnętrznych, możesz bardzo łatwo znaleźć pozostałe dwa. Ale kompletne drzewo binarne nie ma specjalnej własności odnoszącej się do tych trzech atrybutów.
