treap
Sign in to saveIn 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.
Key facts
- Data structure.name
- Treap
- Data structure.type
- Randomized binary search tree
- Data structure.space_avg
- O(n)
- Data structure.space_worst
- O(n)
- Data structure.search_avg
- O(log n)
- Data structure.search_worst
- O(n)
- Data structure.insert_avg
- O(log n)
- Data structure.insert_worst
- O(n)
- Data structure.delete_avg
- O(log n)
- Data structure.delete_worst
- O(n)
- Data structure.build_avg
- O(nlogn)
- Data structure.build_worst
- O(nlogn)
- Data structure.image
- treap.svg
via Wikipedia infobox
Article
17 sectionsContents
- Description
- Operations
- Basic operations
- Building a treap
- Bulk operations
- Randomized binary search tree
- Comparison
- Implicit treap
- Operations
- Insert element
- Delete element
- Find sum, minimum or maximum in a given range
- Addition/painting in a given range
- Reverse in a given range
- See also
- References
- External links
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.
== Description == thumb|left|A treap with alphabetic key and numeric max heap order The treap was first described by Raimund Seidel and Cecilia R. Aragon in 1989; its name is a portmanteau of tree and heap. It is a Cartesian tree in which each key is given a (randomly chosen) numeric priority. As with any binary search tree, the inorder traversal order of the nodes is the same as the sorted order of the keys. The structure of the tree is determined by the requirement that it be heap-ordered: that is, the priority number for any non-leaf node must be greater than or equal to the priority of its children. Thus, as with Cartesian trees more generally, the root node is the maximum-priority node, and its left and right subtrees are formed in the same manner from the subsequences of the sorted order to the left and right of that node.