One ordered set. Seven ways to pay for maintaining it.
Insert a sorted batch. The naive BST becomes a chain while AVL, red–black and size-balanced trees reorganize it.
Compare height, mean node visits and structural edits. These measure different costs; fewer rotations alone do not establish a faster tree.
Repeat a batch to see splaying react to existing keys. Treap priorities give expected logarithmic behavior, not a worst-case guarantee.
Simple binary tree with O(n) worst case. Left children are smaller, right children are larger.
Used in simple databases and file systems where balance is not critical.
Can get O(N) lookup complexity in worst case. Once a long linear chain forms, it will never self-correct without manual deletion.
Self-balancing tree maintaining |height(left) - height(right)| ≤ 1 at every node.
Used in databases requiring strict lookup time guarantees and frequent searches.
Guarantees O(log N) operations with strict height balance.
Sometimes considered too strict — performs more rotations than necessary compared to RBT.
Balanced using node colors with relaxed balance rules. Height ≤ 2log₂(n+1).
A looser height invariant trades strict balance for different update behavior.
Logarithmic height is guaranteed. Compare the recorded rotations here; total runtime also depends on metadata, comparisons and memory access.
More complex to implement than simpler balanced trees.
Maintains balance using subtree sizes. Size(left) and Size(right) bounded by each other's children.
Popular in competitive programming for order statistics and rank queries.
Efficiently supports finding k-th smallest element and node ranking operations.
Subtree sizes support rank-based operations as well as the balance invariant.
Randomized BST with heap property on priorities. Maintains balance probabilistically.
Good for dynamic sets with frequent insertions/deletions and no strict balance requirements.
Worst-case O(N) complexity exists, even with a working random generator. Independent random priorities give expected logarithmic depth.
Expected and worst-case guarantees answer different questions.
Self-adjusting tree bringing accessed elements to root via rotations (splaying).
Excellent for caches and memory systems where recently accessed items are likely to be accessed again.
Self-optimizing: accessing existing nodes restructures the tree for better future access patterns.
One operation can take O(N); sequences have amortized O(log N) cost. A temporarily tall tree is consistent with that guarantee.
B-tree variant where nodes can have 2, 3, or 4 children. All leaves share one depth; each node stores up to three keys.
Used in file systems and databases for efficient disk I/O operations.
Multi-way branching minimizes tree height, reducing disk reads in large datasets.
More complex node structure makes implementation and debugging harder.
A successful lookup, averaged uniformly over stored keys. Current shape, before any splaying.
Recorded rotations, splits, merges and borrows; cumulative since Clear.
Height counts node levels. Mean node visits averages root-to-key paths in the current tree, with each stored key equally likely. For a 2-3-4 node, all its keys share one node visit: this is a storage-access metric, not the number of key comparisons.
Structural edits count logged rotations (a double rotation counts twice), splits, merges and borrows. Recoloring, size/height updates, comparisons, allocations and drawing are excluded. The bars are observations of this run, not a timing benchmark or a universal ranking.
Try sorted, then random batches. Look for the tension between short lookup paths and the maintenance needed to obtain them. Repeated keys do not increase the set size; splay can still move an existing key to the root.