静的データ/ 動的データ

アルゴリズムとデータ構造 補足資料 13-1

「 2 分探索木」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

静的データ / 動的データ

• 静的データ

–

–

→ 静的データ構造：配列

• 動的データ

–

–

→ 動的データ構造

順アクセスだけ： 線形リスト

効率的な探索、局所的なデータ管理：木構造

動的データ構造

• 線形リスト

–

• 木構造

–

• 部分木が高々2個の木構造： ２分木 binary tree

• 動的データ構造共通のオペレータ

–

• 生成先 ポインタ変数= (struct 構造体名 *)malloc(sizeof(struct 構造体名))

–

• free(削除先へのポインタ)

おまけ

• 木構造 tree structure

– 複数の「部分木」を持つ

• 部分木が高々2個の木構造： ２分木 binary tree

– どの部分木にも、自分自身（の節）を含まない – 親と子は 1:n の関係

• 網構造 network structure

– 複数の「参照先」を持つ

– 参照先の参照先の 参照先に自分自身を含んでよい …

解の候補

２分探索のイメージ： 解の候補を片側「半分」に絞り込む

解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む

n 件のデータ 解

解の候補 解の候補

解の候補

解の候補

！

log₂ n

２分探索： O( log n ) （オーダ ろぐエヌ） のア ルゴリズム

静的データの探索：２分探索

２分探索の特徴

• 探索の計算量（比較回数）は O(log n)

• あらかじめソートされている必要がある

– ソートの計算量：クイックソート O( n log n ) – ソートの計算量の方が重い

→ 最初に一度だけソートする。探索は頻繁 に行う。（固定的な名簿の探索に使え

る）

• つまり、静的データ（データの増減、追

加・削除が起こらない）を対象にしてい

る。

動的データを木構造を使って２分探索可能 にする方法： 探索木 (search tree)

• 任意の節点 N について、以下の条件を満 たしている木

1. (N の ) 左部分木中のすべての節点のキーが

、 N のキーよりも小さい

2. (N の ) 右部分木中のすべての節点のキーが

、 N のキーよりも大きい

動的データを木構造を使って２分探索可能 にする方法： 探索木 (search tree)

root

1

4

3 5

6 2

8 10

9 7

キーの値が小さい キーの値が大きい

探索木のオペレータ

• 探索木を探索する

• 探索木に節点を追加（挿入）する

• 探索木から節点を削除する

探索木 (search tree)

root

1

4

3 5

6 2

8 10

9 7

キーの値が小さい キーの値が大きい

8 を探せ！

探索木 (search tree)

root

1

4

3 5

6 2

8 10

9 7

キーの値が小さい キーの値が大きい

8 を探せ！

根から始めて

8 は左？右？

→ 右

探索木 (search tree)

root

1

4

3 5

6 2

8 10

9 7

キーの値が小さい キーの値が大きい

8 を探せ！

根から始めて

8 は左？右？

→ 左

探索木 (search tree)

root

1

4

3 5

6 2

8 10

9 7

キーの値が小さい キーの値が大きい

8 を探せ！

根から始めて

発見！ O(log n)

探索木のオペレータ

• 探索木を探索する

• 探索木に節点を追加（挿入）する

• 探索木から節点を削除する