Topology · binary_tree
Binary Tree
A complete binary tree of depth floor(log2(n)). Edges go parent to child.
Evaluation
Linear · T ∘ E–iterations (left / right recursion)
Doubling · T ∘ T–iterations (double recursion)
iteration 1new pairs per iteration
Point at a node (or tab to the drawing and use the arrow keys) to see every node it reaches, wave by wave. Those pairs are its rows of the closure.
Nodes · edges15 · 14
Closure |TC|34
Closure / edges2.4×
A small instance from the generator the benchmark runs with n from 100 upwards.
Definition
Symbol
B_h
Edges
\{(i, 2i) \mid i \in 1..2^{h-1}\} \cup \{(i, 2i+1) \mid i \in 1..2^{h-1}\}
Generator
engine.data_generator.DataGenerator.generate_binary_tree_graphgenerate_db.py
def generate_binary_tree_graph(self, n: int) -> Generator[tuple[int, int], None, None]:
"""Generate a binary tree graph with n nodes."""
h = math.floor(math.log2(n))
logging.info(f'Generating binary tree graph for n={n} and h={h}')
parent_count = 2 ** (h - 1) - 1
for i in range(1, parent_count + 1):
yield (i, 2 * i)
yield (i, 2 * i + 1)