58 lines
2.5 KiB
Python
58 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.bin_tree import BinaryTree
|
||
|
||
# ── Entarteter BST: sortierte Eingabe ────────────────────────────────────────
|
||
|
||
ctx = AlgoContext()
|
||
tree_sorted = BinaryTree(ctx)
|
||
for v in range(1, 9):
|
||
tree_sorted.insert(v)
|
||
|
||
tree_sorted.graph_traversal() # → entarteter Baum sichtbar: eine gerade Kette
|
||
|
||
print("Höhe (sortierte Eingabe):", tree_sorted.root.height()) # 8
|
||
|
||
ctx.comparisons = 0
|
||
tree_sorted.search(8)
|
||
print("Vergleiche search(8) im entarteten Baum:", ctx.comparisons) # 16
|
||
# Jeder Knoten (1 bis 8) erfordert zwei Vergleiche: value < node? (nein)
|
||
# und value > node? (ja, bis der gesuchte Knoten gefunden ist).
|
||
# Das entspricht einer linearen Suche: O(n).
|
||
|
||
# ── Referenz: ausgewogene Einfügereihenfolge ─────────────────────────────────
|
||
|
||
ctx2 = AlgoContext()
|
||
tree_balanced = BinaryTree(ctx2)
|
||
for v in [4, 2, 6, 1, 3, 5, 7, 8]: # Mitte zuerst → ausgewogener Baum
|
||
tree_balanced.insert(v)
|
||
|
||
print("\nHöhe (ausgewogene Eingabe):", tree_balanced.root.height()) # 4
|
||
|
||
ctx2.comparisons = 0
|
||
tree_balanced.search(8)
|
||
print("Vergleiche search(8) im ausgewogenen Baum:", ctx2.comparisons) # 8
|
||
|
||
# ── Antworten zu den Analysefragen ───────────────────────────────────────────
|
||
|
||
# Wie viele Vergleiche benötigt search(8) im entarteten Baum?
|
||
# 16 – der Baum entartet zur verketteten Liste, jeder Knoten wird besucht.
|
||
|
||
# Wie viele im ausgewogenen Baum mit 8 Knoten?
|
||
# 8 – die Höhe beträgt 4, jede Ebene kostet 2 Vergleiche (< und >).
|
||
|
||
# Welche Eingabereihenfolge erzeugt immer einen ausgewogenen BST?
|
||
# Median-First: stets den Median der aktuellen Teilfolge zuerst einfügen.
|
||
# Das setzt voraus, dass alle Elemente bereits bekannt sind – bei dynamischen
|
||
# Einfügungen (ein Element nach dem anderen, ohne Vorwissen) ist das nicht
|
||
# möglich. Deshalb reicht es nicht, nur die Einfügereihenfolge zu steuern.
|
||
|
||
# Was muss eine Datenstruktur garantieren?
|
||
# Sie muss die Baumhöhe nach jeder Einfüge- oder Löschoperation automatisch
|
||
# auf O(log n) begrenzen – unabhängig von der Eingabereihenfolge.
|
||
# AVL-Bäume erreichen das, indem sie nach jeder Operation den Balance-Faktor
|
||
# prüfen und bei Bedarf Rotationen durchführen.
|