Frage:
Ein AVL-Baum ist ein Suchbaum, in dem für jeden Knoten u die Höhendierenz der
beiden Teilbäume an u höchstens 1 ist, siehe Vorlesungsfolien.
Zeigen Sie, dass die Knoten in einem AVL-Baum immer so gefärbt werden können, dass
das Ergebnis ein Rot-Schwarz-Baum ist. Zeigen Sie dazu die folgende Aussage induktiv:
Jeder Teilbaum T der Höhe h ≥ 0 eines AVL-Baums kann wie folgt rot-schwarz gefärbt
werden:
1. Höhe h gerade, Schwarzhöhe (h/2 )+ 1, Wurzel schwarz,
2. Höhe h ungerade, Schwarzhöhe h+1/2, Wurzel rot.
Zuletzt wird die Wurzel des gesamten AVL-Baums schwarz gefärbt; dies ist jedoch nicht
mehr Teil der Induktion.