Dlaczego minimalna wysokość drzewa binarnego

10

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ń.log2)(n+1)-1

Czy ktoś może wyjaśnić, dlaczego?

CodyBugstein
źródło
Wyjaśniam to tutaj stackoverflow.com/a/13093274/550393
2cupsOfTech 10.04.2014

Odpowiedzi:

11

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:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

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 drzewo nwę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:

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Zacznijmy od konkretnego przypadku, n=2)m-1.

Wiemy to,

2)0+2)1+2)2)+...+2)m-1=2)m-1

Łatwo też udowodnić, że poziom ja 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 poziomu ja, od 0 do mistnieje odpowiedni termin 2)ja-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(2m)=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,

h(2)m)=m,
h(2)m+1)=m+1
jak również,
h(2)m+1-1)=m

A zatem, nZ,2)mn<2)m+1

mh(n)<m+1

Ale biorąc dziennik (podstawa 2) po obu stronach,

mlog2)(n)<m+1
m=log2)(n)

A zatem, n,n[2)m,2)m+1)

h(n)=m=log2)(n)

I możemy uogólnić ten wynik nZ za pomocą indukcji.

PS: Książka określająca wysokość pełnego drzewa binarnego jako log2)(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.

Anurag Kalia
źródło
19

Zakładam, że przez n, 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 binarne 4 poziomy będą miały 1+12)+12)2)+12)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:

węzły=1+2)+2)2)+2)3)+...+2)głębokość=k=0głębokość2)k=1-2)głębokość+11-2).

Zmieńmy więc kolejność:

węzły=2)głębokość+1-1,
następnie rozwiąż problem z głębokością:
węzły+1=2)głębokość+1log2)(węzły+1)=log2)(2)głębokość+1)=głębokość+1log2)(węzły+1)-1=głębokość.
i jest twoja formuła. Teraz pamiętaj, że daje to wartości całkowite tylko wtedy, gdy każde drzewo jest całkowicie wypełnione („idealne” drzewo binarne), więc jeśli otrzymasz wartość inną niż całkowita, pamiętaj o zaokrągleniu w górę.
MikeDan
źródło
4

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ę

2)0+2)1+2)2)+2)3)++2)h=2)h+1-1n.
Więc minimum
h=lg(n+1)-1.
Ale zastosuj pułap, ponieważ dodajemy wyimaginowane ziarna, a nie usuwamy je.
użytkownik1234
źródło