Treap (Cartesian Tree)
Randomized balanced BST combining binary search on keys and heap on priorities.
Visualization
Interactive visualization for Treap (Cartesian Tree)
Interactive visualization with step-by-step execution
Implementation
1class TreapNode { constructor(public key:number, public pr:number=Math.random(), public l:TreapNode|null=null, public r:TreapNode|null=null){} }
2function treapRotateRight(y:TreapNode){ const x=y.l!; y.l=x.r; x.r=y; return x; }
3function treapRotateLeft(x:TreapNode){ const y=x.r!; x.r=y.l; y.l=x; return y; }
4function treapInsert(root:TreapNode|null, key:number, pr:number=Math.random()):TreapNode{ if(!root) return new TreapNode(key, pr); if(key<root.key){ root.l=treapInsert(root.l,key,pr); if(root.l!.pr>root.pr) root=treapRotateRight(root); } else { root.r=treapInsert(root.r,key,pr); if(root.r!.pr>root.pr) root=treapRotateLeft(root); } return root; }
5function treapFind(root:TreapNode|null, key:number):boolean{ if(!root) return false; if(root.key===key) return true; return key<root.key? treapFind(root.l,key): treapFind(root.r,key); }Deep Dive
Theoretical Foundation
Treap is a randomized balanced BST (binary search on keys) and a heap on priorities. Each insertion chooses a random priority. Standard BST insertion by key is followed by rotations to restore the heap property by priority, keeping expected height O(log n). Deletions rotate the target node down until it becomes a leaf, then remove.
Complexity
Time
O(log n)
O(log n)
O(n)
Space
O(n)
Applications
Industry Use
Ordered sets/maps
Implicit treaps for array/sequence operations (split/merge)
Rope-like text structures with split/concat
Use Cases
Related Algorithms
AVL Tree (Self-Balancing BST)
A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. Named after inventors Adelson-Velsky and Landis (1962), AVL trees guarantee O(log n) time for search, insert, and delete operations by maintaining balance through rotations. It was the first self-balancing binary search tree to be invented.
Segment Tree (Range Query Tree)
Segment Tree is a binary tree data structure for storing intervals/segments that enables efficient range queries (sum, min, max, GCD) and updates in O(log n) time. Each node represents an interval, with leaves representing single elements. Essential for competitive programming, it solves problems like range sum queries with updates, which would be O(n) with arrays but becomes O(log n) with segment trees.
Fenwick Tree (Binary Indexed Tree - BIT)
A data structure that can efficiently update elements and calculate prefix sums in O(log n) time. Also known as Binary Indexed Tree (BIT), invented by Peter Fenwick in 1994. Fenwick trees are more space-efficient and simpler than segment trees for range sum queries, using only O(n) space compared to segment tree's O(4n).
Lowest Common Ancestor (LCA)
Lowest Common Ancestor (LCA) finds the deepest node that is an ancestor of two given nodes in a tree. This fundamental tree query operation has applications in computational biology (phylogenetic trees), version control systems (finding merge base), network routing, and range queries. Multiple algorithms exist: simple recursive O(n), binary lifting O(log n) per query after O(n log n) preprocessing, and Tarjan's offline algorithm for batch queries.