86 lines
3.2 KiB
Python
86 lines
3.2 KiB
Python
import sys
|
||
import os
|
||
sys.path.insert(0, os.path.join(os.path.dirname(os.path.abspath(__file__)), '..', '..'))
|
||
|
||
import random
|
||
from utils.algo_context import AlgoContext
|
||
from vorlesung.L05_binaere_baeume.bin_tree import BinaryTree
|
||
from vorlesung.L05_binaere_baeume.avl_tree import AVLTree
|
||
|
||
# ── Theoretische Herleitung ───────────────────────────────────────────────────
|
||
|
||
# AVL-Baum / ausgeglichener BST
|
||
# Bei jedem Schritt der Suche wird genau ein Teilbaum mit (ungefähr) halber
|
||
# Größe weiterverfolgt:
|
||
#
|
||
# T(n) = T(n/2) + O(1)
|
||
#
|
||
# Master-Theorem: a=1, b=2, f(n)=O(1)
|
||
# log_b(a) = log_2(1) = 0 → f(n) = O(n^0) = O(n^log_b(a))
|
||
# → Fall 2: T(n) = O(log n)
|
||
|
||
# BST – Worst Case (sortierte Eingabe, entarteter Baum)
|
||
# Der Baum ist eine verkettete Liste; jeder Schritt reduziert das Problem um 1:
|
||
#
|
||
# T(n) = T(n-1) + O(1)
|
||
#
|
||
# Kein Master-Theorem (b > 1 gefordert). Direkte Auflösung durch Entfalten:
|
||
# T(n) = T(n-2) + 2·c = … = T(0) + n·c → O(n)
|
||
|
||
# BST – zufällige Eingabe (Expected Case)
|
||
# Bei zufälliger Einfügereihenfolge teilt die Wurzel den Schlüsselraum im
|
||
# Erwartungswert in zwei ungefähr gleich große Hälften – analog zum
|
||
# durchschnittlichen Fall bei Quicksort. Daraus folgt eine erwartete Höhe
|
||
# von O(log n), empirisch ca. 2,5 · log₂(n). Ein formaler Beweis erfordert
|
||
# eine Wahrscheinlichkeitsanalyse über alle n! Permutationen.
|
||
|
||
# ── Empirische Messung ───────────────────────────────────────────────────────
|
||
|
||
SIZES = [10, 100, 500]
|
||
|
||
print(f"{'n':>5} {'BST zufällig':>14} {'BST sortiert':>14} {'AVL sortiert':>14}")
|
||
print("-" * 55)
|
||
|
||
for n in SIZES:
|
||
# BST, zufällige Eingabe
|
||
ctx = AlgoContext()
|
||
tree = BinaryTree(ctx)
|
||
values = random.sample(range(n * 10), n)
|
||
for v in values:
|
||
tree.insert(v)
|
||
ctx.comparisons = 0
|
||
tree.search(values[-1])
|
||
cmp_random = ctx.comparisons
|
||
|
||
# BST, sortierte Eingabe
|
||
ctx = AlgoContext()
|
||
tree = BinaryTree(ctx)
|
||
for v in range(1, n + 1):
|
||
tree.insert(v)
|
||
ctx.comparisons = 0
|
||
tree.search(n)
|
||
cmp_sorted = ctx.comparisons
|
||
|
||
# AVL-Baum, sortierte Eingabe
|
||
ctx = AlgoContext()
|
||
tree = AVLTree(ctx)
|
||
for v in range(1, n + 1):
|
||
tree.insert(v)
|
||
ctx.comparisons = 0
|
||
tree.search(n)
|
||
cmp_avl = ctx.comparisons
|
||
|
||
print(f"{n:>5} {cmp_random:>14} {cmp_sorted:>14} {cmp_avl:>14}")
|
||
|
||
# ── Abschlussfrage ────────────────────────────────────────────────────────────
|
||
#
|
||
# Stimmen die Messwerte mit den theoretischen Komplexitätsklassen überein?
|
||
#
|
||
# BST sortiert wächst linear mit n (2·n Vergleiche für das letzte Element),
|
||
# was die hergeleitete O(n)-Komplexität bestätigt.
|
||
#
|
||
# BST zufällig und AVL sortiert wachsen logarithmisch: für n=500 liegen die
|
||
# Vergleiche bei ca. 20 bzw. 18 – weit unter dem linearen Worst Case.
|
||
# Das bestätigt O(log n) für beide, wobei der AVL-Baum die Schranke
|
||
# garantiert und der zufällige BST sie nur im Erwartungswert einhält.
|