RBST

説明

Randomized Binary Search Tree (RBST) は平衡二分探索木の一種。これを使って色々できるみたい。ランダムなノードを根にして、期待的に木の高さを $O(\log _{2} n)$に抑えている。

---

情報

項目	データ
計算量	クエリ $O(\log _{2} n)$

関数

Node *MakeRoot(value)
機能	$1$ノードの木を返す
引数	$value$: ノードの値
戻り値	木の根

Node *Merge(l, r)
機能	木l, 木r を結合
引数	$l, r$: 木の根
戻り値	新しい木の根

pair<Node*,Node*>Split(t, k)
機能	木$t$を $[0,k)[k,n)$で分割
引数	$t$: 木の根 $k$: 分割位置
戻り値	分割後の双方の木の根

Node *Insert(root, pos, value)
機能	位置$pos$に新しいノードを挿入(区間反転とかそういうときに使う)
引数	$root$: 木の根 $pos$: 挿入位置 $value$: 挿入ノードの値
戻り値	新しい木の根

Node *Erase(root, pos)
機能	$pos$番目のノードを削除
引数	$root$: 木の根 $pos$: 削除位置
戻り値	新しい木の根

int Lower_Bound(root, value)
機能	$value$ 以上の最左位置を返す
引数	$root$: 木の根 $value$: 検索値
戻り値	位置

Node* Insert(root, value)
機能	木に値 $value$ のノードを挿入($set$みたいに使いたいときに使う)
引数	$root$: 木の根 $value$: 挿入値
戻り値	新しい木の根

void Dump(root)
機能	木を表示
引数	$root$: 木の根
戻り値	なし

実装例

問題例

#	ソース	難易度
ARC033_C - データ構造	ARC033 C	★★★★
AOJ 1508 - RMQ	UAPC2012	★★★★★
コピー＆ペースト	JOI2012春合宿	★★★★★★
ARC030_D - グラフではない	ARC030 D	★★★★★★