Das finden der minimalen und maximalen Höhe in einem AVL-Baum, da eine Anzahl von Knoten?

Die Lösung unten ist geeignet für arbeiten, die Dinge von hand und gewinnt eine intuition, finden Sie die genauen Formeln an der Unterseite dieser Antwort-für größere Bäume (54+ Knoten).

Sowie die minimale Höhe einfach: füllen Sie jede Ebene im Baum mit den Knoten, bis Sie laufen aus. Diese Höhe ist das minimum.

Finden das maximum, das gleiche zu tun wie für das minimum, aber dann wieder einen Schritt zurück gehen (entfernen des letzten Platzierten Knoten) und sehen, wenn Sie hinzufügen, dass die Knoten an der gegenüberliegenden sub-Baum (von wo er gerade war) verletzt die AVL-Baum-Eigenschaft. Wenn Sie es tut, Ihre maximale Höhe ist einfach eine min-height. Ansonsten ist diese neue Höhe ein (die sollte min Höhe+1) ist Ihre maximale Höhe.

Wenn Sie brauchen eine übersicht, welche Eigenschaften ein AVL-Baum, oder einfach nur eine Allgemeine Erklärung von einem AVL-Baum, Wikipedia ist ein großartiger Ort zu starten.

Beispiel:

Nehmen wir die 7-Knoten-Beispiel Fall. Sie füllen Sie alle Ebenen und finden Sie einen vollständig ausgefüllten Baum der Höhe 3. (1 bei level 1, 2 auf Ebene 2, 4 auf Ebene 3. 1+2+4=7 Knoten.) Das bedeutet, dass 3 Ihre minimale.

Nun die max. Entfernen letzten Knoten und legen Sie es auf der linken Teilbaum, anstatt das Recht. Der Rechte Teilbaum noch hat die Höhe 3, aber der linke Teilbaum nun hat die Höhe 4. Allerdings sind diese Werte unterscheiden sich um weniger als 2, so ist es immer noch ein AVL-Baum. Deshalb ist Ihre maximale Höhe ist 4. (Das ist min+1)

Alle drei Beispiele erarbeitet unten (beachten Sie, dass die Nummern entsprechen der Reihenfolge der Platzierung, NICHT Wert):

Formeln¹:

Die Technik, die oben gezeigt wird, nicht zu halten, wenn Sie einen Baum mit einer sehr großen Anzahl von Knoten. In diesem Fall kann man die folgenden Formeln zum berechnen der genauen min/max.

Gegeben n Knoten²:

Minimum: ceil(log₂(n+1))

Maximum: Boden(1.44*log₂(n+2)-.328)

Wenn du neugierig bist, das erste mal max-min - >1 ist, wenn n=54.

¹Dank Jamie S, dass diese Fehler bei größeren Knoten zählt, um meine Aufmerksamkeit.

²Diese Formeln sind von der Wikipedia AVL-Seite, mit Konstanten angeschlossen. Die ursprüngliche Quelle ist Sortieren und suchen von Donald E. Knuth (2. Auflage).

Vermuten lässt die Anzahl der Knoten ist n

Versucht herauszufinden, die mindestens die Höhe eines AVL-Baums die gleiche wäre wie der Versuch, um den Baum komplett d.h. füllen Sie möglichst alle Knoten auf jeder Ebene, und dann bewegen Sie auf die nächste Ebene.

Also auf jeder Ebene die Anzahl der geeigneten Knoten erhöht durch 2^(h-1) wobei h die Höhe des Baumes.

Also bei h=1 Knoten(1) = 2^(1-1) = 1 Knoten

für h=2, Knoten(2) = Knoten(1)+2^(2-1) = 3 Knoten

für h=3, Knoten(3) = Knoten(2)+2^(3-1) = 7 Knoten

also nur das kleinste h, für welche Knoten(h) ist größer als die angegebene Anzahl der Knoten n.

Nun für das problem der maximalen Höhe eines AVL-Baums:-

können davon ausgehen, dass die AVL-Baum der Höhe h, F(h) die Anzahl der Knoten im AVL-Baum,

für seine Höhe maximal können davon ausgehen, dass der linke Teilbaum FL und rechten Teilbaum FR eine Differenz in Höhe von 1(wie es erfüllt die AVL-Eigenschaft).

Nun vorausgesetzt, FL ist ein Baum mit Höhe h-1 und FR ein Baum mit Höhe h-2.

nun die Anzahl der Knoten in

F(h)=F(h-1)+F(h-2)+1 (Eq 1)

Hinzufügen von 1 auf beiden Seiten :

F(h)+1=(F(h-1)+1)+ (F(h-2)+1) (Eq 2)

Damit reduzieren wir die maximale Höhe problem auf eine Fibonacci sequence. Und diese Bäume F(h) aufgerufen werden Fibonacci-Bäume.

Also F(1)=1 und F(2)=2

so, in Reihenfolge zu erhalten, die maximale Höhe finden Sie einfach den index, der die Zahl in der fibonacci-Folge, die kleiner oder gleich n.

So anwenden (Eq-1)

F(3)= F(2) + F(1)+ 1=4, also, wenn n zwischen 2 und 4 Baum haben Höhe 3.

F(4)= F(3)+ F(2)+ 1 = 7, wenn n zwischen 4 und 7 Baum Höhe 4.

und so weiter.