データ構造と アルゴリズム第10回 知能情報学メジャー 和田俊和
４全順序集合とヒープ，2分探索木，AVL木 4.1 全順序集合と適用される操作 4.2 ヒープ 4.3 ２分探索木 4.4 AVL木
4.4 AVL木 Georgy Adelson-Velsky Evgenii Landis 4.4.1 AVL木とその再構成 すべての節点において，左部分木の高さー右部 分木の高さ（＝平衡係数）が[-1,1]の範囲内で ある2分探索木． （ただし，空の木の高さは−１と定義する．）
4.4.1 AVL木とその再構成 AVL木とAVL木ではない木の例
4.4.1 AVL木とその再構成 2分木作成途中，データ追加によりバランスを 崩す２つのケース
4.4.1 AVL木とその再構成 (a)のケースの木の変形（1重回転）
4.4.1 AVL木とその再構成 (b)のケースの木の変形（2重回転）
4.4.1 AVL木とその再構成 𝑇 3 の節点削除により，バランスが崩れる場合 １重回転 ２重回転
4.4.2 AVL木における時間計算量 1重回転，2重回転の1回の計算量は𝑂(1) これらは最大でも木の高さ分の回数しか実行さ れない． したがって，平均時間計算量は𝑂( log 𝑛 ) AVL木の高さの最大値は，𝑂 log 𝑛 したがって，最悪時間計算量も𝑂( log 𝑛 )
例題 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 平均探査回数 (1+2+3+4+5+12)/7=27/7=3.86回 平均探査回数 (1+4+12)/7=17/7=2.43 回
演習課題 これらを作成 途中に，再平 衡化を行って， AVL木にしな さい．作成途 中で施した回 転の種類もそ のつど明記し なさい． 20,95,35,50,80,75 演習課題 35,95,75,20,80,50 これらを作成 途中に，再平 衡化を行って， AVL木にしな さい．作成途 中で施した回 転の種類もそ のつど明記し なさい．