Wie ist Wikipedias Beispiel einer unausgeglichenen AVL-Baum wirklich unausgeglichen?

Question

Das oben gezeigte Bild ist von „Wikipedias Eintrag auf AVL-Bäume“ die Wikipedia zeigt unausgewogen . Wie ist dieser Baum nicht bereits ausgeglichen? Hier ist ein Zitat aus dem Artikel:

  

Der Ausgleichsfaktor eines Knotens ist die Höhe seines rechten Unterbaumes minus die Höhe seines linken Teilbaumes und ein Knoten mit Gleichgewichtsfaktor 1, 0 oder -1 wird als ausgewogen. Ein Knoten mit einem beliebigen anderen Ausgleichsfaktor unausgeglichen betrachtet und den Baum erfordert Neugewichtung. Der Ausgleichsfaktor wird entweder direkt oder an jedem Knoten berechnet von den Höhen der Teilbäume gespeichert.

Sowohl die linken und rechten Teilbäume haben eine Höhe von 4. Der rechte Teilbaum des linken Baum eine Höhe von 3 hat, die nach wie vor nur 1 kleiner als 4. Kann jemand erklären, was ich bin fehlt?

Answer 1

Um ausgeglichen, jeder Knoten im Baum muss entweder,

• haben keine Kinder, (ein "Blatt" node)
• haben zwei Kinder.

• Oder, wenn es nur ein Kind hat, muss das Kind ein Blatt sein.

  In der Tabelle, die Sie geschrieben, 9, 54 und 76 verletzt die letzte Regel.

Richtig ausgeglichen, würde der Baum wie folgt aussehen:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

UPDATE: (nach knapp 9 Jahren haben ich ein cooles Online-Diagramm für die Grafik unter draw.io )

Answer 2

Knoten 76 ist unausgewogen, zum Beispiel, weil sein rechter Teilbaum der Höhe 0 und die linken Seite ist die Höhe 3.

Answer 3

Intuitiv, es ist, weil es nicht so klein wie möglich ist. beispielsweise sollte 12 sein, die Mutter von 9 und 14 ist es, 9 keinen linken Unterbaum hat, so dass es aus dem Gleichgewicht geraten ist. Ein Baum ist eine hierarchische Datenstruktur so eine Regel wie „balanced“ oft auf jeden Knoten anwenden und nicht nur den Wurzelknoten.

Sie haben Recht der Wurzelknoten ist ausgeglichen, aber nicht alle Knoten des Baumes sind.

Answer 4

Eine andere Möglichkeit, dies zu betrachten ist, dass die Höhe h eines Knotens ist gegeben durch:

h = 1 + max( left.height, right.height )

und ein Knoten ist unausgewogen, wenn:

abs( left.height - right.height ) > 1

am Baum Blick über:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

Um festzustellen, ob Knoten 9 ausgeglichen ist oder nicht schauen wir auf der Höhe seiner Kinder:

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

lösen nun diesen Knoten zu zeigen, 9 ist unausgewogen:

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

ähnliche Berechnungen können für jeden anderen Knoten gemacht werden.