Overview
A treap stores keys in search-tree order and random priorities in heap order, giving expected logarithmic height.
ExtendedSource checked
Treap
Combines binary search tree ordering with random heap priorities.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Randomized Search Tree
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
random prioritybinary search orderheap ordertree rotation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use when fast lookup needs random priority.
- Use when the input matches the assumptions behind randomized Search Tree.
When Not to Use
- Avoid when the operation mix does not benefit from the structure's maintenance cost.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Combines binary search tree ordering with random heap priorities
- Uses random priority and binary search order to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Treap invariant
keyleft < keynode < keyright and priorityparent ≤ prioritychild
key_left < key_node < key_right and priority_parent <= priority_childMaintains search ordering and heap ordering at the same time.
Pseudocode
- 1.Prepare the inputs and state needed for Treap.
- 2.Apply the random priority step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return stored structure.
Canonical Example
- Input
- Treap input with a small representative case
- Output
- Stored structure
- Explanation
- Treap applies random priority to produce stored structure.
Implementation Notes
- Test insertion, deletion, lookup, and boundary cases separately.
- Keep the random priority step separate enough to test independently.
Common Pitfalls
- Ignoring update costs can make a structure look faster than it is in practice.
- Forgetting to check edge cases can make Treap look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 4: Prepare the inputs and state needed for Treap.
data-structures-mechanismNotes
Treap should be used with the assumptions and tradeoffs of randomized Search Tree in mind.
Sources (1)
What each reference supports for this entry.
Randomized Search Trees
PaperOriginal reference for treaps/randomized search trees, heap priorities, and expected logarithmic operations.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toSkip List
Treaps and skip lists both use randomization to maintain expected logarithmic ordered-set operations.
Variant ofBinary Search Tree
Treap is a data-structure variant of Binary Search Tree with different update or query tradeoffs.
Related Algorithms
Tags
Data StructureTreeBalanced TreeRandomness