データ構造と アルゴリズム第10回 知能情報学メジャー 和田俊和.

Presentation on theme: "データ構造と アルゴリズム第10回 知能情報学メジャー 和田俊和."— Presentation transcript:

1 データ構造と アルゴリズム第10回 知能情報学メジャー 和田俊和

2 ４全順序集合とヒープ，2分探索木，AVL木 4.1 全順序集合と適用される操作 4.2 ヒープ 4.3 ２分探索木 4.4 AVL木

3 4.4　AVL木 Georgy Adelson-Velsky Evgenii Landis 4.4.1 AVL木とその再構成 すべての節点において，左部分木の高さー右部 分木の高さ（＝平衡係数）が[-1,1]の範囲内で ある2分探索木． （ただし，空の木の高さは−１と定義する．）

4 4.4.1　AVL木とその再構成 AVL木とAVL木ではない木の例

5 4.4.1　AVL木とその再構成 2分木作成途中，データ追加によりバランスを 崩す２つのケース

6 4.4.1　AVL木とその再構成 (a)のケースの木の変形（1重回転）

7 4.4.1　AVL木とその再構成 (b)のケースの木の変形（2重回転）

8 4.4.1　AVL木とその再構成 𝑇 3 の節点削除により，バランスが崩れる場合 １重回転 ２重回転

9 4.4.2 AVL木における時間計算量 1重回転，2重回転の1回の計算量は𝑂(1) これらは最大でも木の高さ分の回数しか実行さ れない．
したがって，平均時間計算量は𝑂( log 𝑛 ) AVL木の高さの最大値は，𝑂 log 𝑛 したがって，最悪時間計算量も𝑂( log 𝑛 )

10 例題 28, 2, 21, 14, 17, 15, 18 というデータを順に与え たときに出来上がる二分探索木と，平衡が崩れ た際に再平衡化を行って作成したAVL木を図示 し，成功探索時の平均探査回数をそれぞれ求め なさい． 28 28 21 21 17 2重回転 1重回転 2重回転 2 2 2 28 28 14 14 21 21 21 14 14 2 15 28 2 17 18 17 17 15 15 18 平均探査回数　( )/7=27/7=3.86回 平均探査回数　(1+4+12)/7=17/7=2.43　　回

11 演習課題 これらを作成 途中に，再平 衡化を行って， AVL木にしな さい．作成途 中で施した回 転の種類もそ のつど明記し なさい．
20,95,35,50,80,75 演習課題 35,95,75,20,80,50 これらを作成 途中に，再平 衡化を行って， AVL木にしな さい．作成途 中で施した回 転の種類もそ のつど明記し なさい．