über AVL Tree Insertion Operation

Question

In der Standard-Prozess der AVL-Tree-Insertion, nachdem wir einen neuen Knoten einfügen, werden wir Anpassung von unten nach oben tun, und während des Prozesses ist es möglich, eine Sub-Baum-Höhe um eins (wegen der Insertion und Rotation Operation), während der Unterbaum (nach der Höhe um eins zu erhöhen), immer noch die gleiche Höhe von links/rechts Kind? Wenn dem so ist, wird ein Beispiel geschätzt, und wenn nicht, wird es großartig sein, wenn irgendjemand es erklären könnte. Vielen Dank. :)

Hier ist ein Verweis auf AVL-Baum (https://en.wikipedia.org/wiki/AVL_tree)

Grüßen, Lin

Answer 1

Nach dem Einfügen ist es nicht möglich, dass das linke und rechte Kind des Unterbaums bei einer Höhenänderung gleich bleibt.

Betrachten wir ein einfaches Beispiel mit nur < 3 Knoten in einem Unterbaum. Die Möglichkeiten des Ausgleichsfaktors sind,

• +1 - und das ist der Startknoten in Unterbaum mit 1 Linksem Kind und kein rechtes Kind
• -1 - der Wurzelknoten in Teilbaum mit 1 rechtsem Kind und kein linken Kind
• 0 - Root-Knoten in Teilbaum hat 1 Knoten in Right und Left.

Für SubTree Ausgewogene Faktor +1,

• , wenn wir in den rechten einsetzen, sind wir
• in Ordnung, wenn wir in den linken legen wir die Balance Änderungen 2. So müssen um den Baum auszugleichen, in welchem ​​Fall die Höhe des Teilbaums geändert wird.

Für SubTree Ausgewogene Faktor -1,

• , wenn wir in den linken legen sind wir ok
• , wenn wir in den rechten einfügen, den Ausgleichsfaktor Änderungen -2. Also müssen wir den Baum ausbalancieren, in welchem ​​Fall die Höhe des Teilbaums geändert wird.

Für SubTree Ausgewogene Faktor 0,

• , wenn wir in den linken einsetzen, sind wir ok. Die Höhe wird geändert, aber der untergeordnete Knoten wird ebenfalls geändert.
• Wenn wir in das Recht einfügen, sind wir in Ordnung. Die Höhe wird geändert, aber der untergeordnete Knoten wird ebenfalls geändert.

So ist es nicht möglich, die Höhe geändert zu haben und immer noch die gleiche rechte und linke Kindhöhe zu haben.

Answer 2

Von Wikipedia Binary Tree page:

Eine ausgewogene Binärbaum hat die minimal mögliche maximale Höhe (aka Tiefe) für die Blattknoten, da für jede gegebene Anzahl von Blattknoten die Blattknoten in der größtmöglichen Höhe angeordnet sind.

Eine gemeinsame ausgeglichene Baumstruktur eine binäre Baumstruktur, in der die linken und rechten Teilbäume von jedem Knoten in der Höhe unterscheiden sich um nicht mehr als 1

Zum Beispiel:

Dies ist ein ausgewogener Baum.

Und wenn wir 1 Einsatz ist es Höhe erhöht sich um 1. Es ist jedoch ein ausgeglichener Baum wieder. Da links und rechts Teilbäume in der Höhe unterscheiden sie nicht mehr als 1.

BTW, ist AVL-Baum ein Balancierter Baum. Es ist also nicht möglich, nach dem Einsetzen das Gleichgewicht zu verlieren. Denn nach jeder Insertion balanciert der Baum sich selbst aus, indem er notwendige Rotationen vornimmt.

Ich denke, Sie verwenden den Begriff ausgeglichen falsch. Sie betrachten ausgeglichen als keinen Höhenunterschied, aber es ist höchstens 1 Höhenunterschied in der Definition.

Ihre Frage:

In dem Standardverfahren der AVL-Baum Insertion, ist es möglich, ein Teilbaumhöhenzunahme durch eine (aufgrund der Insertion und Rotationsoperation), während des Unterbaumes (nach Höhe um eins erhöhen), haben immer noch die gleiche Höhe von links/rechts Kind?

Wenn wir würden einen Baum haben, die die gleiche Höhe von linken und rechten Zweige hat, und wenn wir einen Knoten in einem Blattknoten auf dem linken Zweig einsetzen würde, würde Höhe erhöhen, weil Höhe des Baumes maximum(height(left_branch, right_branch)) ist. Denn nach dieser Operation ist height(left_branch) gleich height(right_branch)+1. Sie können also nicht gleich sein.

Kurz gesagt, Ihre Voraussetzung ist height(left_branch) == height(right_branch)

Ihr Betrieb ist increasing height of left_branch by 1

So height(left_branch) == height(right_branch) Bedingung nicht mehr wahr sein kann.