62 lines
2.1 KiB
Python
62 lines
2.1 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)
|
||
|
||
import graphviz
|
||
from datetime import datetime
|
||
from b_tree import BTree
|
||
from utils.algo_context import AlgoContext
|
||
from utils.algo_array import Array
|
||
|
||
|
||
class BTreeVis(BTree):
|
||
"""BTree-Erweiterung mit Graphviz-Ausgabe als Unterklasse."""
|
||
|
||
def graph_traversal(self):
|
||
def _node_rep(node):
|
||
label = " | ".join(str(node.value[i]) for i in range(node.n))
|
||
dot.node(str(id(node)), label=label, shape="record", fontname="Arial")
|
||
|
||
def _rec(node):
|
||
_node_rep(node)
|
||
if not node.leaf:
|
||
for i in range(node.n + 1):
|
||
child = node.children[i]
|
||
if child is not None:
|
||
dot.edge(str(id(node)), str(id(child)))
|
||
_rec(child)
|
||
|
||
dot = graphviz.Digraph(
|
||
name=f"BTree_m{self.m}",
|
||
engine="dot",
|
||
node_attr={"fontname": "Arial"},
|
||
format="pdf",
|
||
)
|
||
_rec(self.root)
|
||
ts = datetime.now().strftime("%Y%m%d_%H%M%S")
|
||
dot.render(f"BTree_m{self.m}_{ts}.gv")
|
||
|
||
|
||
ctx = AlgoContext()
|
||
values = Array.from_file('data/seq1.txt', ctx)
|
||
tree = BTreeVis(3, ctx)
|
||
for cell in values:
|
||
tree.insert(cell)
|
||
|
||
# graph_traversal() erzeugt eine DOT-Datei und rendert sie als PDF.
|
||
tree.graph_traversal()
|
||
|
||
# ── Antworten zu den Beobachtungsfragen ──────────────────────────────────────
|
||
|
||
# Wie viele Schlüssel hat die Wurzel?
|
||
# Ablesbar direkt aus tree.root.n.
|
||
print("Schlüssel in der Wurzel:", tree.root.n)
|
||
|
||
# Liegen alle Blätter auf derselben Tiefe?
|
||
# Ja – das ist eine B-Baum-Invariante: alle Blätter haben immer
|
||
# dieselbe Tiefe, da Splits ausschließlich aufwärts propagieren.
|
||
# In der PDF sind alle Blattknoten auf der untersten Ebene.
|
||
print("Höhe des Baums:", tree.height()) |