Fügen Sie Schlüssel ein und beobachten Sie, wo die Balance kippt und welche Rotation (Einfach- oder Doppelrotation) den Baum wieder ausgleicht. Mit dem Schalter «Ohne Balancierung» sehen Sie dieselbe Folge im gewöhnlichen binären Suchbaum.
Das Prinzip
Jeder Knoten hat eine Balance b = Höhe rechter Teilbaum − Höhe linker Teilbaum. Zulässig sind −1, 0 und +1. Nach jedem Einfügen wird auf dem Weg zurück zur Wurzel geprüft. Wo b = ±2 erreicht ist, stellt eine Rotation die Bedingung wieder her.
| Fall | Erkennung | Massnahme |
|---|---|---|
| Links-Links | b = −2, linkes Kind b ≤ 0 | Rechtsrotation |
| Rechts-Rechts | b = +2, rechtes Kind b ≥ 0 | Linksrotation |
| Links-Rechts | b = −2, linkes Kind b > 0 | Linksrotation am Kind, dann Rechtsrotation |
| Rechts-Links | b = +2, rechtes Kind b < 0 | Rechtsrotation am Kind, dann Linksrotation |
Die ersten beiden Fälle sind Einfachrotationen, die letzten beiden Doppelrotationen. Im Baum «Ohne Balancierung» wächst bei aufsteigenden Schlüsseln eine Liste, mit AVL bleibt die Höhe logarithmisch.
Python-Code
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
self.height = 1
def height(n):
return n.height if n else 0
def balance(n):
return height(n.right) - height(n.left) # b = h(rechts) − h(links)
def update(n):
n.height = 1 + max(height(n.left), height(n.right))
def rotate_right(y):
x = y.left
y.left, x.right = x.right, y
update(y)
update(x)
return x # x ist die neue Wurzel dieses Teilbaums
def rotate_left(x):
y = x.right
x.right, y.left = y.left, x
update(x)
update(y)
return y
def rebalance(n):
update(n)
b = balance(n)
if b < -1: # links zu hoch
if balance(n.left) > 0: # Links-Rechts-Knick: erst zur Linie drehen
n.left = rotate_left(n.left)
return rotate_right(n)
if b > 1: # rechts zu hoch
if balance(n.right) < 0: # Rechts-Links-Knick
n.right = rotate_right(n.right)
return rotate_left(n)
return n
def insert(n, key):
if n is None:
return Node(key)
if key < n.key:
n.left = insert(n.left, key)
elif key > n.key:
n.right = insert(n.right, key)
return rebalance(n) # auf dem Rückweg: jeden Knoten des Pfads prüfen
Verwendung: root = None, dann root = insert(root, 10) für jeden Schlüssel. Wer die Höhe prüfen möchte, liest root.height.