Binary Search Tree Dynamics lab report

1. Title and aim

Empirical Analysis of Binary Search Trees: Tree Height, Search Path Depth, and Degeneracy from Random to Pathological Insertion Sequences. Determine the tree height scaling factor α and examine search path depth across balanced and degenerate binary search trees, verifying the logarithmic bound h = Θ(log₂ n) and analyzing AVL rotation mechanics.

2. Abstract

Seven benchmark trials were generated across key dataset sizes n = 64 to n = 4096 keys (logarithmic entropy x = log₂(n) from 6.0 to 12.0 bits, tree height h from 7 to 13 levels). An ordinary least-squares regression of tree height h against logarithmic entropy log₂(n) yielded an empirical height scaling factor of 1.0000 levels/bit, demonstrating exact agreement with the theoretical complete binary tree bound (difference = 0.0000%). The empirical telemetry proves that balanced binary search trees strictly constrain search path depth to optimal Θ(log₂ n) scaling, outperforming degenerate unaugmented trees by a factor of over 315× at n = 4096 keys (where degenerate height explodes to h = 4096 levels), and validating self-balancing rotation algorithms (AVL and Red-Black trees) as essential computational defenses against catastrophic worst-case degradation.

3. Apparatus and fixed settings

• Virtual Binary Search Tree Generator: Deterministic memory allocator instantiating hierarchical 64-bit tree nodes equipped with 8-byte payload, left child pointer, right child pointer, and balance factor fields.
• Key Sequence Stream Synthesizer: Configurable input generator producing pseudo-random uniform permutations, monotonically increasing sorted sequences, and pathological zig-zag insertion patterns.
• Tree Height & Depth Gauge: Recursive structural profiler computing maximum root-to-leaf path depth (tree height h), internal path length I(n), and average search comparison depth.
• AVL Rotation & Balancing Unit: Microarchitectural transformation engine executing Left-Left (LL), Right-Right (RR), Left-Right (LR), and Right-Left (RL) single and double tree rotations in O(1) time.
• Degeneracy Ratio Comparator: Computational monitor evaluating the structural distortion ratio ρ = h_observed / ⌊log₂ n⌋, quantifying deviation from the information-theoretic lower bound.
• Node Memory Allocator & Cache Profiler: Virtual memory monitor tracking heap byte allocation (32 to 48 bytes per node), child pointer alignment, and non-contiguous pointer-chasing cache line traversal latencies.
• Complete balanced binary search tree with distinct keys inserted in optimal balanced sequence.
• Hardware-coordinated 64-bit tree node memory architecture with 32 to 48 bytes allocated per dynamic node.

4. Theory and graph choice

The Binary Search Tree (BST) is a foundational hierarchical abstract data type that unites the efficient dynamic insertion and deletion capabilities of linked structures with the logarithmic search efficiency of sorted contiguous arrays. Formally, a binary search tree is a rooted, recursive binary tree structure where every node x satisfies the strict Binary Search Tree Invariant: for any node y residing in the left subtree of x, key(y) < key(x); and for any node z residing in the right subtree of x, key(z) > key(x). This simple yet profound ordering property guarantees that an in-order traversal (Left, Node, Right) visits every stored key in strictly ascending monotonic order in linear O(n) time. More critically, the invariant enables divide-and-conquer search operations: at each visited node, a single scalar comparison between the query key and the node's stored value eliminates either the entire left subtree or the entire right subtree from the remaining candidate space, mirroring the bisection strategy of Binary Search. However, unlike a sorted array where random access guarantees an invariant O(log n) bisection depth, the operational efficiency of a binary search tree is entirely determined by its topological shape and height h. In an optimally balanced binary search tree containing n keys, the maximum path depth from root to leaf is bounded by h_min(n) = ⌊log₂ n⌋ + 1, ensuring that search, insertion, and deletion operations execute in worst-case O(log n) time. Conversely, if keys are inserted in monotonic sorted or pathological order (e.g., 1, 2, 3, ...), every newly inserted node branches exclusively to the right, causing the tree structure to collapse into a degenerate singly-linked list of height h = n. Under such degeneracy, search performance catastrophically degrades from logarithmic O(log n) to linear O(n), imposing quadratic O(n²) cumulative costs to build the tree. To eliminate this pathological vulnerability, modern computer science developed Self-Balancing Binary Search Trees, most notably AVL trees (Adelson-Velsky and Landis, 1962) and Red-Black trees (Bayer, 1972; Guibas and Sedgewick, 1978). These balanced tree variants augment each node with balance metadata (such as an integer balance factor or a 1-bit color flag) and execute local O(1) pointer transformations known as Tree Rotations whenever an insertion or deletion violates pre-established structural symmetry invariants. In this laboratory investigation, students use virtual machine register telemetry and visual tree profilers to construct binary search trees across varying scale parameters n in [64, 4096], measure empirical tree height h against logarithmic key entropy x = log₂(n), calculate the empirical height scaling factor α via ordinary least-squares regression, contrast balanced trees with degenerate linked topologies, and verify the branchless pointer mechanics of AVL tree single and double rotations.

The mathematical regression fits the linear model y = mx + b, where x = log₂(n) represents key entropy in bits, y = h represents tree height in levels, m represents the height scaling factor alpha, and b represents the baseline leaf level offset (theoretically b = 1.0000 level). The gradient has physical units levels/bit.

5. Method

1. Configure the virtual laboratory environment with 64-bit pointer alignment and verify that the root pointer is initialized to NULL with a baseline tree height of 0 levels.
2. Adjust the independent variable control slider to choose a dataset size n between 64 and 4,096 keys across the designated power-of-two benchmark settings.
3. Trigger the benchmark engine to insert n unique keys into the binary search tree using optimal balanced insertion, maintaining the structural invariant across all subtrees.
4. Read the deterministic root-to-leaf height h from the height register, verify that h matches ⌊log₂ n⌋ + 1 levels, and record the observation into the experimental notebook.
5. Systematically iterate through all 7 power-of-two key counts (n = 64, 128, 256, 512, 1024, 2048, and 4096 keys), recording the exact tree height for each dataset scale.
6. Plot measured tree height h against logarithmic key entropy x = log₂(n), perform Ordinary Least-Squares regression to compute the height scaling factor α, and compare with degenerate unbalance.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 1.8898e-07. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 1.7423e-06.

Propagating the fit parameters yields a fit standard error of 1.8898e-07 levels/bit, with an ideal coefficient of determination R² = 1.000000.

In discrete tree algorithm analysis, the minimum height h_min(n) = ⌊log₂ n⌋ + 1 of a complete balanced binary search tree is an exact combinatorial invariant derived from decision tree entropy. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete tree levels or key comparisons. However, in physical semiconductor microprocessors, tree traversal latency and memory access time deviate from idealized theoretical models due to memory hierarchy and pipeline dynamics: (1) Pointer chasing cache line misses: because child nodes reside at non-contiguous heap addresses, descending each level (node = (k < node->key) ? node->left : node->right) incurs cold CPU L1/L2 data cache stalls (~100–250 CPU cycles) once dataset size exceeds cache capacity; (2) Hardware spatial prefetcher failure: stream prefetchers excel at sequential array scans but cannot predict non-linear pointer dereferences, giving contiguous vectors a massive practical advantage over pointer-based trees; (3) Branch predictor mispredictions in inner key comparisons, which stall superscalar execution pipelines by 15–20 clock cycles; and (4) Insertion order asymmetry: in unaugmented binary search trees, sorted or pathological sequences cause catastrophic tree collapse into a singly-linked list of height h = n, increasing search latency by over 300×. Ordinary least-squares linear regression of observed tree height against logarithmic key entropy x = log₂(n) across systematically doubled scales n in [64, 4096] yields an empirical height scaling slope alpha = 1.0000 levels/bit with zero residual error (R² = 1.00000), verifying the logarithmic height bound Θ(log₂ n) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations perfectly align with the combinatorial capacity theorem for binary trees. Because each node has at most two children, a binary tree of height h can accommodate at most 2^h − 1 nodes. Inverting this geometric relationship yields the fundamental lower bound on tree height: h ≥ ⌈log₂(n + 1)⌉ = ⌊log₂ n⌋ + 1. The regression slope m = 1.0000 confirms that tree height increases by exactly 1 level each time dataset size doubles, mirroring the 1-bit entropy halving of Binary Search. Furthermore, topological comparison across insertion sequence regimes illustrates the vital importance of balance invariants: while randomly constructed binary search trees achieve an acceptable average search depth E[D(n)] ≈ 1.386 log₂ n, pathological monotonic insertion sequences (such as sorted datasets) cause unaugmented trees to collapse into degenerate singly-linked lists of height h = n. Under such degeneracy, search performance degrades catastrophically from O(log n) to O(n), and cumulative construction cost explodes to quadratic O(n²). Finally, the rotation sandbox demonstrates that local single (LL, RR) and double (LR, RL) tree rotations restore balance factor equilibrium (|BF| ≤ 1) in strictly O(1) time with 3 to 5 pointer updates, guaranteeing worst-case O(log n) bounds without whole-tree reconstruction.

11. Precautions and limitations

• Always update parent and child pointer links in strict sequence during tree rotations to prevent broken pointer chains and detached orphan subtrees.
• Carefully recalculate height and balance factor fields immediately after rotation transformations, as parent balance factors depend on updated child heights.
• In recursive tree implementations, beware of deep recursion stack overflow when testing degenerate or pathological insertion sequences; prefer iterative or tail-call formulations for large scale benchmarks.
• When profiling physical memory consumption, account for 64-bit allocator alignment padding: each tree node typically consumes 32 to 48 bytes depending on parent pointer and color tag packing.

The simulated execution model evaluates complete balanced binary search trees where height scales deterministically as h(n) = ⌊log₂ n⌋ + 1 levels. In physical computer systems, tree performance is modulated by dynamic memory allocator fragmentation, non-contiguous heap pointer chasing across CPU cache lines, TLB virtual memory translation misses for large datasets, and non-deterministic tree shapes resulting from arbitrary insertion and deletion sequences. The simulated benchmark environment reflects an idealized complete balanced binary search tree where n distinct keys are distributed with optimal structural symmetry. For any key count n, the maximum tree height is deterministically governed by the floor logarithm h(n) = ⌊log₂ n⌋ + 1 levels. Across the designated power-of-two benchmark samples n in [64, 128, 256, 512, 1024, 2048, 4096], the logarithmic entropy x = log₂(n) scales through exact integer values [6, 7, 8, 9, 10, 11, 12] bits, yielding tree heights h in [7, 8, 9, 10, 11, 12, 13] levels. Consequently, the empirical relationship satisfies the exact linear model h = 1.0000 · log₂(n) + 1.0000 levels, providing an ideal microarchitectural testbed for Ordinary Least-Squares regression with zero residual error.

12. Conclusion

This laboratory investigation quantitatively verified the tree height dynamics, search path geometry, and balancing mechanics of Binary Search Trees. Through systematic benchmarking across datasets from 64 to 4096 keys, we verified the empirical height scaling factor alpha = 1.0000 levels/bit with an ideal coefficient of determination R² = 1.00000. The investigation established the microarchitectural necessity of self-balancing tree architectures, proving how AVL and Red-Black tree invariants protect systems from O(n) worst-case collapse, and demonstrating why multi-way B-trees remain the foundational storage architecture for high-fanout disk and cache-resident database engines.