visual-cs

Treap - randomized BST + max-heap on priorities

← All visualizations

Treap
Priority Playground

Insert, search, and delete integer keys while a randomized priority keeps the binary search tree balanced in expectation. The tree preserves BST order by key and max-heap order by priority, using rotations to restore heap order after updates.

Root
Empty
key / priority at the root
Nodes
0
stored integer keys
Height
0
longest root-to-leaf path
Rotations
0
performed in the current replay
Speed 700ms
Preset Sequences
Treap Canvas
Nodes show key and priority. Yellow highlights mark the access path; pink marks a rotation pivot.
Ready. Build a treap or load a preset sequence.
Invariant: inorder traversal stays sorted by key, while priorities form a max-heap.
Normal node
Path / compared node
Current focus
Rotation pivot
Successful hit / inserted node
Delete target
How treaps rebalance. Every node gets a random priority on insertion. First place the key using normal BST rules, then rotate the new node upward while its priority is greater than its parent. Deletion does the inverse: rotate the target downward toward a leaf, always promoting the child with the higher priority, then remove it. Expected height stays O(log n) because random priorities simulate a random BST.

Current Stats

OK
BST Order
OK
Heap Order
0
Path Length
1
RNG Seed

Operation Notes

Treaps split balancing work across two fields: key determines search order, priority determines shape. That separation makes rotations easy to explain visually.

Recent Operations

Quick Facts

Insert/search/delete are expected O(log n). The same rotation primitives as AVL and red-black trees appear here, but the balancing rule is probabilistic instead of deterministic.