アルゴリズムとデータ構造 補足資料13-1 「2分探索木」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志 静的データ / 動的データ • 静的データ – あらかじめ、データの全量がわかっている – データの追加・削除がない →静的データ構造：配列 • 動的データ – データの追加・削除がある – したがって、データの全量もわからない（増減する） →動的データ構造 順アクセスだけ： 線形リスト 効率的な探索、局所的なデータ管理：木構造 動的データ構造 • 線形リスト – 次の項目への「ポインタ」 • 木構造 – 複数の「部分木」を持つ • 部分木が高々2個の木構造： ２分木 binary tree • 動的データ構造共通のオペレータ – 要素の生成（追加） • 生成先 ポインタ変数= (struct 構造体名 *)malloc(sizeof(struct 構造体名)) – 要素の削除 • free(削除先へのポインタ) おまけ • 木構造 tree structure – 複数の「部分木」を持つ • 部分木が高々2個の木構造： ２分木 binary tree – どの部分木にも、自分自身（の節）を含まない – 親と子は1:nの関係 • 網構造 network structure – 複数の「参照先」を持つ – 参照先の参照先の…参照先に自分自身を含んでよい 静的データの探索：２分探索 解の方針：「区間」と「中央」を決めて、「中央」より「右」、「左」のどちらかに絞り込む ２分探索のイメージ： 解の候補を片側「半分」に絞り込む 解 n件のデータ 解の候補 解の候補 解の候補 解の候補 解の 候補 ！ ろぐエヌ） のアルゴリズム ２分探索： O( log n ) （オーダ log2 n ２分探索の特徴 • 探索の計算量（比較回数）はO(log n) • あらかじめソートされている必要がある – ソートの計算量：クイックソート O( n log n ) – ソートの計算量の方が重い → 最初に一度だけソートする。探索は頻繁に行 う。（固定的な名簿の探索に使える） • つまり、静的データ（データの増減、追加・削 除が起こらない）を対象にしている。 動的データを木構造を使って２分探索 可能にする方法： 探索木(search tree) • 任意の節点Nについて、以下の条件を満たし ている木 1. (Nの)左部分木中のすべての節点のキーが、N のキーよりも小さい 2. (Nの)右部分木中のすべての節点のキーが、N のキーよりも大きい 動的データを木構造を使って２分探索 可能にする方法： 探索木(search tree) root 7 2 9 1 6 8 10 4 3 キーの値が小さい 5 キーの値が大きい 探索木のオペレータ • 探索木を探索する • 探索木に節点を追加（挿入）する • 探索木から節点を削除する 探索木(search tree) 8を探せ！ root 7 2 9 1 6 8 10 4 3 キーの値が小さい 5 キーの値が大きい 探索木(search tree) 8を探せ！ root 根から始めて 7 2 8は左？右？ → 右 1 6 8 9 10 4 3 キーの値が小さい 5 キーの値が大きい 探索木(search tree) 8を探せ！ root 根から始めて 7 2 8は左？右？ → 左 1 6 8 9 10 4 3 キーの値が小さい 5 キーの値が大きい 探索木(search tree) 8を探せ！ root 根から始めて 7 2 9 1 6 8 10 4 発見！ O(log n) 3 キーの値が小さい 5 キーの値が大きい 探索木のオペレータ • 探索木を探索する • 探索木に節点を追加（挿入）する • 探索木から節点を削除する
© Copyright 2024 ExpyDoc
