Microsoft PowerPoint - algo ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - algo ppt [互換モード]"

たかよしあわび
5 years ago
Views:

1 平衡木アルゴリズム概論 - 探索 (2)- 安本慶一 yasumoto[at]is.naist.jp 二分探索木高さがデータを挿入削除する順番による挿入削除は平均 O(log n) だが, 最悪 O(n) 木の高さをできるだけ低く保ちたい平衡木 (balanced tree) データを更新する際に形を変形して高さが log 2 n 程度に収まるようにした木木の変形に要する時間を log 2 n にできれば高速 VL 木木 2 二分探索木による探索の計算量木の形によって大きく変わる ( 例 : 7 要素の場合 ) VL 木 ( 平衡木 ) del son-vel skii and Landis Tree どの頂点においても, その左部分木の高さと右部分木の高さの差が 1 以下 (±1 か 0) であるような二分探索木完全二分木計算量 : O(log n) 計算量の平均は O(log n) 挿入の計算量は探索と同じ最悪の場合計算量 : O(n) 3 高さ 3 高さ 2 4

2 VL 木 ( 平衡木 ) VL 木でない例 del son-vel skii and Landis Tree どの頂点においても, その左部分木の高さと右部分木の高さの差が 1 以下 (±1 か 0) であるような二分探索木高さ 1 高さ 2 高さ 1 5 高さ 3 完全二分木はどうか? 6 VL 木でない例 VL 木の高さ高さの最小値高さ 3 高さ 2 Fibonacci 数列 VL 木が完全二分木 ( 頂点数 :n) のとき O(log n) 高さの最大値同じ高さの VL 木のうち頂点数が最小のときどの頂点でも左右の木の高さが 1 異なるとき高さの VL 木の最小の頂点数を N とすると, 左部分木の頂点数を N -1, 右部分木の頂点数を N -2 とする N = N 1 + N 2 + 1, N0 = 1, N1 = 2 N = (( ) ( ) 2 ) 1 7 = O(log N ) 最も頂点数が少ない VL 木の例 8

3 VL 木における挿入削除基本的な手順 ( ステップ1) 新しい頂点を挿入, または頂点を削除 (2 分探索木の時と同様 ) ( ステップ2) VL 木でなくなれば木を再構成 VL 木でなくなる場合左部分木の高さ = 右部分木の高さ +1 のときに左部分木に挿入した場合右についても同様 VL 木の再構成簡単のため左部分木が高い場合を考える左部分木の左右どちらの部分木に挿入するかによって次の二つのケースに分けて考える Y Y 左部分木右部分木 9 ase1 に挿入された場合 ase2 Y に挿入された場合 10 ase 1: 1 重回転 ase 2: 2 重回転基本操作を根に移動してをの右の子に Y をの子に基本操作まず前準備として Y の子を Y 1 と Y 2 とする Y 1 回目 Y Y Y 1 Y 2 ase1 に挿入された場合 ase2 Y に挿入された場合 11 12

4 ase 2: 2 重回転基本操作をのレベルに移動し, をの左の子に, の左の子はの右の子へ移動を根に, をの右の子に,Y 2 をの左の子に ase 2: 2 重回転基本操作をのレベルに移動し, をの左の子に, の左の子はの右の子へ移動を根に, をの右の子に,Y 2 をの左の子に 1 回目 2 回目 Y 2 Y 2 Y 1 Y 2 Y 1 Y 2 Y 1 13 Y 1 14 下のVL 木に対して ()~(F) の各操作を行うとどうなるか示せ挿入の計算量根から葉に向かって挿入箇所を決定頂点を挿入した箇所から根に向かって必要なら 1 重回転あるいは 2 重回転その頂点を根とする部分木の高さが増加したかどうかを親に報告計算量 : すべて O(log n) 削除についても同様 ()10の挿入 () 3の削除 () 1の削除 (D)4の挿入 (E)8の削除 (F) 6の挿入 15 16

5 VL 木のまとめ探索挿入削除の計算量最悪時 : O(log n) ランダムデータによる実験結果挿入時の回転操作全挿入回数の 47% 1 重回転か2 重回転かはほぼ同確率削除時の回転操作全削除回数の 21% 木以下の制約を満たす m 分木各頂点 ( 葉以外 ) の子供の数の最大は m 各頂点 ( 葉以外 ) の子供の数の最小は m / 2 根の子供の数の最小は2 根から葉までの深さはどの葉についても同じ例 : m =5 のとき m/2 以上の最小の整数 ( 切り上げ ) 十分実用的なアルゴリズム木の例 m=3 の場合 18 各頂点は,m-1 個のキー ( とレコード ) を持つ葉以外の頂点は隣り合う二つの枝の境目を示すキー値を持つ木の例 m=4 の場合子へのポインタキーを含むデータ ( レコード ) 木の高さ : 根ノードから葉ノードまでのパスの長さバランス木なので根から葉へのパスの長さは一定

6 木の探索木への挿入必ず葉になる葉以外の頂点では二分探索と同様の方法でどの子を選択するかを定める例 : 探索キー 15, m=5 のとき 1. lo=1, i=4, mid= <20 より i=1, lo=1, mid= >10 より i=1, lo=2 4. lo>i より探索終了 5. 2 番目の子を探索する挿入 STEP1: 新しいデータの挿入位置 ( 頂点 ) を決める STEP2 : 以下で場合分け頂点のデータの数が m-1 未満なら, 普通に登録頂点のデータの数が m-1 の時 ( あふれる時 ) は, 木を再構成隣に新たに頂点を作成基準となるキーを選び, データ ( 挿入データを含む ) を基準キーとの大小関係で分割親に基準となったキーを追加 ( あふれるときは再帰的に処理 ) 基準キー :3 1 6 を選択 m=4 22 m=3 の木において 18,5,25,33,28,10,22,13,16,7 と, 入力があった場合に木の変化を示せ m=3 の木において 18,5,25,33,28,10,22,13,16,7 と, 入力があった場合に木の変化を示せ

7 + 木データが入っているのは葉のみ葉以外の頂点には隣り合う二つの枝の境目を示すキーの値が入っている ( できるだけ右側の部分木の最小値を使う ) 木を改良し, より一般的にしたのが + 木木の探索必ず一番下の葉まで降りる葉以外の頂点では二分探索と同様の方法でどの子を選択するかを定める例. 探索キー 15, m=5 のとき 1. lo=1, i=4, mid= <20 より i=1, lo=1, mid= >10 より i=1, lo=2 4. lo>i より探索終了 5. 2 番目の子を探索する木のメリット HDD のような 2 次記憶装置で利用するときに有効アクセスの回数が同じならば, 少量のデータを読むのも, ある程度まとまった量 ( 大きすぎるのはもちろんダメ ) を読むのも, ほとんどアクセス時間は変わらない 2 分木よりも,m 分木のようにまとまった量をブロックで持つほうが得レコードを木の葉だけにおくのは, できるだけmを大きくするため m=4 の + 木において 18,5,25,33,28,10,22,13,16,7 と, 入力があった場合に + 木の変化を示せ

8 m=4 の + 木において 18,5,25,33,28,10,22,13,16,7 と, 入力があった場合に + 木の変化を示せまとめ VL 木どの頂点でも, 左部分木と右部分木の高さの差が 1 以下の 2 分探索木挿入削除時に木の高さを調整 (1 重回転,2 重回転 ) 探索挿入削除の最悪時計算量 : O(log n) 木 (+ 木 ) 根から葉までの深さはどの葉に対しても同じ m 分木 mを大きくすることで木の高さ ( 探索回数 ) を小さくできる 2 次記憶装置で利用するのに有効 29 30

Microsoft PowerPoint - 7.pptx

Microsoft PowerPoint - 7.pptx 7. 木構造 7-1. データ構造としての木グラフ理論での木の定義根付き木 7-2.2 分探索木 7-3. 高度な木 ( 平衡木 ) AVL 木 B 木 1 7-1 1. データ構造としての木 2 木構造木構造を表すデータ構造の一つとしてヒープがあるしかしヒープでは配列を用いプではるため要素数で木の形状が一通りに決定してしまったここでは再帰的なデータ構造を用いることによりより柔軟な木構造が構築可能なより柔軟な木構造が構築可能なことを見ていく