Treapはなぜランダムな優先度で木の崩壊を防げるのか

Treap (Cartesian Tree)

Treapは二分探索木と二分ヒープを組み合わせたデータ構造で、キーとランダムな優先度の組を保持する。優先度がなければ木は連結リスト状に退化し最悪O(n)になるが、優先度をランダムに選ぶことで平均O(log n)が保証される。SplitとMergeという2つの補助操作だけで挿入・削除・検索・結合まで実装できる点が特徴で、1989年にSiedelとAragonが提案した。