W mojej klasie Java uczymy się o złożoności różnych typów kolekcji.
Wkrótce będziemy rozmawiać o drzewach binarnych, o których czytałem. Książka stwierdza, że minimalna wysokość drzewa binarnego wynosi , ale nie oferuje dalszych wyjaśnień.
Czy ktoś może wyjaśnić, dlaczego?
data-structures
binary-trees
discrete-mathematics
trees
CodyBugstein
źródło
źródło
Odpowiedzi:
Drzewo binarne ma 1 lub 2 elementy podrzędne w węzłach innych niż liście i 0 węzłów w węzłach liści. Niech będzien węzły w drzewie i musimy je ułożyć w taki sposób, aby nadal tworzyły prawidłowe drzewo binarne.
Nie udowadniając, twierdzę, że aby zmaksymalizować wysokość, dane węzły powinny być ustawione liniowo, tj. Każdy węzeł inny niż liść powinien mieć tylko jedno dziecko:
Wzór na obliczenie relacji wysokości w kategoriach liczby węzłów jest prosty. Gdybyh jest zatem wysokością drzewa h = n - 1 .
Teraz, jeśli spróbujemy zbudować binarne drzewon węzły o minimalnej wysokości (zawsze redukowalne do pełnego drzewa binarnego), musimy przejść jak najwięcej węzłów na wyższych poziomach, zanim przejdziemy do następnego poziomu. Drzewo przyjmuje zatem postać następującego drzewa:
Zacznijmy od konkretnego przypadku,n =2)m- 1 .
Wiemy to,
Łatwo też udowodnić, że poziomja może mieć co najwyżej 2)ja węzły w nim.
Używając tego wyniku w powyższej sumie, znajdujemy to dla każdego poziomuja , od 0 do m istnieje odpowiedni termin 2)i - 1 w rozszerzeniu 2)m- 1 . Oznacza to, że kompletne drzewo binarne2)m- 1 węzły są całkowicie wypełnione i mają wysokość, h (2)m- 1 ) = m - 1 , gdzie h ( n ) = wysokość pełnego drzewa binarnego z n węzły
Korzystając z tego wyniku,h (2)m) = m , ponieważ drzewo z 2)m- 1 węzły są całkowicie wypełnione, a tym samym drzewo (2)m- 1 ) + 1 =2)m węzły muszą pomieścić dodatkowy węzeł na następnym poziomie m , zwiększając wysokość o 1 od m - 1 do m .
Do tej pory udowodniliśmy,
A zatem,∀ n ∈ Z ,2)m≤ n <2)m + 1
Ale biorąc dziennik (podstawa 2) po obu stronach,
A zatem,∀ n , n ∈ [2)m,2)m + 1)
I możemy uogólnić ten wynik∀ n ∈ Z za pomocą indukcji.
PS: Książka określająca wysokość pełnego drzewa binarnego jakolog2)( n + 1 ) - 1 nie jest ważne dla wszystkich n ponieważ log2)( n ) dałoby wartości niecałkowite dla większości liczb całkowitych n (tj. dla wszystkich oprócz doskonałych drzew podwójnych), ale wysokość drzewa jest całkowicie integralna.
źródło
Zakładam, że przezn , masz na myśli całkowitą liczbę węzłów w drzewie binarnym. Wysokość (lub głębokość) drzewa binarnego to długość ścieżki od węzła głównego (węzła bez rodziców) do najgłębszego węzła liścia. Aby ta wysokość była minimalna, drzewo powinno być w pełni nasycone (z wyjątkiem ostatniej warstwy), tj. Jeśli konkretna warstwa ma węzły z dziećmi, wówczas wszystkie węzły w warstwie nadrzędnej muszą mieć dwoje dzieci.
Więc w pełni nasycone drzewo binarne4 poziomy będą miały 1 + 1 ⋅ 2 + 1 ⋅ 2 ⋅ 2 + 1 ⋅ 2 ⋅ 2 ⋅ 2 węzły maksymalnie i będą miały głębokość 3) . Zatem jeśli mamy głębokość drzewa binarnego, możemy bardzo łatwo znaleźć maksymalną liczbę węzłów (co występuje, gdy drzewo jest w pełni nasycone). Jeśli przypomnisz sobie ze swoich klas algebry, jest to tylko seria geometryczna i dlatego można ją przedstawić w następujący sposób:
Zmieńmy więc kolejność:
źródło
Aby utrzymać minimalną wysokość, łatwo zauważyć, że musimy wypełnić wszystkie poziomy, z wyjątkiem ewentualnie ostatniego. Dlaczego? w przeciwnym razie moglibyśmy po prostu przesunąć węzły ostatniego poziomu do pustych miejsc na wyższych poziomach.
Teraz wyobraź sobie, że mam nieokreśloną liczbę ziaren i daję ci jedną fasolę na raz i proszę, abyś zbudował drzewo binarne o możliwie najmniejszej wysokości. Mogę skończyć się fasolą, zanim albo całkowicie zapełnisz ostatni poziom, albo przynajmniej będziesz mieć jedną fasolę na ostatnim poziomie. Powiedzmy, że w tym momencie masz wysokość drzewa h .
W obu przypadkach h się nie zmienia. Co oznacza, że masz kompletne binarne drzewo wysokości h z moim ograniczeniem. Ale założyłem fikcyjne fasole na ostatnim poziomie (jeśli nie możesz wypełnić ostatniego poziomu). Więc tak naprawdę
źródło