Ibaraki Univ. Dept of Electrical & Electronic Eng.

Presentation on theme: "Ibaraki Univ. Dept of Electrical & Electronic Eng."— Presentation transcript:

1 Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 Ibaraki Univ. Dept of Electrical & Electronic Eng. Keiichi MIYAJIMA

2 平衡2分探索木

3 平衡２分探索木 18 7 22 5 11 21 31 8 15 25 ９ これはＡＶＬ木ではない ２分探索木の中で以下の条件を満たしたもの
頂点ごとに各部分木の高さの差がたかだか１になるようにバランス(平衡)を保つもの（AVL木とも呼ばれる）。 18 7 22 5 11 21 31 8 15 25 ９ これはＡＶＬ木ではない

4 平衡２分探索木 18 7 5 22 11 21 31 8 15 25 これはＡＶＬ木ではない ９ ２分探索木の中で以下の条件を満たしたもの
頂点ごとに各部分木の高さの差がたかだか１になるようにバランス(平衡)を保つもの（AVL木とも呼ばれる）。 18 7 5 22 11 21 31 8 15 25 これはＡＶＬ木ではない ９

5 このような動作を「回転(Rotate)」と呼ぶ
平衡２分探索木 ２分探索木の中で以下の条件を満たしたもの 頂点ごとに各部分木の高さの差がたかだか１になるようにバランス(平衡)を保つもの（AVL木とも呼ばれる）。 18 8 22 7 11 21 31 5 ９ 15 25 このような動作を「回転(Rotate)」と呼ぶ

6 平衡２分探索木 「回転」の操作は説明するのは易しいがプログラムにすることは難しい 18 8 22 7 11 21 31 5 ９ 15 25

7 ２色木 ２分探索木の各辺に次ぎの３つの条件を満たすように赤か黒の色を塗ったもの。 外点に接続する辺の色は黒。
根から外点に至るどの路の上でも、赤い辺が連続することはない。 根から外点に至るどの路も、含む黒色の辺の数は同じ。

8 ２色木への挿入 挿入するとき、以下のような頂点を見つけたら・・・ 18 8 22

9 ２色木への挿入 挿入するとき、以下のような頂点を見つけたら・・・ 18 8 22 色を交換する

10 ２色木への挿入 以下のような連続する赤い辺がでた場合 18 8 22 7 11

11 ２色木への挿入 以下のような連続する赤い辺がでた場合 8 7 18 11 22

12 ２色木への挿入 以下のような連続する赤い辺がでた場合 18 8 22 7 11 10 13

13 ２色木への挿入 さらに、赤い辺が連続しているので、 18 22 11 8 7 10 13

14 ２色木への挿入 さらに、赤い辺が連続しているので、 11 8 18 7 13 10 22

15 本日のまとめ TCP/IPアプリケーション 平衡２分探索木 平衡２分探索木の定義 平衡２分探索木の探索、挿入
　平衡２分探索木 平衡２分探索木の定義 平衡２分探索木の探索、挿入 平衡２分探索木（２色木）の挿入については資料を配付する。

16 本日の課題 １．2色木のプログラムを作成し、 整数を上記の順で挿入したときの結果を図示せよ。
以下の課題について、プログラムを作成し、プログラムと実行結果をプリントアウトしたものを提出すること。 １．2色木のプログラムを作成し、 整数を上記の順で挿入したときの結果を図示せよ。 その際、先週の単純な2分探索木のプログラムの結果と比較できる形でプリントアウトすること。 ２分探索木の表示と印刷は先週の関数などを参考にせよ。

17 レポートの〆切と提出先 レポート提出先： E2棟（旧システム棟）６F606室（宮島教員室）前 レポートBOX レポート〆切：
6月16日火曜日　PM５：００頃