Science Fair Project Encyclopedia
Treap
In computer science, a treap is a binary search tree that orders the nodes by adding a random number priority attribute to a node, as well as a key. The nodes are ordered so that the keys form a binary search tree and the priorities obey the min heap order property.
- If v is a left child of u, then key[v] < key[u];
- If v is a right child of u, then key[v] > key[u];
- If v is a child of u, then priority[v] > priority[u];
- (priority[v] > priority[u] means u was inserted before v)
Treaps exhibit the properties of both binary search trees and heaps.
External links
09-23-2007 01:00:40
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details