Home▸Algorithms & AI▸Order-Statistics Tree

🌳 Order-Statistics Tree

Explore how augmenting a balanced binary search tree with subtree-size counters unlocks O(log n) rank and selection queries, and see why rotations must repair those counts to keep the structure correct.

Algorithms & AI3DModerate60 FPS

The simulator builds a live red-black order-statistics tree, showing subtree-size counters on every node and updating them in real time as insertions, deletions, and rotations reshape the structure, then visualizes the single root-to-node descent path used by OS-SELECT and the root-to-node ascent path used by OS-RANK.

🔬 What It Demonstrates

🎮 How to Use

Insert or delete values to grow and shrink the tree, watching the size field on each node update automatically, including during rotations. Enter a rank k and run OS-SELECT to watch the algorithm descend the tree, highlighting the comparison against each node's left-subtree size at every level. Click any node and run OS-RANK to watch the algorithm climb back to the root, accumulating rank as it goes.

💡 Did You Know?

Because subtree size only ever needs a node's two immediate children to be recomputed, a single rotation, no matter how deep in the tree it occurs, only requires fixing two size fields, which is why the augmentation adds no asymptotic cost to insertion or deletion.

⚙ Under the hood

data structuresbinary search treered-black treealgorithmsorder statisticscomputer sciencebalanced trees

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install