Schlimmster Fall in Max-Heapify - Wie bekommt man 2n / 3?

In CLRS, dritte Ausgabe, auf Seite 155, ist angegeben, dass in MAX-HEAPIFY,

Die Teilbäume der Kinder haben jeweils eine Größe von höchstens 2n / 3 - der schlimmste Fall tritt auf, wenn die unterste Ebene des Baums genau halb voll ist.

Ich verstehe, warum es am schlimmsten ist, wenn die unterste Ebene des Baumes genau halb voll ist. Und es wird auch in dieser Frage der schlimmste Fall in MAX-HEAPIFY beantwortet: "Der schlimmste Fall tritt auf, wenn die unterste Ebene des Baumes genau halb voll ist."

Meine Frage ist, wie man 2n / 3 bekommt?

Warum, wenn die unterste Ebene halb voll ist, beträgt die Größe des untergeordneten Baums bis zu 2n / 3?

Wie berechnet man das?

Vielen Dank

In einem Baum, in dem jeder Knoten genau entweder 0 oder 2 Kinder hat, ist die Anzahl der Knoten mit 0 Kindern eins mehr als die Anzahl der Knoten mit 2 Kindern. {Erläuterung: Die Anzahl der Knoten in der Höhe h beträgt 2 ^ h Summationsformel einer geometrischen Reihe ist gleich (Summe der Knoten von Höhe 0 bis h-1) + 1; und alle Knoten von Höhe 0 bis h-1 sind die Knoten mit genau 2 Kindern}

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

Sei k die Anzahl der Knoten in R. Die Anzahl der Knoten in L ist k + (k + 1) = 2k + 1. Die Gesamtzahl der Knoten ist n = 1 + (2k + 1) + k = 3k + 2 (Wurzel plus L plus R). Das Verhältnis ist (2k + 1) / (3k + 2), das oben durch 2/3 begrenzt ist. Keine Konstante von weniger als 2/3 funktioniert, da die Grenze, wenn k gegen unendlich geht, 2/3 beträgt.

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.

Sobald dies klar ist, ist die Grenze von 2N / 3 leicht zu bekommen.

Nehmen wir an, dass die Gesamtzahl der Knoten im Baum N ist.

Anzahl der Knoten im Baum = 1 + (Anzahl der Knoten im linken Teilbaum) + (Anzahl der Knoten im rechten Teilbaum)

Für unseren Fall, in dem der Baum die letzte Ebene halb voll hat, nehmen wir an, dass der rechte Teilbaum die Höhe h hat, und der linke Teilbaum die Höhe (h + 1):

Anzahl der Knoten im linken Teilbaum = 1 + 2 + 4 + 8 .... 2 ^ (h + 1) = 2 ^ (h + 2) -1 ..... (i)

Anzahl der Knoten im rechten Teilbaum = 1 + 2 + 4 + 8 .... 2 ^ (h) = 2 ^ (h + 1) -1 ..... (ii)

Einstecken in:

Anzahl der Knoten im Baum = 1 + (Anzahl der Knoten im linken Teilbaum) + (Anzahl der Knoten im rechten Teilbaum)

=> 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

Wenn wir diesen Wert in Gleichung (i) einfügen, erhalten wir:

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

Daher beträgt die Obergrenze für die maximale Anzahl von Knoten in einem Teilbaum für einen Baum mit N Knoten 2N / 3.

Für einen vollständigen binären Höhenbaum beträgt die hAnzahl der Knoten f(h) = 2^h - 1. Im obigen Fall haben wir einen fast vollständigen Binärbaum mit einer vollen vollen Hälfte. Wir können dies als Sammlung von visualisieren root + left complete tree + right complete tree. Wenn die Höhe des ursprünglichen Baums ist h, ist die Höhe von links h - 1und rechts h - 2. So wird Gleichung

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

Wir wollen oben lösen für f(h-1)ausgedrückt als in Bezug aufn

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

Mit oben in (1) haben wir

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

Daher O (2n / 3)

Zur Antwort von swen hinzufügen. Wie (2k + 1) / (3k + 2) zu 2/3 tendiert, wenn k zur Unendlichkeit tendiert,

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)

Wenden Sie das Limit an und Sie erhalten 2/3

Anzahl der Knoten bei -

• Stufe 0 dh Wurzel ist 2 ^ 0
• Stufe 1 ist 2 ^ 1
• Stufe 2 ist 2 ^ 2
• ...
• Stufe n ist 2 ^ n

Summation aller Knoten von Level 0 bis Level n,

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

Aus der Summationsregel für geometrische Reihen wissen wir das

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

Wenn wir x = 2 einsetzen, erhalten wir

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

Da 2 ^ (n + 1) die Gesamtzahl der Knoten auf Ebene n + 1 ist, können wir sagen, dass die Anzahl der Knoten mit 0 Kindern eins mehr ist als die Anzahl der Knoten mit 2 Kindern.

Berechnen wir nun die Anzahl der Knoten im linken Teilbaum, im rechten Baum und in der Summe.

• Angenommen, die Anzahl der Nicht-Blattknoten im linken Teilbaum von root = k.

• Nach der obigen Überlegung ist die Anzahl der Blattknoten im linken Teilbaum oder der Wurzel = k + 1. Die Anzahl der Nicht-Blattknoten im rechten Teilbaum der Wurzel = k, da der Baum genau halb voll sein soll.

• Gesamtzahl der Knoten im linken Teilbaum von root = k + k + 1 = 2k +

• Gesamtzahl der Knoten im Baum, n = (2k + 1) + k + 1 = 3k + 2.
• Verhältnis der Knoten im linken Teilbaum und der Gesamtknoten = (2k + 1) / (3k + 2), das oben durch 2/3 begrenzt ist.

Das ist der Grund zu sagen, dass die Teilbäume der Kinder jeweils höchstens 2n / 3 groß sind.