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

... forms part of the Constitution of Canada adopted in 1982. The Charter developed out of the United Nations human rights and freedoms movement as enunciated in th ...

 
 
 
This page was created in 70.1 ms