Everything about Treap
Random search tree data structure
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: TreapA 5-minute orientation
- Pick up a classic book: Data structures and algorithm analysis in CThe most-reprinted book on the subject
- Read the landmark paper: Association rule mining using treapCited 24 times
- Go sideways: Join-based tree algorithmsA closely related topic
- Go sideways: Weight-balanced treeA closely related topic
đź“– Definitions
Noun A type of randomized binary search tree where nodes are labelled with randomly chosen priority values and which is simultaneously a heap on those priorities.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
đź“š Books worth reading
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Join-based tree algorithms In computer science, join-based tree algorithms are a class of algorithms for self-balancing binary search trees. This framework aims at designing highly-parall…
- Weight-balanced tree In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionari…
- AVL tree In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights…
- Red–black tree In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information…
- Binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each…
- Cartesian tree In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be…
- Random binary tree In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees…
- Brodal queue In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: O(1) for insertion, find-minimum, meld (merge…