データ構造と
アルゴリズム
第十回
知能情報学部
知能情報学科
新田直也
二分探索木の性質（復習）
節xのkeyは，節xの左部分木に含まれるkeyより大きい．
節xのkeyは，節xの右部分木に含まれるkeyより小さい．
13
3
1
20
4
14
8
21
18
25
二分探索木による探索（復習）
二分探索と同様．
14 (key)?
13
14 (key)<
3
1
<14 (key)
4
14
8
20
=14 (key)
18
21
25
二分探索木への登録（復習）
登録位置は探索と同じアルゴリズムで見つけれる．
4 (key)<
3
4
<19 (key)
19 (key)<
<4 (key)
1 4 (key)<
13
6
14
8
20
<19 (key)
18
21
<19 (key)
19
25
二分探索木からの削除（復習）
13を削除したい場合．
13
3
1
20
6
14
8
21
18
25
→右部分木の最小値か左部分木の最大値を持っ
てくればよい．
二分探索木の欠点
探索アルゴリズムの時間計算量が木の形に依存．
4
1
1
2
6
2
3
5
7
3
4
→最良の場合(完全二分木)
O(log n)
5
6
→最悪の場合
O(n)
7
高速化の指針
どんな順番で登録しても完全二分木になるように，
登録アルゴリズムを修正する．
4
1
1
2
6
2
3
5
7
3
4
5
6
7
平衡木
平衡木： 葉までの距離（深さ）がバランスしている木．
AVL木，B木などがある．
探索，登録，削除の全計算量の最悪オーダが
O(log n) になる．
AVL木
AVL木： (Adel’son, Vel’skii, Landis, ‘62)
すべての節において，右部分木と左部分木の高さ
の差が1以内に収まる二分探索木．
13
3
1
20
4
14
8
21
18
25
AVL木による探索
二分探索木の場合とまったく同じ．
14 (key)?
13
14 (key)<
3
1
<14 (key)
4
14
8
20
=14 (key)
18
21
25
AVL木への登録
そのまま登録したのでは，AVL木になるとは限らない．
→たとえば9を二分探索木と同様に登録すると…
13
3
20
6
1
14
8
21
18
差が2
9
25
AVL木の回転
登録した後，バランスがとれるように木を変形する．
13
3
1
20
6
14
8
21
18
9
25
1重回転（1）
以下のようにxを追加した場合．
A
B
高さh
高さh
差が1
x
差が1
1重回転（2）
Bを親にすればよい．
B
A
高さh
高さh
x
差は0
2重回転（1）
以下のようにxを追加した場合．
A
B
高さh
高さh
差が1
x
差が1
2重回転（2）
Bを親にしても解決しない．
B
A
高さh
高さh
差が2
x
2重回転（3）
挿入した場所に（もっと）近い節を親にする．
A
B
高さh
高さh
差が1
x
差が1
2重回転（4）
Cを親にすると…
A
B
C
高さh
高さh
差が2
x
2重回転（4）
AVL木になる．
C
B
A
高さh
高さh
x
差が0
回転操作
挿入後の操作は1重回転と2重回転だけで十分．
（右部分木に追加された場合は左右対称にする．）
A
A
B
B
x
C
x
回転操作を行う位置（1）
どの節を中心に回転操作を行えばよいか?
1
2
2
2
2
1
回転操作を行う位置（2）
回転位置が不適切だと…
1
2
2
2
2
1
回転操作を行う位置（3）
差が解消されない
1
2
2
1
回転操作を行う位置（4）
適切な回転位置なら…
1
2
2
2
2
1
回転操作を行う位置（5）
1回の回転で差が解消
1
1
1
適切な回転位置
左右の差が2になる最も下の位置
回転前は追加した頂点へのパスが最も長い．
回転によってそのパスは1つ短くなる．
0
1
2
1
2
2
1
1
1
左右の差の計算
パス上の全頂点で左右の差を計算すると，O(n)
毎回，最初から計算し直す必要はない．
→左右の差を各頂点に記憶させればよい．
0
1
2
1
2
2
1
1
1
AVL木構造体
各頂点を以下の構造体で表す．
struct AVLTree {
int key;
int data;
int balance;
// 左右部分木の高さの差(1,0,-1)
struct AVLTree *left; // 左部分木へのポインタ
struct AVLTree *right; // 右部分木へのポインタ
};
登録アルゴリズム
1.
2.
3.
4.
5.
二分探索木と同様に追加する．
追加したパスを逆向きに辿り，
最初に左右の差が2になる位置を求める．
2.で求めた位置で回転を行う．
パスをさらに逆向きに辿り，
左右の差の値を更新する．
根まで戻ったら終わり．
0
1
2
1
2
2
1
1
1
登録アルゴリズムの最悪計算量
1.
2.
3.
4.
5.
二分探索木と同様に追加する．
追加したパスを逆向きに辿り，
最初に左右の差が2になる位置を求める．
2.で求めた位置で回転を行う．
パスをさらに逆向きに辿り，
左右の差の値を更新する．
根まで戻ったら終わり．
O(log n)
O(log n)
O(1)
O(log n)
時間計算量のまとめ
時間計算量のまとめ登録
探索
削除
線形探索法
(最悪・平均)
O(1)
O(n)
O(n)
二分探索法
(最悪・平均)
二分探索木
(最悪)
O(n)
O(log n)
O(n)
O(n)
O(n)
O(n)
二分探索木
(平均)
AVL木探索
(最悪)
O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
© Copyright 2024 ExpyDoc
