= Raimund Seidel
{c}
<Raimund Seidel> coauthored <Randomized Search Trees by Raimund Seidel and Cecilia R. Aragon> with <Cecilia R. Aragon>. The paper analyzes search <tree (graph theory)>[trees] whose shape is governed by random priorities. Combining <binary search tree> order and <heap order> gives the <treap>, supporting searches, updates and split/join operations with <expected value>[expected] bounds.<Randomized Search Trees by Raimund Seidel and Cecilia R. Aragon>[abstract and §2]{ref}
The key idea is to analyze the distribution of the whole <tree (graph theory)>[tree] instead of enforcing a fixed local balance ratio after every update. For example, the item with highest priority becomes the root, and the same construction applies recursively to the smaller and larger keys. This turns priority independence into an analyzable balancing mechanism.
Back to article page
