Seven search trees

The same keys isolate what balancing policies change. In Fortune, related trees have to maintain a moving beachline through geometric events. Here the geometry is removed so that rotations and structural choices are easier to see. This is the focused building block, while the geometry workbench supplies the demanding application.

The comparison sends the same inserted values to a binary search tree, AVL tree, red-black tree, size-balanced tree, treap, splay tree, and 2–3–4 tree. A common controller handles input and collects their results. Shared sequences make differences in shape and structural work easier to inspect than separate demonstrations with unrelated inputs.

Random, repeated sequential, and advancing sequential batches provide different input patterns. A frequency heatmap records which values were requested and distinguishes the current batch from earlier input. This supplies context for the resulting structures, particularly when repeated values are involved.

Each implementation records structural events alongside its own state. The view exposes rotations, red-black colors, treap priorities, and the multiple keys held by a 2–3–4 node. Height and mean successful node-visit charts compare the resulting shapes. Mean visits weights every stored key equally; a multiway node visit is not the same as a single key comparison.

The visualization has a common SVG path for binary trees and a separate layout path for 2–3–4 nodes and children. It computes subtree widths, places descendants, and adjusts the view to fit the resulting bounds. Keeping the multiway representation explicit preserves the algorithm's structure instead of forcing every implementation into an identical binary picture.

The operation chart counts logged spins, splits, borrows, and merges. It gives a concrete view of how much restructuring accompanies the same insertion stream. Red-black recoloring appears in the event records but is excluded from this chart. Comparing the chart with the actual node arrangement makes that accounting choice visible.

A useful sequence is to compare a sorted batch with a random batch, then repeat an earlier range. Watch the unbalanced tree's shape, the balancing changes in the other structures, and the splay tree's movement toward the inserted or revisited value. This is a small instrumented study of implementation behavior: the diagrams and counters help explain what a balancing policy does on a particular input.

These are structural measurements, not frame-rate benchmarks. Treap guarantees are expected, splay guarantees are amortized, and AVL/red-black invariants differ; one generic “balance score” would hide those distinctions.