51 lines
2.2 KiB
Python
51 lines
2.2 KiB
Python
import sys
|
||
import os
|
||
_root = os.path.abspath(os.path.join(os.path.dirname(__file__), '..', '..'))
|
||
_l06 = os.path.join(_root, 'vorlesung', 'L06_b_baeume')
|
||
if _l06 not in sys.path: sys.path.insert(0, _l06)
|
||
if _root not in sys.path: sys.path.insert(0, _root)
|
||
|
||
from b_tree import BTree
|
||
from utils.algo_context import AlgoContext
|
||
from utils.algo_array import Array
|
||
|
||
ctx = AlgoContext()
|
||
values = Array.from_file('data/seq3.txt', ctx)
|
||
|
||
tree3 = BTree(3, ctx)
|
||
tree5 = BTree(5, ctx)
|
||
for cell in values:
|
||
tree3.insert(cell)
|
||
tree5.insert(cell)
|
||
|
||
# ── Welche Höhe ergibt sich für Ordnung 3 bzw. 5? ───────────────────────────
|
||
print("Höhe Ordnung 3:", tree3.height())
|
||
print("Höhe Ordnung 5:", tree5.height())
|
||
|
||
# Ordnung 3: Knoten fassen 2–5 Schlüssel → weniger Schlüssel pro Knoten,
|
||
# mehr Ebenen nötig. seq3.txt hat 10 000 Werte → Höhe ca. 5–7.
|
||
# Ordnung 5: Knoten fassen 4–9 Schlüssel → geringere Höhe, ca. 4–5.
|
||
|
||
# ── Traversierung und Sortierungsprüfung ─────────────────────────────────────
|
||
results3 = []
|
||
tree3.traversal(lambda v: results3.append(int(str(v))))
|
||
print("Sortiert (Ordnung 3):", results3 == sorted(results3))
|
||
|
||
results5 = []
|
||
tree5.traversal(lambda v: results5.append(int(str(v))))
|
||
print("Sortiert (Ordnung 5):", results5 == sorted(results5))
|
||
|
||
# In-Order-Traversal eines B-Baums liefert immer eine sortierte Folge:
|
||
# Die B-Baum-Eigenschaft (linker Teilbaum < Schlüssel < rechter Teilbaum)
|
||
# gilt rekursiv für jeden Knoten.
|
||
|
||
# ── Knoten mit Wert 0 suchen ─────────────────────────────────────────────────
|
||
node3 = tree3.search(0)
|
||
node5 = tree5.search(0)
|
||
print("Knoten mit 0 (Ordnung 3):", str(node3) if node3 else "nicht gefunden")
|
||
print("Knoten mit 0 (Ordnung 5):", str(node5) if node5 else "nicht gefunden")
|
||
|
||
# search() gibt den Knoten zurück, der den gesuchten Schlüssel enthält.
|
||
# __str__ gibt alle Schlüssel des Knotens aus, z.B.: ( -2 0 3 )
|
||
# Größere Ordnung → mehr Schlüssel pro Knoten → der Knoten mit 0
|
||
# enthält bei m=5 tendenziell mehr Nachbarn als bei m=3. |