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
Quadratic formula

... solutions x, both of which are complex numbers. The two solutions are complex conjugates of each other. (In this case, the parabola does not intersect the x-axis at ...

 
 
 
This page was created in 45.2 ms