狠狠撸

データを工夫して记録するデータ构造
Katsutoshi Nagaoka
2013/05/30
1

Agenda
? 復習
? 木
? 二分木
? プライオリティキュー
? 二分ヒープ
? 問題
? プライオリティキューを用いる問題
2

Agenda
? 復習
? 二分探索木
? 平衡二分探索木
? Union-Find 木
? 問題
? Union-Find 木を用いる問題
3

? 図中の丸を「ノード」と呼ぶ
用語の定義 (1/8)
ノード
6

? 図中の線を「辺」と呼ぶ
辺
7

? 各ノードを「親」と「子」の関係で呼ぶ
親
子子
8

子
? 各ノードを「親」と「子」の関係で呼ぶ
親
子
9

? 同じ親を持つノードを「兄弟」と呼ぶ
親
子子兄弟
10

? 同じ親を持つノードを「兄弟」と呼ぶ
子
親
子兄弟
11

? 一番上のノードを「根」と呼ぶ
根
12

? 子を持たないノードを「葉」と呼ぶ
葉
葉
葉
13

? 全てのノードにおいて、子が 2 個以下である木のこと
? 数字は子の数
0
二分木とは
2
1 2
00
15

? 子が 2 個以上ある木
0
二分木ではない例
3
0 3
0
0
0
×
×
16

プライオリティキュー
17

プライオリティキューとは
? 仕様
? 数を追加する
? 最小の数値を取り出す (値を取得し、削除する)
18

概要図 (1/2)
? 値の追加
5
1
4
5
1
4
3
3 を追加する
19

概要図 (1/2)
? 最小値の取り出し
5
1
4
5 4
最小値を取り出す
20

二分ヒープとは
? プライオリティキューを効率的に実現する実装の 1 つ
? 二分ヒープは、二分木を用いて処理を行う
2 4
7 8 5
1
22

二分ヒープのルール (1/2)
? 子の数字は親の数字より大きい
1
2 4
7 8 5
<<
<
< <
23

二分ヒープのルール (2/2)
? 木は上から下へ、左から右へ順にノードが詰まっている
1
2 4
7 8 5
a
b c
e f g
24

? 新たな数字を最後尾に追加する
新しい値の追加 (1/4)
1
2 4
7 8 5
25

? 追加した数字を逆転がなくなるまで上げていく
1
2 4
7 8 5 3
26

? 追加した数字を逆転がなくなるまで上げていく
1
2 3
7 8 5 4
27

? 二分ヒープのルールに従った二分木になった
1
2 3
7 8 5 4
28

? 根の数字を取り出す
最小値の取り出し (1/7)
1
2 3
7 8 5
29

? 最後尾の数字を根にコピーする
2 3
7 8 5
30

? 最後尾の数字を削除する
5
5
2 3
7 8
×
31

? 根にコピーした数字を逆転が無くなるまで下げる
5
2 3
7 8
32

? 逆転する対象が 2 つある場合は小さい方に下げる
5
2 3
7 8
33

? 逆転する対象が 2 つある場合は小さい方に下げる
2
5 3
7 8
34

? 二分ヒープのルールに従った二分木になった
2
5 3
7 8
35

? 値の追加?最小値の取り出しは、木の深さに比例した時間がかかる
? 要素数を n とすると、Order (log n)
? この場合は Order (log 5)
二分ヒープの計算量
2
5 3
7 8
36

プライオリティキューの実装
37

? 多くの言語にて、効率的に実装されたライブラリが標準で含まれる
? C 言語の場合は priority_queue
? Java 言語の場合は java.util.PriorityQueue, java.util.PriorityBlokingQueue
プライオリティキューの実装
38

? トラックで距離 X を移動する
? タンク容量に制限はない
? ガソリン P が積まれている
? 距離 1 に対してガソリン 1 を消費する
? 移動途中にガソリンスタンドが N 個ある
? 各ガソリンスタンドは、給油可能量に制限がある
? 最小で何回の給油が必要か求めよ
Expedition 問題
40

? 考え方
? 一番近いガソリンスタンドに移動し、ガソリンが無くなったら通
過した中で最も給油量が多い場所で給油したことにする
? ソースコード
? https://github.com/na-ga/pcontest/tree/master/src/main/java/pcontest/
datastructure1/question1 ?
Expedition 回答
41

? とても長い板から、N 個の板を切り出す
? 長さ 1 の板を切断するにはコスト 1 が発生する
? 長さ 21 の板から、長さ 5, 8, 8 の 3 つの板を切り出す
? 最小のコストを求めよ
FenceRepair 問題
42

? 考え方
? 最も小さい板 2 つを結合する
datastructure1/question2 ?
FenceRepair 回答
43

? 次のような操作が効率的に行えるデータ構造
? 数値を追加する
? ある数値が含まれているかを調べる
? ある数値を削除する
二分探索木とは
45

? こんな感じ
二分探索木の例
7
2 15
10 1751
198 16114
46

? 全てのノードにおいて
? 左の子以下の数は、自分の数より全て小さい
? 右の子以下の数は、自分の数より全て大きい
二分探索木のルール
7
2 15
10 1751
198 16114
47

? 追加する値を、根から順番に比較する
? 小さい場合は左の子を比較する
? 大きい場合は右の子を比較する
? 比較対象が存在しなかった場合追加する
値の追加方法
7
2 15
10 1751
198 16114
48

? 追加する値を、根から順番に比較する
値の追加例 (1/5)
7
2 15
10 1751
198 16114
6
49

? 7 より小さいので左の子を比較する
7
2 15
10 1751
198 16114
6比較
50

? 2 より大きいので右の子を比較する
7
2 15
10 1751
198 16114
6比較
比較
51

? 5 より大きいので右の子を比較する
7
2 15
10 1751
198 16114
6比較
比較
比較
52

? 二分探索木のルールを守った二分木になった
7
2 15
10 1751
198 16114 6
53

? 削除ノードから順番に比較する
? 削除ノードが左の子を持っていない場合、右の子を移動
? 削除ノードの左の子が右の子を持っていない場合、左の子を移動
? どちらでもない場合、左の子以下で最も大きいノードを移動
値の削除方法
7
2 15
10 1751
198 16114
54

? 削除ノードから順番に比較する
値の削除例 (1/5)
7
2 15
10 1751
198 16114
×
55

? 削除ノードから見て、左の子が存在するか確認する
7
2 15
10 1751
198 16114
×1. 確認
56

? 削除ノードから見て、左の子の右の子が存在するか確認する
7
2 15
10 1751
198 16114
×1. 確認
2. 確
認
57

? 削除ノードから見て、左の子以下で一番大きいノードを移動する
7
2 15
10 1751
198 164
1. 確認
2. 確
認
3. 移動
11
×
58

? 二分探索木のルールを守った二分木になった
7
2 11
10 1751
198 164
59

? 木の深さに比例した時間がかかる
? 要素数を n とすると、平均 Order (log n)
? この場合は、平均 Order (log 12)
二分探索木の計算量
7
2 11
10 1751
198 164
60

? 多くの言語にて、効率的に実装されたライブラリが標準で含まれる
? C 言語の場合は STL に set と map が含まれている
? Java 言語の場合は java.util.TreeSet と java.util.TreeMap が該当する
二分探索木の実装
61

? 単純な二分探索木は偏りが生じる
? 偏りが生じると二分探索木の計算量にメリットが無くなる
? 平衡二分探索木は回転処理などを使用して常に平衡を保つ
? 多くのプログラミング言語に含まれる二分探索木の実装は、
平衡二分探索木となっているため、意識する必要はない
平衡二分探索木
63

? グループ分けを管理するデータ構造
? 2 つのグループを結合する
? 2 つの要素が同じグループに属しているか判定する
Union-Find 木とは
65

? 2 つのグループを結合する
Union-Find 木の概要図 (1/2)
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 5 3 4 6 7
66

? 2 つの要素が同じグループに属しているかを判定する
? 2 と 5 → true
? 2 と 4 → false
1 2 5 3 4 6 7
Union-Find 木の概要図 (2/2)
67

? 同じグループなら同じ数字を配列に入れる
1 2 5 3 4 6 7
簡単に思いつく実装例 (1/2)
int data[7];?
data[0] = 1; ?
data[1] = 1; ?
data[2] = 2;??
data[3] = 3;?
?
data[4] = 1; ?
data[5] = 3; ?
data[6] = 3;?
?
68

? グループの結合にかかる計算量は Order (n) となり効率悪い
1 2 5 4 6 7 3
簡単に思いつく実装例 (1/2)
int data[7];?
data[0] = 1; ?
data[1] = 1; ?
data[2] = 2;??
data[3] = 1; ★?
?
data[4] = 1; ?
data[5] = 1; ★??
data[6] = 1; ★??
?
69

? グループを木で表現する
1 2 5 3 4 6 7
Union-Find 木の仕組み (1/3)
1
2 5
3 4
6 7
70

? 結合は、片方の根からもう片方の根に辺を張る
1
2 5
4
6
7 1
2 5
4
6
7
71

? 判定は、2 つの要素を上にって根が同じかどうか見る
? 2 と 5 → 根は 1 と 1 → true
? 2 と 7 → 根は 1 と 3 → false
1
2 5
3
4
6 7
72

? 判定処理において、調べた辺を根に直接つなぎ直す
? 4 の根を調べると、2, 3, 4 の根が 1 と分かるので根に直接つなぐ
Union-Find 木の経路圧縮
1
2
3
1
32 44
73

? 結合処理において、木の高さ (=ランク) の低い方を高い方につなげる
Union-Find 木のランク
1
2 5
4
6
7 1
2 5
4
6
7
Rank2 Rank3
74

? 非常に高速に動作する
? 経路圧縮とランクを使用すると、平均 Order (α(n)) となる
? α(n) はアッカーマン関数 A(n, n) の逆関数
? 経路圧縮またはランクを使用すると、平均 Order (log n) となる
Union-Find 木の計算量
75

? https://github.com/na-ga/pcontest/blob/master/src/main/java/pcontest/
datastructure1/UnionFind.java ?
Union-Find 木の実装
76

? N 匹の動物は、それぞれ下記の A, B, C いずれかに属する
? A は B を食べ、B は C を食べ、C は A を食べる
? 下記の 2 種類の情報が、順番に k 個与えられる
? タイプ 1 : x と y は同じ種類です
? タイプ 2 : x は y を食べます
? 与えられる情報には間違った内容もあり、
順番に情報を適用し、矛盾してしまう情報の個数を求めよ
植物連鎖問題
78

? 考え方
? N * 3 で Union-Find 木を初期化し、
与えられた情報が矛盾していないか調べる
datastructure1/question3
植物連鎖回答
79

狠狠撸

データを工夫して记録するデータ构造

More Related Content

データを工夫して记録するデータ构造