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; independent random priorities give expected logarithmic search and update costs. The analysis separates expected cost from the possibly linear height of a particular realization.[ref]
The construction makes balancing probabilistic without storing the explicit balance conditions used by AVL trees. Operations that split or join a tree preserve the two orderings, making the idea useful for both ordered dictionaries and sequence data structures.
New to topics? Read the docs here!