iPedia Free Information Center

Information about Treap

In computer science, a treap is a binary search tree that orders the nodes by adding a priority attribute to a node, as well as a key. [1] The nodes are ordered so that the keys form a binary search tree and the priorities obey the max heap order property. The name treap is a composition of tree and heap.
Enlarge picture
A treap with alphabetic key and numeric max heap order

Definitions

The treap was invented by Cecilia R. Aragon and Raimund G. Seidel in 1989, [2] though the authors credit Jean Vuillemin with studying essentially the same data structure in 1980.
  • If v is a left descendant of u, then key[v] < key[u];
  • If v is a right descendant of u, then key[v] > key[u];
  • If v is a child of u, then priority[v] <= priority[u];
During insertion, the value is also assigned a priority. (This priority may be random, in which case the use of a pseudorandom number generator is applicable.) Initially, insertion proceeds in a manner identical to general binary search tree insertion. After this is done, tree rotations are employed to restore the heap property: the in-order traversal sequence is invariant under rotations, so an in-order traversal still yields the same sequence of values.

If priorities are non-random, the tree will usually be unbalanced; this worse theoretical average-case behavior may be outweighed by better expected-case behavior, as the most important items will be near the root.

Treaps exhibit the properties of both binary search trees and heaps.

Related data structures

When the priority is randomly allocated according to subtree size, the structure is known as a randomized binary search tree or RBST.

References

1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein2001">Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001), Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, ISBN 0-262-03293-7
2. ^ Seidel, Raimund & Cecilia R. Aragon (1996), "Randomized Search Trees", Algorithmica 16 (4/5): pp. 464-497, <[1]

External links

Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems.
..... Click the link for more information.
binary search tree (BST) is a binary tree data structure which has the following properties:
  • Each node has a value.
  • A total order is defined on these values.
  • The left subtree of a node contains only values less than the node's value.

..... Click the link for more information.
heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B).
..... Click the link for more information.
Cecilia R. Aragon is an American computer scientist and champion aerobatic pilot.[1][2] In computer science, she is best known as the co-inventor (with Raimund Seidel) of the treap data structure, a type of binary search tree that orders nodes by adding a
..... Click the link for more information.
A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's
..... Click the link for more information.
binary search tree (BST) is a binary tree data structure which has the following properties:
  • Each node has a value.
  • A total order is defined on these values.
  • The left subtree of a node contains only values less than the node's value.

..... Click the link for more information.
A tree rotation is an operation on a binary search tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down.
..... Click the link for more information.
binary search tree (BST) is a binary tree data structure which has the following properties:
  • Each node has a value.
  • A total order is defined on these values.
  • The left subtree of a node contains only values less than the node's value.

..... Click the link for more information.
heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B).
..... Click the link for more information.
A randomized binary search tree (abbreviated RBST) is a type of binary search tree, with data nodes organized as in a normal binary search tree. Each node has also an access priority, namely p(n) which is chosen in a random fashion according to subtree size, every time a new
..... Click the link for more information.
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College.
..... Click the link for more information.
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.
..... Click the link for more information.

..... Click the link for more information.
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in
..... Click the link for more information.
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College.
..... Click the link for more information.
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.
..... Click the link for more information.

..... Click the link for more information.
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in
..... Click the link for more information.
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter