酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年6月16日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html

平衡木 木を作り変えて性能のよい形に保つ 作り変えるための計算量が多すぎてもダメ AVL木 B木 ほどほどにバランスをとる ２分探索木の一種 多分木　(maybe treeではなく、multiway tree)

AVL木 どの頂点においても、 その左部分木と右部分木の高さの差が +1, 0, -1 のいずれかである２分探索木

この漸化式はFibonacci数列として有名 Fibonacchi数列 頂点数最少のAVL木の頂点数 この漸化式はFibonacci数列として有名 h=2

バランスが崩れて、AVL木でなくなった。 ( のノードの左部分木と右部分木) 17 9 21 5 13 19 23 3 7 11 15 1 を挿入すると… 17 9 21 5 13 19 23 3 7 11 15 バランスが崩れて、AVL木でなくなった。 ( のノードの左部分木と右部分木) 1 17

17 9 21 5 13 19 23 3 7 11 15 1 と を入れ替える（回転する）。 17 9 9 5 17 3 7 13 21 1 11 15 19 23

バランスが崩れて、 AVL木でなくなった。 91ページc) 17 9 21 5 13 19 23 3 7 11 15 17 9 21 23 13 11 5 7 3 19 10 を挿入すると… バランスが崩れて、 AVL木でなくなった。 15

バランスが崩れて、 AVL木でなくなった。 17 9 21 23 13 11 5 7 3 19 10 を挿入すると… バランスが崩れて、 AVL木でなくなった。 15 17 9 21 23 13 11 5 7 3 19 10 1回転してもダメ 15 17 9 21 23 13 11 5 7 3 19 10 15 を根に置くことにして、 ２回転します。

削除した結果の木が、 AVL木の条件を満たさない場合 削除の場合 通常の２分探索木として頂点を削除 削除した結果の木が、 AVL木の条件を満たさない場合 木の形が９０ページa)では一重回転 木の形が９１ページc)では二重回転 教科書９８ページにも、そう書いてある。 挿入にせよ削除にせよ、結果の木の形で 再構成の要・不要を判断する。ということ。

B木（B-tree） 二分木ではないが、探索用のｍ分木 いわゆる平衡木 順序木である B木を構成するためのルール 根から葉までの深さはどの葉についても同じである 各頂点（葉以外）の子の数は最大mである 各頂点（葉以外）の子の数は最小 である 　は切り上げを意味する記号である 根は例外で、最小2である

頂点の構造 頂点にはデータは置かない 探索キーだけをおく キーは枝をたどるときの境目

B木の探索 途中の頂点にはデータは入ってない 根から部分木を選択しながら下降する 葉に達したら探索は終了 入ってる値は部分枝の選択のためのキー値 データは葉の部分におかれている そうしない実装もある 根から部分木を選択しながら下降する 部分木の選択にはO(log m)必要 葉に達したら探索は終了 葉の値と一致すれば成功、そうでなければ失敗

B木の頂点に置く境界値 頂点に置かれる値は部分木選択に使われる 境界値の条件は次の２つを満たす 条件を満たす値は複数あるがどれでもいい 左に位置する部分木の最大値以上 右に位置する部分木の最小値以下 条件を満たす値は複数あるがどれでもいい 境界値 境界値の左部分木 境界値の右部分木

44を探索 3を探索 29を探索 7 31 7未満の数 7以上31未満の数 31以上の数 3 6 22 29 - 49 3 6 7 22 29 31 49 探索失敗 未満, less than, より小さい 以上, greater than or equal to 以下, less than or equal to

新しいデータ（子）を追加するとき 追加すべき位置（親の頂点）を決定します 親の頂点に空きがあるか調べます 空きがない場合は親の頂点を分割します 親の親の頂点から新たに枝を増やします 親が根である場合は、新たな根を親の親として増やします 子を頂点に追加します

データ（子）を削除するとき 削除すべきデータを探索し、削除します 親からの枝の本数が最少数を満たすかどうか調べます 最少数に満たない場合は隣の頂点と子を按分します 按分した結果最少数を満たせない場合は隣の頂点と併合します 親が根である場合に最少数２を割ったら、根を削除します

計算量の考察 キー値の比較を1回行うと候補は半減する ちょうど半分ずつ絞りこめばO(log N) 候補が半減する場合がもっとも効率が良い 半減するようにデータを保持する 例：平衡木を使う ちょうど半分ずつ絞りこめばO(log N) キーの比較という手法を使う限りはこれ以上探索の効率はよくならない。

アルゴリズムとデータ構造 演習 学生番号： 名前： ８ページ下の図から を削除します。 アルゴリズムとデータ構造　演習 学生番号：　　　　　　　　　　　　　　　　 　　　名前：　　　　　　　　　　　　　　　　 13 ８ページ下の図から を削除します。 15 9 17 5 11 21 3 7 10 19 23 AVL木としてバランスが取れなくなりました。どのノードの 左部分木と右部分木の高さが規定外なのでしょうか？ 回転操作により木をAVL木として再構成してください。