プログラミングコンテストでのデータ构造 2 ～平衡二分探索木編～
86 likes61,870 views
続き (動的木編) はこちら http://www.slideshare.net/iwiwi/2-12188845
![Treap 実装: ノード構造体
struct node_t {
int val; // 値
node_t *ch[2]; // = {左, 右};
int pri; // 優先度
int cnt; // 部分木のサイズ
int sum; // 部分木の値の和
node_t(int v, double p) : val(v), pri(p), cnt(1), sum(v) {
ch[0] = ch[1] = NULL;
}
};
26](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-26-320.jpg)
![Treap 実装: update
int count(node_t *t) { return !t ? 0 : t->cnt; }
int sum(node_t *t) { return !t ? 0 : t->sum; }
node_t *update(node_t *t) {
t->cnt = count(t->ch[0]) + count(t->ch[1]) + 1;
t->sum = sum(t->ch[0]) + sum(t->ch[1]) + t->val;
return t; // 便利なので t 返しとく
}
部分木に関する情報を計算しなおす
子が変わった時などに必ず呼ぶようにする
27](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-27-320.jpg)
![Treap 実装: 回転
(insert-erase ベース)
node_t *rotate(node_t *t, int b) {
node_t *s = t->ch[1 - b];
t->ch[1 - b] = s->ch[b];
s->ch[b] = t;
update(t); update(s);
return s;
}
子を，別の変数でなく，配列にすると，
左右の回転が 1 つの関数でできる
親の親のポインタを張り替えなくて良いのは，
各操作が常に部分木の根を返すように実装してるから (次)
31](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-31-320.jpg)
![Treap 実装: insert
(insert-erase ベース)
// t が根となっている木の k 番目に 値 val，優先度 pri のノード挿入
// 根のノードを返す
node_t *insert(node_t *t, int k, int val, double pri) {
if (!t) return new node_t(val, pri);
int c = count(t->ch[0]), b = (k > c);
t->ch[b] = insert(t->ch[b], k - (b ? (c + 1) : 0), val, pri);
update(t);
if (t->pri > t->ch[b]->pri) t = rotate(t, 1 - b);
}
このように，新しい親のポインタを返す実装にすると楽
（親はたまに変わるので．）
32](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-32-320.jpg)
![Treap 実装: merge
(merge-split ベース)
node_t *merge(node_t *l, node_t *r) {
if (!l || !r) return !l ? r : l;
if (l->pri > r->pri) { // 左の部分木の根のほうが優先度が高い場合
l->rch = merge(l->rch, r);
return update(l);
} else { // 右の部分木の根のほうが優先度が高い場合
r->lch = merge(l, r->lch);
return update(r);
}
}
※ merge-split ベースだと，子を ch[2] みたいに配列で管理するメリットは薄い
上では代わりに lch, rch としてしまっている
37](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-37-320.jpg)
![反転: 方法 1
真面目に反転を処理する
struct node_t {
int val; // 値
node_t *ch[2]; // = {左, 右};
int pri; // 優先度
int cnt; // 部分木のサイズ
int min; // 部分木の値の最小 (RMQ のため)
bool rev; // 部分木が反転していることを表すフラグ
…
};
まずは構造体にフィールドを追加
42](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-42-320.jpg)
![他色々: Skip List
[http://en.wikipedia.org/wiki/Skip_list]
? リストの階層
– 最下層は通常のソートされた連結リスト
– 層 ? に存在する要素は確率 0.5 で層 ? + 1 に存在
? 高い層をできるだけ使って移動，? log ?
? Path-copying による永続化ができない
（やっぱり木じゃないですが似たような機能ができるので仲間）
50](https://image.slidesharecdn.com/balancedbinarysearchtree-120328040632-phpapp01/85/2-50-320.jpg)
More Related Content
What's hot (20)
Viewers also liked (6)
More from Takuya Akiba (9)
Recently uploaded (8)
![ElasticsearchでSPLADEする [Search Engineering Tech Talk 2025 Winter]](https://cdn.slidesharecdn.com/ss_thumbnails/searchtech-250228102455-ddc5ce09-thumbnail.jpg?width=560&fit=bounds)
プログラミングコンテストでのデータ构造 2 ～平衡二分探索木編～
- 1. 2012/3/20 NTTデータ駒場研修所 (情報オリンピック春合宿) プログラミングコンテストでの データ構造２ ～平衡二分探索木編～ 東京大学情報理工学系研究科 秋葉 拓哉 1
- 2. 自己紹介 ? 秋葉 拓哉 / @iwiwi ? 東京大学 情報理工学系研究科 コンピュータ科学専攻 ? プログラミングコンテスト好き ? プログラミングコンテストチャレンジブック 2
- 3. データ构造たち (もちろん他にもありますが) ? 二分ヒープ ? 組み込み辞書 (std::map) ? Union-Find 木 初級編 ? Binary Indexed Tree コンテストでの データ構造１ ? セグメント木 (2010 年) ? バケット法 中級編 ? 平衡二分探索木 ? 動的木 本講義 ? （永続データ構造） 3
- 4. 話すこと 1. 平衡二分探索木 2. 動的木 3. 永続データ構造 (時間あれば) ? ちょっとむずい！ 「へ～」ぐらいの気持ちでも OK！ ? アイディアだけじゃなくて，実装にまで立ち入り，簡潔 に実装するテクを伝授したい 4
- 5. 平衡二分探索木 5
- 6. 普通の二分探索木 7 2 15 1 5 10 17 4 8 11 16 19 6
- 7. 普通の二分探索木: 検索 (find) 10 を検索 7 7と比較 15と比較 2 15 発見 1 5 10 17 4 8 11 16 19 7
- 8. 普通の二分探索木: 挿入 (insert) 7と比較 7 6 を挿入 2と比較 2 15 5と比較 1 5 10 17 4 6 8 11 16 19 追加 8
- 9. 普通の二分探索木: 削除 (erase) 15 を削除 7 15 削除 2 11 1 5 10 17 4 8 11 16 19 9
- 10. 普通の二分探索木の偏り 1, 2, 3, 4, … の順に挿入すると…？ 1 2 高さが ? ? ！ 3 処理に ? ? 時間！ 4 5 やばすぎ！ こういった意地悪に耐える工夫をする二分探索木 ＝ 平衡二分探索木が必要！ 10
- 11. …その前に！ 平衡二分探索木は本当に必要？ ? いつものじゃダメ？ – 配列，線形リスト – std::set, std::map – Binary Indexed Tree，バケット法，セグメント木 ? 実装が面倒なので楽に避けられたら避けたい ? 実際のとこ，本当に必要になる問題はレア 11
- 12. 例 範囲の大きな Range Minimum Query ? ある区間の最小値を答えてください ? ある場所に数値を書いてください ただし場所は 1～109．デフォルト値は ∞ ． そんな大きな配列作れない… セグメント木じゃできない… (??_?`) セグメント木でもできるよ ( ?`д??) クエリ先読みして座標圧縮しとけばいいよ 12
- 13. 例 範囲の大きな Range Minimum Query ? ある区間の最小値を答えてください ? ある場所に数値を書いてください ただし場所は 1～109．デフォルト値は ∞ ． でもクエリ先読みできないかも… (情オリの interactive とか，計算したら出てくるとか) (??_?`) 必要な场所だけ作るセグメント木でいいよ ( ?`д??) 13
- 14. 必要な场所だけ作るセグメント木 2 3 2 3 ∞ 8 2 5 3 ∞ 8 2 ∞ 5 3 ∞ ∞ ∞ 8 2 ∞ ? 以下が全てデフォルト値になってるノードは要らない ? ?(クエリ数 ???(場所の範囲)) のノードしかできない ? ?(??? 場所の範囲 ) でクエリを処理できる 春季選考合宿 2011 Day4 Apple 参照 14
- 15. 例2 反転のある Range Minimum Query ? ある区間の最小値を答えてください ? ある区間を左右反転してください 反転なんてできない… (??_?`) ( ?`д??) ??? おとなしく平衡二分探索木を書こう！ 15
- 16. 平衡二分探索木 (＆仲間) 超いっぱいあります AVL 木，赤黒木，AA 木，2-3 木，2-3-4 木，スプレー木， Scapegoat 木，Treap，Randomized Binary Search Tree，Tango 木，Block Linked List，Skip List，… ? ガチ勢: 赤黒木 （std::map とか） – (定数倍的な意味で) かなり高速 – でも実装が少し面倒 ? コンテスト勢: 実装が楽なのを組もう！ 16
- 17. コンテストでの平衡二分探索木 ? 大抵，列を管理するために使われる （探索木という感じより，ただの順序を持った列を高機能に扱う感じが多い） ? よく必要になるもの – ? 番目に挿入 (insert)，? 番目を削除 (erase) – 0, ? と ?, ? の 2 つの列に分割 (split) – 2 つの列を連結 (merge) – 値に関する質問?更新 (sum, add 等) これをサポートする木を作ろう！ 17
- 18. Treap の思想 ? 根がランダムに選ばれるようにする！ – 全ノードが等確率で根になるようにする – 部分木に関しても再帰的に，根をランダムに選ぶこ とを繰り返す ? これだけで高さが ? log ? ? なぜ？ 乱択クイックソートと同じ． 18
- 19. Treap の思想 Treap / RBST 乱択クイックソート ランダムに選ばれた ランダムに選ばれた 根 ピボット 根より ↓ 根より ↓ 小さい値 大きい値 ↑ ↑ ピボットより ピボットより 小さい値 大きい値 19
- 20. Treap の思想 (別解釈) 普通だと，挿入順は木にどう影響する？ c c c c b b d b d a ナイーブな二分探索木に c → b → d → a と挿入 先に挿入したものが上，後に挿入したものが下 20
- 21. Treap の思想 (別解釈) ? 普通の二分探索木でも，もしランダム順に挿入 されてたら必ず高さ ? log ? ? 実際の挿入順に構わず，ランダム順に挿入され たかのように扱おう！ – 常に std::random_shuffle した後で挿入されたかのう 21
- 22. Treap ? 乱数を用いる平衡二分探索木 ? 各ノードは，キーの他，優先度を持つ – 優先度は挿入時にランダムで決める キー 優先度 22
- 23. Treap 以下の 2 つの条件を常に保つ 1. キーを見ると二分探索木 2. 優先度を見ると二分ヒープ （Tree + Heap なので Treap という名前らしい…ワロスｗｗｗ） 大 優 先 度 小 小 キー 大 23
- 24. Treap ? 優先度が最高のやつが根になる – これは，全ノード等確率！ → 平衡！ – 部分木に関しても再帰的に同様 大 優 先 度 小 小 キー 大 24
- 25. Treap の実装法 大まかに 2 つの方法があります insert-erase ベース （insert, erase を実装し，それらの組み合わせで merge, split） merge-split ベース （merge, split を実装し，それらの組み合わせで insert, erase） 25
- 26. Treap 実装: ノード構造体 struct node_t { int val; // 値 node_t *ch[2]; // = {左, 右}; int pri; // 優先度 int cnt; // 部分木のサイズ int sum; // 部分木の値の和 node_t(int v, double p) : val(v), pri(p), cnt(1), sum(v) { ch[0] = ch[1] = NULL; } }; 26
- 27. Treap 実装: update int count(node_t *t) { return !t ? 0 : t->cnt; } int sum(node_t *t) { return !t ? 0 : t->sum; } node_t *update(node_t *t) { t->cnt = count(t->ch[0]) + count(t->ch[1]) + 1; t->sum = sum(t->ch[0]) + sum(t->ch[1]) + t->val; return t; // 便利なので t 返しとく } 部分木に関する情報を計算しなおす 子が変わった時などに必ず呼ぶようにする 27
- 28. Treap 実装: insert (insert-erase ベース) まず優先度を無視して普通に挿入 28
- 29. Treap 実装: insert (insert-erase ベース) 優先度の条件が満たされるまで回転して上へ 29
- 31. Treap 実装: 回転 (insert-erase ベース) node_t *rotate(node_t *t, int b) { node_t *s = t->ch[1 - b]; t->ch[1 - b] = s->ch[b]; s->ch[b] = t; update(t); update(s); return s; } 子を，別の変数でなく，配列にすると， 左右の回転が 1 つの関数でできる 親の親のポインタを張り替えなくて良いのは， 各操作が常に部分木の根を返すように実装してるから (次) 31
- 32. Treap 実装: insert (insert-erase ベース) // t が根となっている木の k 番目に 値 val，優先度 pri のノード挿入 // 根のノードを返す node_t *insert(node_t *t, int k, int val, double pri) { if (!t) return new node_t(val, pri); int c = count(t->ch[0]), b = (k > c); t->ch[b] = insert(t->ch[b], k - (b ? (c + 1) : 0), val, pri); update(t); if (t->pri > t->ch[b]->pri) t = rotate(t, 1 - b); } このように，新しい親のポインタを返す実装にすると楽 （親はたまに変わるので．） 32
- 33. Treap 実装: erase (insert-erase ベース) 1. 削除したいノードを葉まで持っていく – 削除したいノードの優先度を最低にする感じ – 回転を繰り返す 2. そしたら消すだけ 33
- 34. Treap 実装: merge / split (insert-erase ベース) ? insert, erase が出来たら merge, split は超簡単 ? merge(?, ?) – 優先度最強のノード ? を作る – ? の左の子を ?，右の子を ? にする – ? を erase ? split(?, ?) – 優先度最強のノード ? を木 ? の ? 番目に挿入 – ? の左の子と右の子をそっと取り出す 34
- 35. Treap 実装: insert / erase (merge-split ベース) ? 逆に，merge, split が出来たら insert, erase は超簡単 ? insert(木 t, 場所 k, 値 v) – 木 t を場所 k で split – 左の部分木，値 v のノードだけの木，右の部分木を merge ? erase(木 t, 場所 k) – 木 t を場所 k - 1 と場所 k で 3 つに split (split 2 回やればいい) – 一番左と一番右の部分木を merge 今度は， merge, split を直接実装してみよう 35
- 36. Treap 実装: merge (merge-split ベース) a a b ＋ = A b A B C D B ＋ C D ? 優先度の高い方の根を新しい根にする ? 再帰的に merge 36
- 37. Treap 実装: merge (merge-split ベース) node_t *merge(node_t *l, node_t *r) { if (!l || !r) return !l ? r : l; if (l->pri > r->pri) { // 左の部分木の根のほうが優先度が高い場合 l->rch = merge(l->rch, r); return update(l); } else { // 右の部分木の根のほうが優先度が高い場合 r->lch = merge(l, r->lch); return update(r); } } ※ merge-split ベースだと，子を ch[2] みたいに配列で管理するメリットは薄い 上では代わりに lch, rch としてしまっている 37
- 38. Treap 実装: split (merge-split ベース) split は優先度の事を何も考えないで再帰的に切るだけ （部分木内の任意のノードは根より優先度小なので大丈夫） pair<node_t*, node_t*> split(node_t *t, int k) { // [0, k), [k, n) if (!t) return make_pair(NULL, NULL); if (k <= count(t->lch)) { pair<node_t*, node_t*> s = split(t->lch, k); t->lch = s.second; return make_pair(s.first, update(t)); } else { pair<node_t*, node_t*> s = split(t->rch, k - count(t->lch) - 1); t->rch = s.first; return make_pair(update(t), s.second); } } 38
- 39. Treap 実装法の比較 insert-erase ベース （insert, erase を実装し，それらの組み合わせで merge, split） merge-split ベース （merge, split を実装し，それらの組み合わせで insert, erase） ? どっちでも良いです，好きな方で ? ただ，個人的には，merge-split ベースのほうが遥かに楽!! – 回転が必要ない，を筆頭に，頭を使わなくて済む – コードも少し短い – あと，コンテストでは，insert, erase より merge, split が必要にな ることの方が多い 39
- 40. その他，実装について ? malloc?new – 解放?メモリリークやオーバーヘッドが気になる？ – グローバル変数としてノードの配列を 1 つ作っておき，そこか ら 1 つずつ取って使うと良い ? merge-split ベースでの真面目な insert 1. 優先度が insert 先の木より低ければ再帰的に insert 2. そうでなければ，insert 先の木を split してそいつらを子に – という真面目な実装をすると，定数倍すこし高速 – erase も同様：再帰していって merge 40
- 41. 例题 反転のある Range Minimum Query ? ある区間の最小値を答えてください ? ある区間を左右反転してください …結局これはどうやるの？ 反転って？ (??_?`) 2 つの方法があるよ ( ?`д??) 41
- 42. 反転: 方法 1 真面目に反転を処理する struct node_t { int val; // 値 node_t *ch[2]; // = {左, 右}; int pri; // 優先度 int cnt; // 部分木のサイズ int min; // 部分木の値の最小 (RMQ のため) bool rev; // 部分木が反転していることを表すフラグ … }; まずは構造体にフィールドを追加 42
- 43. 反転: 方法 1 区間 [l, r) を反転したいとする 1. 場所 l, r で split → 3 つの木を a, b, c とする 2. b の根ノードの rev フラグをトグル 3. 木 a, b, c を merge rev フラグはどのように扱う？ 43
- 44. 反転: 方法 1 void push(node_t *t) { if (t->rev) { ? rev フラグの扱い swap(t->lch, t->rch); if (t->lch) t->lch->rev ^= true; // 子に反転を伝搬 if (t->rch) t->rch->rev ^= true; // 子に反転を伝搬 t->rev = false; } } rev フラグによる反転を実際に反映する関数 push ノードにアクセスするたびに最初にこれを呼ぶようにする セグメント木における更新遅延と同様のテクニック （いっぱい push 書きます，書き忘れに注意！） ※数値の更新なども同様に，フラグ的変数作って push する (区間への一様な加算など） 44
- 45. 反転: 方法 2 はじめから 2 本の列をツリー t1, t2 で管理 ? t1：順向き ? t2：逆向き 区間 [l, r) を反転したいとする ? t1 の [l, r) と，t2 の [l, r) を split して切り出す ? 交換して merge t1 1 2 3 4 5 6 簡単． （ただし，無理なケースも．） t2 6 5 4 3 2 1 45
- 46. 他色々: RBST (Randomized Binary Search Tree) ? Treap と同様に，ランダムなノードを根に来させる ? ただし，ノードに優先度など余分な情報が不要！ ? merge(a, b) – n ノードの木 a と m ノードの木 b マージの場合 – 全体 (n + m) ノードから根が等確率で選ばれていれば良い ? ? – 確率 で a の根を新しい根，確率 で b の根を新しい根に ?+? ?+? – これを，必要に応じて乱数を発生して決める Treap よりこっちのほうが構造体がシンプルになってカッコイイかも 46
- 47. 他色々: スプレー木 ? 一見よくわからん回転を繰り返す ? でも実はそれで平衡される！という不思議系データ構造 ? 基本: ノード ? にアクセスする際，そのついでに回転を 繰り返して ? を木の根まで持ってくる – この行為をスプレーと呼ぶ．splay(?) – ただし，回転のさせ方にちょっと工夫 ? ならし ?(log ?) 時間で操作 (ポテンシャル解析) ? コンテスト界でそこそこ人気 47
- 48. 他色々: スプレー木 回転ルール: 下図を覚えさえすれば OK z x x y y z x z y 普通にやるとこっち ? x が上に行くようにどんどん回転！ になっちゃう ? ただし，2 つ親まで見る – そこまで直線になってたら直線のままになるように y, x の順で回転 （上図） – そうなってなかったら普通に x を上に行かせる回転 2 連発 ? 詳しくは http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%97%E3%83%AC%E3%83%BC%E6%9C%A8 48
- 49. 他色々: Block Linked List ? 平方分割をリストでやろう的な物 ? サイズ ? 程度のブロックに分けて，スキップできるように ? ブロックのサイズが変化してきたら調整 – 2 ? を超えたら 2 つに分割 – 連続する 2 ブロックのサイズの和が ?/2 未満になったら併合 – こうしとけば常にどこでも ?( ?) で辿れる！ ? Wikipedia の中国語にだけ載ってる （木じゃないですが似たような機能ができるので仲間ということで） 49
- 50. 他色々: Skip List [http://en.wikipedia.org/wiki/Skip_list] ? リストの階層 – 最下層は通常のソートされた連結リスト – 層 ? に存在する要素は確率 0.5 で層 ? + 1 に存在 ? 高い層をできるだけ使って移動，? log ? ? Path-copying による永続化ができない （やっぱり木じゃないですが似たような機能ができるので仲間） 50
- 51. 平衡二分探索木まとめ ? まずはもっと容易な道具を検討！ – 配列, リスト, std::map，BIT，セグメント木，バケット法 – 必要な场所だけ作るセグメント木 ? 実装が楽な平衡二分探索木を選ぼう – 今回: Treap / Randomized Binary Search Tree – 他: スプレー木, Scapegoat 木, Block Linked List, Skip List ? 実装しよう – insert / erase ベース vs. merge / split ベース – 更新遅延 51