/ / Dlaczego ostatni poziom "pełnego drzewa binarnego" lub "kupki binarnej" może być częściowo pusty? Czy istnieje ku temu dobry powód? - algorytm, struktury danych, drzewo binarne, sterty, sterty binarne

Dlaczego ostatni poziom "pełnego drzewa binarnego" lub "kupki binarnej" może być częściowo pusty? Czy istnieje ku temu dobry powód? - algorytm, struktury danych, drzewo binarne, sterty, sterty binarne

Definicja kompletnego drzewa binarnego to "Akompletne drzewo binarne jest drzewem binarnym, w którym każdy poziom, z wyjątkiem być może ostatnim, jest całkowicie wypełniony, a wszystkie węzły są tak daleko w lewo, jak to możliwe. "Chciałem wiedzieć, dlaczego ostatni poziom może być częściowo wypełniony. w niektórych sytuacjach / przypadkach?

Próbowałem szukać odpowiedzi na to pytanie w wielu miejscach, jednak nie byłem w stanie znaleźć satysfakcjonującej odpowiedzi, czy ktoś może mi pomóc, odpowiadając na to.

Odpowiedzi:

2 dla odpowiedzi № 1

Inne podejście do tego pytania niż inne: Jeśli wszystkie poziomy będą wymagały całkowitego wypełnienia, możesz mieć tylko drzewa (2^n)-1 elementy dla niektórych n. To znaczy. 1, 3, 7, 15, ... elementy. Pozwalając, aby ostatni poziom został częściowo wypełniony, możesz mieć drzewa binarne z dowolną liczbą elementów.


1 dla odpowiedzi nr 2

Jest to po prostu definicja kompletnego drzewa binarnego, niekoniecznie pomagającego lub przeszkadzającego w niczym, po prostu tak jest.

Jeśli jesteś zainteresowany tematem, sprawdźzrównoważone drzewa binarne. Nie ma sensu, aby tylko najniższe poziomy nie były całkowicie wypełnione, aby zapewnić, że drzewo jest zrównoważone i nie ma 10 węzłów głębokich po lewej stronie i 1 węzeł po prawej stronie.

Posiadanie wszystkich poziomów drzewa jest całkowiciewypełniona pomoc gwarantuje szybki czas wyszukiwania. Jeśli wszystkie poziomy są całkowicie wypełnione, wiesz, że głębokość drzewa jest równa na wszystkich możliwych ścieżkach, więc zapewnia ci dobre górne ograniczenie prędkości wyszukiwania. W takich przypadkach można obliczyć głębokość wszystkich możliwych ścieżek węzłów liści według D = floor(lg(N)), gdzie N jest liczbą węzłów.

Teraz wyobraź sobie, że nie musisz mieć w ogóle wypełnionych poziomów, możesz mieć coś takiego jak monstrum, w którym niektóre elementy będą pobierane znacznie szybciej niż inne.

wprowadź opis obrazu tutaj