Encyclopedia > Treap

  Article Content

Treap

In computer science, a Treap is a binary search tree (BST) 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 obey BST 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 a BST and a heap.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Islandia, New York

... 36 years. For every 100 females there are 92.3 males. For every 100 females age 18 and over, there are 88.8 males. The median income for a household in the village is ...

 
 
 
This page was created in 25.3 ms