Najgorszy przypadek w Max-Heapify - jak uzyskać 2n / 3?

W CLRS, wydanie trzecie, na stronie 155 podano, że w MAX-HEAPIFY,

Każde poddrzewo dziecięce ma rozmiar co najwyżej 2n / 3 - najgorszy przypadek ma miejsce, gdy dolny poziom drzewa jest dokładnie w połowie zapełniony.

Rozumiem, dlaczego jest najgorzej, gdy dolny poziom drzewa jest wypełniony dokładnie do połowy. W tym pytaniu odpowiedź na najgorszy przypadek w MAX-HEAPIFY: „najgorszy przypadek występuje, gdy dolny poziom drzewa jest dokładnie w połowie zapełniony”

Moje pytanie brzmi jak zdobyć 2n / 3?

Dlaczego jeśli dolny poziom jest w połowie zapełniony, to rozmiar drzewa podrzędnego wynosi do 2n / 3?

Jak to obliczyć?

Dzięki

W drzewie, w którym każdy węzeł ma dokładnie 0 lub 2 dzieci, liczba węzłów z 0 dziećmi jest o jeden większa niż liczba węzłów z 2 potomkami. {Objaśnienie: liczba węzłów na wysokości h wynosi 2 ^ h, co wzór sumowania szeregu geometrycznego równa się (suma węzłów od wysokości 0 do h-1) + 1; a wszystkie węzły od wysokości 0 do h-1 to węzły z dokładnie 2 dziećmi}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

Niech k będzie liczbą węzłów w R.Liczba węzłów w L to k + (k + 1) = 2k + 1. Całkowita liczba węzłów to n = 1 + (2k + 1) + k = 3k + 2 (pierwiastek plus L plus R). Stosunek wynosi (2k + 1) / (3k + 2), który jest ograniczony powyżej 2/3. Nie ma stałej mniejszej niż 2/3, ponieważ granica przy k do nieskończoności wynosi 2/3.

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

Gdy to już jest jasne, granica 2N / 3 jest łatwa do zdobycia.

Załóżmy, że całkowita liczba węzłów w drzewie to N.

Liczba węzłów w drzewie = 1 + (liczba węzłów w lewym poddrzewie) + (liczba węzłów w prawym poddrzewie)

W naszym przypadku, gdy ostatni poziom drzewa jest w połowie zapełniony, iF zakładamy, że prawe poddrzewo ma wysokość h, a lewe poddrzewo, jeśli ma wysokość (h + 1):

Liczba węzłów w lewym poddrzewie = 1 + 2 + 4 + 8 .... 2 ^ (h + 1) = 2 ^ (h + 2) -1 ..... (i)

Liczba węzłów w prawym poddrzewie = 1 + 2 + 4 + 8 .... 2 ^ (h) = 2 ^ (h + 1) -1 ..... (ii)

Zatem podłączenie do:

Liczba węzłów w drzewie = 1 + (liczba węzłów w lewym poddrzewie) + (liczba węzłów w prawym poddrzewie)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

Podstawiając tę ​​wartość do równania (i), otrzymujemy:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

Stąd górna granica maksymalnej liczby węzłów w poddrzewie dla drzewa z N węzłami wynosi 2N / 3.

W przypadku pełnego binarnego drzewa wysokości hliczba węzłów wynosi f(h) = 2^h - 1. W powyższym przypadku mamy prawie pełne drzewo binarne z pełną dolną połową. Możemy to sobie wyobrazić jako zbiór plików root + left complete tree + right complete tree. Jeśli wysokość oryginalnego drzewa to h, to wysokość lewej h - 1i prawej jest h - 2. Więc staje się równanie

n = 1 + f(h-1) + f(h-2) (1)

Chcemy rozwiązać powyższe rozwiązanie f(h-1)wyrażone jako w zakresien

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

Używając powyższego w (1) mamy

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

Stąd O (2n / 3)

Aby dodać do szwedzkiej odpowiedzi. Jak (2k + 1) / (3k + 2) zmierza do 2/3, kiedy k dąży do nieskończoności,

Lim_ (k -> inf) (2k + 1) / (3k + 2) = Lim_ (k -> inf) k (2 + 1 / k) / k (3 + 2 / k) = Lim_ (k -> inf) ) (2 + 1 / k) / (3 + 2 / k)

zastosuj limit, a otrzymasz 2/3

Liczba węzłów w -

• poziom 0 tj. root to 2 ^ 0
• poziom 1 to 2 ^ 1
• poziom 2 to 2 ^ 2
• ...
• poziom n wynosi 2 ^ n

Suma wszystkich węzłów od poziomu 0 do poziomu n,

• S = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ n

Wiemy to z reguły sumowania szeregów geometrycznych

• x ^ 0 + x ^ 1 + x ^ 2 + ... + x ^ (n) = (x ^ (n + 1) - 1) / (x-1)

Zastępując x = 2, otrzymujemy

• S = 2 ^ (n + 1) - 1. tj. 2 ^ (n + 1) = S + 1

Ponieważ 2 ^ (n + 1) to całkowita liczba węzłów na poziomie n + 1, możemy powiedzieć, że liczba węzłów z 0 dziećmi jest o jeden większa niż liczba węzłów z 2 dziećmi.

Teraz obliczmy liczbę węzłów w lewym poddrzewie, prawym drzewie i łącznie.

• Załóżmy, że liczba węzłów niebędących liśćmi w lewym poddrzewie root = k.

• Zgodnie z powyższym rozumowaniem, liczba węzłów liści w lewym poddrzewie lub korzeniu = k + 1. Liczba węzłów nielistnych w prawym poddrzewie korzenia = k, ponieważ mówi się, że drzewo jest dokładnie w połowie zapełnione.

• Całkowita liczba węzłów w lewym poddrzewie korzenia = k + k + 1 = 2k +

• Całkowita liczba węzłów w drzewie, n = (2k + 1) + k + 1 = 3k + 2.
• Stosunek węzłów w lewym poddrzewie do łącznej liczby węzłów = (2k + 1) / (3k + 2), który jest ograniczony powyżej 2/3.

To jest powód, dla którego mówi się, że każde poddrzewo dzieci ma rozmiar co najwyżej 2n / 3.