平衡二分探索木(RBST)
説明
RBST(Randomized Binary Search Tree)は平衡二分探索木の一種。ランダムなノードを根にして期待値的に木の高さを$O(\log N)$ に抑える。
遅延評価が不要な場合は引数が $3$ つのコンストラクタを呼び出す。左からノードの大きさ, 二項演算, 単位元。
計算量
$O(\log N)$
実装例
応用 1: multiset, set
RBSTを単に multiset や set として使うことも可能。$k$ 番目に小さい値を $O(\log n)$ で取得できる機能を追加で持つ。
応用 2: 完全永続
永続をします（ア。コンストラクタに与える pool の大きさに十分な余裕を持つこと。
問題例
- 検証済AOJ 1508 RMQ
- 検証済(応用1)ARC 033 C データ構造
- 検証済(応用2)ARC 030 D グラフではない
- JOI2012 春合宿 コピー&ペースト