Treap

Treap

In computer science, a treap is a binary search tree that orders the nodes by adding a random "priority" attribute to a node, as well as a key. Citation | title=Introduction to Algorithms, Second Edition
publisher=MIT Press and McGraw-Hill | year=2001 | isbn=0-262-03293-7 | pages=296-300
author=Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
] The nodes are ordered so that the keys form a binary search tree and the priorities obey themax heap order property. The name treap is a portmanteau of tree and heap.

Definitions

The treap was first described by Cecilia R. Aragon and Raimund G. Seidel in 1989,Citation | title=Randomized Search Trees
first1=Cecilia R. | last1=Aragon | first2=Raimund | last2=Seidel
journal=Foundations of Computer Science, 30th Annual Symposium on | pages=540-545 | year=1989
doi=10.1109/SFCS.1989.63531 | isbn=0-8186-1982-1
] Citation | title=Randomized Search Trees
first1=Raimund | last1=Seidel | first2=Cecilia R. | last2=Aragon
journal=Algorithmica | volume=16 | issue=4/5 | pages=pp. 464-497 | year=1996
url=http://citeseer.ist.psu.edu/seidel96randomized.html
doi=10.1007/s004539900061
] 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

External links

* [http://people.ksp.sk/~kuko/bak/index.html Treap Applet] by Kubo Kovac
* [http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/Treap-Example.html Animated treap]
* [http://www-tcs.cs.uni-sb.de/Papers/rst.ps Scientific paper about treaps from Raimund Seidel]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • treap — treáp ( puri), s.n. – (Olt.) Groapă în care se pune mîncarea cîinilor la tîrlă. sb. trap (Candrea). Trimis de blaurb, 30.03.2009. Sursa: DER …   Dicționar Român

  • Treap — In der Informatik ist ein Treap (Binary search Tree + Heap, wörtlich Haufen), auch Baufen, ein binärer Suchbaum. Jeder Knoten x besteht aus zwei Elementen: x.key (Element) x.priority (Priorität) Treaps wurden im Jahr 1996 von Cecilia R. Aragon… …   Deutsch Wikipedia

  • Treap — En informatique, un treap est un arbre binaire de recherche qui ordonne les données en utilisant une priorité en plus de la clé propre à l arbre de recherche. Les données sont organisées de manière à ce que les clés forment un arbre binaire de… …   Wikipédia en Français

  • Datenstrukturen — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Datenstruktur — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Deap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Doppelheap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Max-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Min-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”