0 Daumen
309 Aufrufe

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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community