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
Canadian Charter of Rights and Freedoms

... office and similar rights legal rights: the right to be presumed innocent until proven guilty, the right to retain a lawyer and to be informed of that right, and the ...

 
 
 
This page was created in 31.7 ms