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
Explorer

... sea explorer) Ferdinand Magellan, (c. 1470-1521), leader of first expedition around the world Douglas Mawson - Australian explorer of Antarctica N Fridtjof Nansen, ...

 
 
 
This page was created in 27.9 ms