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.
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.
Insert value, delete value, run OS-SELECT with a chosen k, run OS-RANK on a selected node, step through the algorithm one comparison at a time, and toggle visibility of subtree-size labels on the tree diagram.
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.
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.
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.
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.
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.