60 lines
2.5 KiB
Python
60 lines
2.5 KiB
Python
import sys
|
|
import os
|
|
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), '..', '..'))
|
|
|
|
from utils.algo_context import AlgoContext
|
|
from vorlesung.L05_binaere_baeume.avl_tree import AVLTree
|
|
|
|
ctx = AlgoContext()
|
|
tree = AVLTree(ctx)
|
|
for v in [10, 5, 15, 3, 7, 12, 20, 1, 4, 6, 8]:
|
|
tree.insert(v)
|
|
|
|
print("Ausgangszustand:")
|
|
tree.in_order_traversal(lambda n: print(n.value, end=" "))
|
|
print()
|
|
tree.graph_traversal()
|
|
|
|
# ── Fall 1: Blattknoten löschen (1 ist Blatt) ────────────────────────────────
|
|
tree.delete(1)
|
|
print("\nNach Löschen von 1 (Blatt):")
|
|
tree.in_order_traversal(lambda n: print(n.value, end=" "))
|
|
print()
|
|
tree.graph_traversal()
|
|
|
|
# ── Fall 2: Knoten mit einem Kind löschen (3 hat jetzt nur noch Kind 4) ──────
|
|
tree.delete(3)
|
|
print("\nNach Löschen von 3 (ein Kind):")
|
|
tree.in_order_traversal(lambda n: print(n.value, end=" "))
|
|
print()
|
|
tree.graph_traversal()
|
|
|
|
# ── Fall 3: Knoten mit zwei Kindern löschen (10 hat linkes Kind 5, rechtes 15)
|
|
tree.delete(10)
|
|
print("\nNach Löschen von 10 (zwei Kinder):")
|
|
tree.in_order_traversal(lambda n: print(n.value, end=" "))
|
|
print()
|
|
tree.graph_traversal()
|
|
# Inorder-Nachfolger von 10 ist 12 (kleinstes Element im rechten Teilbaum).
|
|
# 12 übernimmt den Platz von 10, anschließend wird rebalanciert.
|
|
|
|
# ── Antworten zu den Verständnisfragen ───────────────────────────────────────
|
|
|
|
# Warum muss node.parent = parent nach dem Löschen neu gesetzt werden?
|
|
#
|
|
# BinaryTree kennt keine parent-Zeiger — delete() gibt lediglich
|
|
# (nachfolgender_knoten, elternknoten) als plain-Python-Tupel zurück.
|
|
# AVLTree pflegt parent-Zeiger, weil balance() sie benötigt, um den Pfad
|
|
# von einem Knoten aufwärts zur Wurzel zu traversieren.
|
|
# Ohne die Aktualisierung würde balance() an einem veralteten parent-Zeiger
|
|
# hängen und die Rebalancierung unvollständig oder fehlerhaft ausführen.
|
|
|
|
# Warum beginnt die Rebalancierung mit balance(parent) statt balance(node)?
|
|
#
|
|
# Das Löschen verändert die Höhe des Teilbaums, in dem der Knoten stand.
|
|
# Diese Höhenänderung kann den Balance-Faktor des Elternknotens (und aller
|
|
# Vorfahren bis zur Wurzel) aus dem Gleichgewicht bringen.
|
|
# Der gelöschte (oder ersetzte) Knoten selbst ist entweder weg oder ein Blatt
|
|
# — er ist kein sinnvoller Startpunkt für die Aufwärts-Traversal.
|
|
# balance(parent) startet genau dort, wo die Höhenänderung zuerst spürbar ist.
|