Treap

個人的メモ

(計算量について)
以下の説明はたしか Motwani, Raghavan の Randomized Algorithm で見た話だった気がする.
まず重要な事実として集合内の全ての要素のキーと優先度のペアが決まれば上記の 2 つの性質を満たす Treap は一意に定まるということに注意する. つまり Treap の形は要素の insert の順番などに依らない.
よって $n$ 個の要素({キー, 優先度}) {$a_1, p_1$}, ..., {$a_n, p_n$} ($p_1 >, ..., > p_n$) からなる Treap における各要素の深さを考えるとき, その Treap は $n$ 個の要素を $1$ から $n$ の順に insert してできたとして考えても一般性を失わない. また $\{a_1, ..., a_n\} = \{1, ..., n\}$ で優先度は全て異なることを便宜上仮定する.
さて要素 $x = \{a_x, p_x\}$ と Treap の根との間に要素がいくつあるか, つまり要素 $x$ の深さを考えるとする. まず $x$ の先祖で $a_x < a_y$ を満たすような要素 $y = \{a_y, p_y\}$ が存在する確率を考える. 今優先度の大きいものから順番に要素を挿入するので新たな要素は必ず葉として挿入されることに注意すると $a_x \le a_z < a_y$ を満たす任意の要素 $z = \{a_z, p_z\}$ は $y$ より後に挿入されたことが分かる. 各要素の優先度の値は互いに独立な同分布(もちろん分布は各要素のキー値にも依存しない)からのサンプルであるので要素 $x$ の先祖として $y$ が存在する確率は $1 / (a_y - a_x + 1)$ となる. また逆に $x$ の先祖で $a_x > a_{y'}$ を満たすような要素 $y' = \{a_{y'}, p_{y'}\}$ が存在する確率は $1 / (a_x - a_{y'} + 1)$ となる. この話はランダムピボット選択を行った場合のクイックソートの計算量解析にも現れるが, 結局上記の結果からキー値が $i$ である要素の深さの期待値は $H_i + H_{n - i + 1} - 1 = \O (\log n)$ となることが計算すると分かる($H$ は調和級数とする).
また Corollary としてキー値が $i$ である要素の深さの期待値は $1$ 〜 $n$ からなる長さ $n$ の数列をランダムピボット選択クイックソートしたときに要素 $i$ がピボットとして選ばれる再帰の深さの期待値と一致することも分かる.