アルゴリズムとデータ構造(2)
1

もくじ
第二回

アルゴリズムと密接に関係するデータ構造
木構造
グラフ構造
ハッシュテーブル
演習
2

木構造
3

木構造

次々に枝分かれしていくデータ構造
各ノード(データ)が関連するノードへのポインタを持つ

4

木構造

親ノード: あるノードのすぐ上のノード
子ノード: あるノードのすぐ下のノード
ルートノード: 親ノードを持たないノード
リーフノード: 子ノードを持たないノード
ルートノード以外のノードは必ず親を1つだ
け持つ
5

木構造
用途

で HTML を扱う際のドキュメントツリー は木構造
ディレクトリ構造など、コンピュータには木構造になっている概念が結構あったりする
事前に個数が分からないデータのソート (後述)
JavaScript6

二分探索木 (BST)

各ノードが最大で2つの子を持ち、それらのデータが左子孫の値 ≦ 親の値 ≦ 右子孫の値のような順序になっている木構造のこと。

7

二分探索木の各種操作格納しているデータ数を n とする。
データの追加: O(log n)
データの検索: O(log n)全データ列挙: O(n)全体的に優秀8

二分探索木へのデータ追加

右図の木構造に「4」を追加する場合
ルートノードである 5 から探索開始
4 < 5 なので、5 の左子ノードに追加したい→ 既存の子である 1 に注目する
1 < 4 なので、1 の右子ノードに追加したい→ 既存の子である 3 に注目する
3 < 4 なので、3 の右子ノードに追加したい→ 子がいないので、ここに追加する

9

二分探索木へのデータ追加
追加アルゴリズムの問題点

データを小さいほうから順に追加していった場合、延々と木が右に伸びていくことになる。
このような構造になるとデータの追加と検索の計算効率が悪くなってしまい、最悪で O(n) になる。

10

二分探索木の検索

データ内に4が存在するか検索する

ルートノードである 5 から処理開始
4 < 5 なので左子ノードを見る
4 > 1 なので右子ノードを見る
4 > 3 なので右子ノードを見る
3 の右子ノードがないので、 4 が存在しないことが分かる
11

二分探索木の全データ列挙
ルートノードである 5 から処理開始
注目しているノードの左子ノードのデータを再帰的に列挙する
注目しているノードのデータを出力する
注目しているノードの右子ノードのデータを再帰的に列挙する
この手順で、データが昇順に列挙される。

12

二分探索木の表現最大サイズが分かっていれば、二分探索木は単なる配列に次のルールを設けることで表現できる。
1 番目の要素をルートとする
n 番目の要素は 2n および 2n + 1番目の要素を子とする
13

二分探索木の発展形B

木 (びーき), B+木, B*木

ノードが m 個のデータと (m + 1) 個の子ノードを持つようにしたもの。データベースのインデックスの保存に使われている。
1

赤黒木

二分探索木の「データの追加順によって計算速度が落ちる」問題点を改善したもの
14グラフ構造15グラフ構造木構造に似ているが、親子のような概念がなくループを許したデータ構造
扱いが難しいので、ぶっちゃけあまり使わない

16グラフ構造の表現方法
隣接リスト

各ノードが「自身とエッジで繋がっているノード」へのポインタを持つ

隣接行列

ノード数 × ノード数 サイズの2次元配列を用意し、各要素に「行と列で表されるノード同士が繋がっているか」を示す値を格納する
17

有向グラフエッジに向きがある。

18

グラフ構造の用途
マップ同士の繋がり

これは「グラフ構造が使いたい」わけじゃなくて「なんか知らんけどグラフ構造になったわ」って感じ

19グラフ構造の用途

正直「グラフ構造を使えば問題が解決できる！」って場面はあまりない…
実装も複雑になりやすいので、可能なら木構造などを使おう

20ハッシュテーブル21

ハッシュテーブルの map 、C#の Dictionary で使われる構造 (Javaは知らん)
自然数以外のインデックスを使ってデータを管理するための構造Go

22

ハッシュテーブル

内部的に配列を持っていて、キーから配列のインデックスに変換する仕組み(ハッシュ関数)を使ってアクセスする。

23

ハッシュ関数 / ハッシュ値

様々な型の値を、別の共通した型 (多くの場合は整数) に変換する関数・変換後の値のこと。
C# なら GetHashCode() メソッドがこれに対応する。
Go にはあらゆる型から共通のハッシュ値を用意する方法はない。
ハッシュ値は偏りがないようにする必要がある。標準機能として用意されている場合はこれを満たすように実装されている。
24

ハッシュテーブル

キーから配列インデックスへの変換

キーのハッシュ値をとり、配列の長さで割った余りをインデックスとする

25

ハッシュテーブル

キーから配列インデックスへの変換

ハッシュ値が重複している場合、次のインデックスにデータを保存するか、連結リストにして後ろにデータを繋げる。

26

ハッシュテーブルの実装例
type Map struct {| func (m *Map) Add(key string, value interface{}) {Buckets []*Bucket|
var hash = m.GetHash(key)Count int|
var bucket = &Bucket{hash, key, value}
GetHash func(string) int |if m.Count >= len(m.Buckets) {}|m.Extend() //O(n)|}|var index = hash % len(m.Buckets)
type Bucket struct {|for n.Buckets[index] != nil {Hash int|index++
Key string|}
Value interface{}|n.Buckets[index] = bucket}
| }

配列の拡張

27

ハッシュテーブルの操作

データの追加: O(1)
データの検索: O(1)
データの削除: O(1)全データ列挙: O(n) であることが多い(実装による)キーによるアクセスを、配列のインデックスと同じ感覚で使っていける28ハッシュテーブルの豆知識
配列長の工夫

ハッシュ値の重複はできるだけ起こしたくないので、配列の長さを素数にすることで剰余が重複しにくくなるようにすることが多い。

容量の拡充

配列にデータが収まりきらなくなったら、新しい配列を用意して全データを入れ直す。元の配列の長さの2倍より少し大きい素数を使うことが多い。この操作は O(n) である。
29

演習
30

演習

二分探索木のデータ tree から、 min ≦ x ≦ max の範囲にある値を昇順で取得するコードを実装してみましょう。
func (t *Tree) GetRange(min, max int) { /* ... */ }public class Tree{public IEnumerable<int> GetRange(int min, int max) { /* ... */ }}

31

演習

二分探索木おさらい
node.Left.Value ≦ node.Value ≦ node.Right.Value

32

おわりに

書籍紹介
『アルゴリズムとデータ構造』

競技プログラミング経験が豊富な著者が「アルゴリズムを自分の道具にしたい」という読者に向けて執筆。
この講義に含まれるデータ構造やアルゴリズムもだいたい載っている。
33