= Cecilia R. Aragon
{c}
<Cecilia R. Aragon> coauthored the randomized search-tree construction with <Raimund Seidel>. Their <treap> combines <binary search tree> order on keys with <heap order> on random priorities. A key set and distinct priorities determine the <tree (graph theory)>[tree]; independent random priorities give <expected value>[expected] logarithmic search and update costs. The analysis separates <expected value>[expected] cost from the possibly linear height of a particular realization.<Randomized Search Trees by Raimund Seidel and Cecilia R. Aragon>[abstract and §2]{ref}
The construction makes balancing probabilistic without storing the explicit balance conditions used by <AVL trees>. Operations that split or join a <tree (graph theory)> preserve the two orderings, making the idea useful for both ordered dictionaries and <sequence> data structures.
Back to article page
