Dlaczego minimalna wysokość drzewa binarnego

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ń.$\log_2(n+1) - 1$

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

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ędzie$n$ 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. Gdyby$h$ jest zatem wysokością drzewa $h = n-1$.

Teraz, jeśli spróbujemy zbudować binarne drzewo $n$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:

                              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 $i$ może mieć co najwyżej $2^i$ węzły w nim.

Używając tego wyniku w powyższej sumie, znajdujemy to dla każdego poziomu $i$, od $0$ do $m$istnieje odpowiedni termin $2^{i-1}$ w rozszerzeniu $2^m - 1$. Oznacza to, że kompletne drzewo binarne$2^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,

$$h(2^m) = m,$$ $$h(2^{m+1}) = m+1$$ jak również, $$h(2^{m+1} -1) = m$$

A zatem, $\forall n \in \mathbb{Z}, 2^m \leq n < 2^{m+1}$

$$m \leq h(n) < m+1$$

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

$$m \leq \log_2(n) < m+1$$ $$m = \lfloor \log_2(n) \rfloor$$

A zatem, $\forall n, n \in [2^m, 2^{m+1})$

$$h(n) = m = \lfloor \log_2(n) \rfloor$$

I możemy uogólnić ten wynik $\forall n \in \mathbb{Z}$ za pomocą indukcji.

PS: Książka określająca wysokość pełnego drzewa binarnego jako $\log_2(n+1)-1$ nie jest ważne dla wszystkich $n$ ponieważ $\log_2(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.

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+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$ 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:

$$\text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}.$$

Zmieńmy więc kolejność:

$$\text{nodes}=2^{\text{depth}+1}-1,$$ następnie rozwiąż problem z głębokością: $$\begin{eqnarray} \text{nodes}+1&=&2^{\text{depth}+1}\\ \log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\ \log_{2}(\text{nodes}+1)-1&=&\text{depth}. \end{eqnarray}$$ 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ę.

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}+\dots+2^{h}=2^{h+1}-1 \leq n\,.$$ Więc minimum $$h = \lg(n+1)-1\,.$$ Ale zastosuj pułap, ponieważ dodajemy wyimaginowane ziarna, a nie usuwamy je.