コンピュータ基礎演習ースタックー

コンピュータ基礎演習
ー高速ソートー
岩井儀雄
[email protected]
高速なソートアルゴリズム

整列アルゴリズムの処理速度


単純なアルゴリズム



比較回数と交換回数の大小
安定，プログラム容易，作業領域不要
バブル，選択，挿入ソート: O(n2)
高速なアルゴリズム




不安定，プログラム複雑，作業領域要
シェルソート：平均O(n1.25~n1.5)
クイックソート：平均O(nlogn)~最悪O(n2)
マージソート: O(nlogn) （安定）
シェルソート(Shell sort)


N 個のデータを整列
H←N/2, I←N/H


H組のI個のデータを挿入ソートする
H←H/2, I←N/H で H が 0 になるまで繰り返し
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
3
19
6
30
13
22
28
55
45
82
46
66
74
87
64
91
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
3
19
6
30
13
22
28
55
45
82
46
66
74
87
64
91
3
19
6
30
13
22
28
55
45
82
46
66
74
87
64
91
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
3
19
6
30
13
22
28
55
45
82
46
66
74
87
64
91
3
19
6
22
13
30
28
55
45
66
46
82
64
87
74
91
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
3
19
6
30
13
22
28
55
45
82
46
66
74
87
64
91
3
19
6
22
13
30
28
55
45
66
46
82
64
87
74
91
3
19
6
22
13
30
28
55
45
66
46
82
64
87
74
91
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソート
74
22
64
91
3
87
6
55
13
19
28
30
45
82
46
66
13
19
28
30
3
82
6
55
74
22
64
91
45
87
46
66
3
19
6
30
13
22
28
55
45
82
46
66
74
87
64
91
3
19
6
22
13
30
28
55
45
66
46
82
64
87
74
91
3
6
13
19
22
28
30
45
46
55
64
66
74
82
87
91
同一色内で挿入ソートを実行する
同一色内ではソートが完了していることに注目
シェルソートの実装（Ｃ言
語）
int greaterthan(DATATYPE a, DATATYPE b); /* 順序を定義する関数 */
void swap(DATATYPE *a, DATATYPE *b);
/* 値を交換する関数
*/
void shellsort( DATATYPE *A, size_t n) {
int i,j,inc;
inc = n/2;
while (inc > 0) {
for (i = inc; i<n; ++n) {
j = i-inc;
while (j > 0) /* 挿入ソートを実行する */
if (greaterthan(A[j],A[j+inc])) { /* 値交換，前方に進む */
swap( &A[j], &A[j+inc] ); j -= inc;
} else j = 0; /* ソート済みなのでwhile ループを抜ける */
}
inc /= 2;
}
} /* 要チェック(動作未確認) */
マージソート (merge sort)



外部記憶装置向けのソート
各要素をシーケンシャルにアクセスする
二つのソートされた列から一つのソートされた
列を作る（併合，merge）
マージソート(merge sort)
整列済
新しいソート済み列
A列
3
13
46
55
B列
30
45
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
A列
B列
30
13
46
55
45
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
13
A列
B列
30
45
46
55
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
13
30
A列
B列
45
46
55
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
13
30
45
A列
46
55
B列
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
13
30
45
46
55
A列
B列
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
13
30
45
46
55
A列
B列
74
87
先頭を大小比較し
小さなほうを取り出す
マージソート(merge sort)
整列済
新しいソート済み列
3
13
30
45
46
55
74
87
A列
B列
どちらかの列が空になったら
残りの列のデータをその順序で
コピーする
マージソート(merge sort)



データ列を真ん中で２つの部分列a,bに
分割する（データが一つしかなければ
整列済みなので戻る）
部分列a,bをそれぞれ整列を行う
整列済みの部分列a,bをマージする
マージソートの実装（Ｃ言
語）
#include <string.h>
int lessthan(DATATYPE a, DATATYPE b); /* 順序を定義する関数 a<b */
void copy(DATATYPE *a, DATATYPE *b); /* 値を代入する関数 a←b */
void mergesort(DATATYPE *A, int low, int high, DATATYPE *B) { /* Bは作業領域 */
int m,i,j,k;
for (i=low; i<=high; ++i) copy(&B[i],&A[i]); /* データをコピー */
if (low >= high) return; /* 要素が一つの場合は戻る */
m = (low+high)/2;
/* 列を２つに分割する位置を決める */
mergesort( B, low, m, A );
/* 前半部分のソート */
mergesort( B, m+1, high, A ); /* 後半部分のソート */
j = low; k = m+1; i=low;
while (j <= m && k <= high)
if (lessthan(A[j],A[k])) copy( &B[i++], &A[j++] );
else copy( &B[i++], &A[k++] );
while (j <= m) copy( &B[i++], &A[j++] );
while (k <= high) copy( &B[i++], &A[k++] );
}
マージソートの実行イメージ
整列前A
low=0
55
時間
55
55
13
13
3
3
分割
13
13
3
55
13
13
87
46
3
3
分割
45
45
3
併合
45
30
high=7
74
55
45
74
分割
87
87
74
30
併合
45
87
46
87
併合
46
46
30
30
併合
分割
30
46
55
分割
30
30
併合
74
46
13
併合
分割
74
3
併合
分割
45
45
55
46
74
87
74
87
マージソートの性質


安定な整列
時間計算量


空間作業量



常に O(nlogn)
整列する配列と同じ作業領域が必要
O(n)
もともと外部記憶装置用のソートアルゴリズムの
ため
クイックソート(quick sort)



高速なソートアルゴリズム
安定な整列ではない
Ｃ言語でもライブラリで用意されている
void
qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
クイックソート(quick sort)



データ列から枢軸(ピボット, Pivot)を選
ぶ
枢軸の値より，小さいもの，大きいも
のに分割する
分割されたそれぞれを整列する．
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
91
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
74
91
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
87
74
91
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
22
28
87
74
91
赤い矢印のところのデータとピボットを交換
赤い矢印がピボットを差し，
赤い矢印から左がピボットより小さい→再帰的に quick sort
赤い矢印から右がピボットより大きい→再帰的に quick sort
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
22
28
66
74
91
87
赤い矢印のところのデータとピボットを交換
赤い矢印がピボットを差し，
赤い矢印から左がピボットより小さい→再帰的に quick sort
赤い矢印から右がピボットより大きい→再帰的に quick sort
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
87
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
22
13
46
45
87
74
91
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
22
13
19
64
55
30
46
45
87
74
91
クイックソート(quick sort)
45
13
30
64
55
74
87
22
28
46
19
91
66
Pivot
66
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
22
13
19
28
55
30
46
45
64
87
74
87
91
クイックソート(quick sort)
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
22
13
19
28
55
30
46
45
64
Pivot
19
87
74
Pivot
64
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
22
13
19
28
55
30
46
45
64
Pivot
22
64
28
74
Pivot
19
13
87
55
30
46
45
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
45
13
30
64
55
19
46
22
28
66
74
91
87
Pivot
Pivot
28
22
13
19
28
55
30
46
45
64
Pivot
19
22
64
28
74
Pivot
19
13
87
55
30
46
45
64
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
22
13
19
28
55
30
46
45
64
Pivot
Pivot
19
13
19
Pivot
要素数１
なので終了
22
64
28
Pivot
要素数１
なので終了
74
55
30
46
45
64
Pivot
45
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
22
13
19
28
55
30
46
45
64
Pivot
Pivot
19
13
19
Pivot
要素数１
なので終了
22
64
28
55
30
46
45
64
Pivot
Pivot
要素数１
なので終了
28
74
45
46
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
22
13
19
28
55
30
46
45
64
Pivot
Pivot
19
13
19
Pivot
要素数１
なので終了
22
64
28
55
30
46
45
64
Pivot
Pivot
要素数１
なので終了
28
74
45
30
55
46
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
22
13
19
28
55
30
46
45
64
Pivot
Pivot
19
13
19
Pivot
要素数１
なので終了
22
64
28
55
30
46
45
64
Pivot
Pivot
要素数１
なので終了
28
74
45
30
45
46
55
87
Pivot
要素数１
なので終了
91
Pivot
要素数１
なので終了
クイックソート(quick sort)
13
19
Pivot
要素数１
なので終了
22
28
55
30
46
64
Pivot
Pivot
要素数１
なので終了
28
45
45
30
45
46
55
Pivot
30
Pivot
55
クイックソート(quick sort)
13
19
Pivot
要素数１
なので終了
22
28
55
30
46
45
30
45
46
55
Pivot
Pivot
30
28
64
Pivot
Pivot
要素数１
なので終了
28
45
55
46
クイックソート(quick sort)
13
19
Pivot
要素数１
なので終了
22
28
55
30
46
45
30
45
46
55
Pivot
Pivot
30
28
64
Pivot
Pivot
要素数１
なので終了
28
45
30
55
46
55
クイックソート(quick sort)
28
30
45
46
55
Pivot
Pivot
30
28
30
Pivot
要素数１
なので終了
55
46
55
Pivot
要素数１
なので終了
クイックソート(quick sort)
28
30
45
46
55
Pivot
Pivot
30
13
19
22
28
30
Pivot
要素数１
なので終了
55
45
46
55
Pivot
要素数１
なので終了
64
66
74
87
91
クイックソートの実装
（Ｃ言語）
#include <stdio.h>
int lessthan(DATATYPE a,DATATYPE b); /* 大小比較を行う関数 */
void copy(DATATYPE *a,DATATYPE *b);
/* 値のコピーを行う関数 */
void swap(DATATYPE *a,DATATYPE *b);
/* 値の交換を行う関数 */
int partition(DATATYPE *A,int l,int r) {
int i,j,t;
DATATYPE pivot;
i = l-1; j = r;
copy( &pivot, &A[r]); /* 右端をピボットとする */
for (;;) {
while (lessthan(A[++i],pivot)) ; /* 左側を進める(pivotより小さい) */
while (i < --j && lessthan(pivot,A[j])) ; /* 右側を進める(pivotより大きい)*/
if (i >= j) break; /* 両側からぶつかったらループを抜ける */
swap(&A[i],&A[j]); /* 値を交換する */
}
swap( &A[r], &A[i] ); /* pivot と交換する */
return i;
}
void quicksort(DATATYPE *A,int l,int r) {
int v;
if (l >= r) return;
v = partition( A, l, r ); /* v の位置を pivot として，データを左右に振り分け */
quicksort( A, l, v-1 ); /* 左部分列をソート */
quicksort( A, v+1, r ); /* 右部分列をソート */
}
クイックソートの性質

時間計算量


平均的に O(nlogn)
最悪 O(n2) （ピボットが端に来る場合）
コンピュータ基礎演習
ーハッシュ法ー
岩井儀雄
[email protected]
ハッシュ法 (hashing)



Hash: 切り刻む，細かに切るの意味
ハッシュ法とは，キーに一定時間の演
算Hを施して，データ格納のアドレスに
変換し，そのアドレスからデータを参
照するというキー・アドレス変換の技
法
目的のデータの探索時間が短縮可能
ハッシュ法

ハッシュ関数


ハッシュ値


キーの値ｘをデータのアドレス（通常は，
配列の添え字）へ変換する関数H
ハッシュ関数が返す値
ハッシュテーブル

データを格納する配列T
ハッシュ法

キーXを持つデータは，配列Tの要素
T[H(X)] に格納される．
ハッシュ関数の例
簡単なハッシュ関数の例）
int hash(char *s) {
int i= 0;
while (*s) i += *s++;
return i%100;
}
実行例
文字列
one
two
three
four
five
six
seven
eight
nine
ten
ハッシュ値
22
46
36
44
26
40
45
29
26
27
文字列中の全ての文字コードを加算
その結果の100で割った余りをハッシュ値とする
ハッシュ関数

実行例
文字列
one
two
three
four
five
six
seven
eight
nine
ten
ハッシュ値
22
46
36
44
26
40
45
29
26
27
欠点


異なる入力に対して同じハッ
シュ値を返すことがある（衝
突）
衝突に対する対処法

チェイン法(chaining)


同じハッシュ値を持つデータをリス
トでつなぐ方法
オープンアドレス法(open
addressing)

別のハッシュ関数を使って再度ハッ
シュする方法
チェイン法

ハッシュ表には連結リストへのポイン
タをいれ，データはポインタでつなぐ
ハッシュ表
[0]
AAA
A
[1]
[2]
C
…
DD
DDDD
[N]
NNN
N
AAAA
探索方法


ハッシュ値の計算
リストを線形探索
ハッシュ表
[0]
AAA
A
[1]
[2]
C
…
DD
DDDD
[N]
NNN
N
AAAA
探索方法

ハッシュ値の計算
AAAA の探索
ハッシュ表
H(AAAA)
[0]
AAA
A
[1]
[2]
C
…
DD
DDDD
[N]
NNN
N
AAAA
探索方法


ハッシュ値の計算
リストを線形探索
AAAA の探索
ハッシュ表
H(AAAA)
[0]
AAA
A
[1]
[2]
C
…
DD
DDDD
[N]
NNN
N
AAAA
探索方法


ハッシュ値の計算
リストを線形探索
AAAA の探索
ハッシュ表
H(AAAA)
[0]
AAA
A
[1]
[2]
C
…
DD
DDDD
[N]
NNN
N
AAAA
探索方法


ハッシュ値の計算
リストを線形探索
AAAA の探索
ハッシュ表
H(AAAA)
[0]
AAA
A
[1]
[2]
C
…
DD
DDDD
[N]
NNN
N
AAAA
データの追加・削除

連結リストにおける挿入削除と同じ処理


ハッシュ値を計算して追加・削除する連結リ
ストを決定する
その連結リストに対して，追加・削除を行う．
チェイン法の性質

探索の時間計算量


ハッシュ値の計算 O(1)
連結リストにおける線形探索 O(L)

リストの平均長L = N/ハッシュ表の大きさＢ

N << B  N / B < 1
N BN /B 1
N >> B  N / B  N
ハッシュ表がデータに比べて十分大きい場合→O(1)
ハッシュ表がデータに比べて大きくない場合→O(N)
チェイン法の性質

挿入の時間計算量



連結リストの先頭へのデータ挿入O(1)
キーの重複チェック O(L)
削除の時間計算量


連結リストからのデータ削除 O(1)
データの探索 O(L)
チェイン法の性質

良好な性能を維持するためには


連結リストが長くならないように十分大き
なハッシュ表を用意する
できるだけ均等に分布するハッシュ関数H
を用意する．
オープンアドレス法

衝突が発生したときに，ある手順に
従って別の位置にデータを格納する
（再ハッシュ）
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
A
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
A
[2]
[3]
[4]
[5]
[6]
[7]
[8]
B
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
A
[2]
[3]
[4]
[5]
B
[6]
[7]
[8]
C
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
A
[2]
[3]
[4]
[5]
B
[6]
[7]
[8]
C
D: 衝突再ハッシュH(x,1)=6
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
A
[2]
[3]
[4]
[5]
B
[6]
D
[7]
[8]
C
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
A
[2]
[3]
[4]
[5]
B
[6]
D
[7]
[8]
C
E: 衝突再ハッシュH(x,1)=7
再ハッシュの方法

例）k回目の再ハッシュ
H(x,k) = (H(x) + k) mod B
X
A
B
C
D
E
H(X)
→ 1
→ 5
→ 8
→ 5
→ 6
[0]
[1]
A
[2]
[3]
[4]
[5]
B
[6]
D
[7]
E
[8]
C
コンピュータ基礎演習
ー平衡木，AVL木ー
岩井儀雄
[email protected]
平衡木 (Balanced Tree)



木の高さが，高々log N程度の２分探索木
二分探索木において平均的にO(log N)の性能を出すことができる．
AVL木： (Adel’son -Vel’skii Landis)

２分探索木でかつ，全ての節において左部分木TLと右部分木TRの高さの差
H(TL)-H(TR)が１以内に収まらなければならない
c
右部分木
左部分木
a
d
高々1
b

x H(TL(x)) – H(TR(x))  1
AVL木


以下の制約によりN個の節を持つAVL木の高
さはO(log N)
探索を常にO(log N)で実行可能
c
右部分木
左部分木
a
d
高々1
b

x H(TL(x)) – H(TR(x))  1
AVL木の要素探索

通常の２分探索木と同様に実行できる
AVL木への要素の削除と挿入


挿入削除も基本的には２分探索木と同様
木のバランスが壊れたときに修正する処理
c
右部分木
左部分木
a
d
高々1
b

x H(TL(x)) – H(TR(x))  1
AVL木への挿入


要素を新しい位置に挿入するのは２分
探索木と同様
その結果，部分木によっては高さが１
増加するので，挿入位置から根に向
かって高さの調整作業を行う
AVL木の挿入(2)


修正の手順において，左の子vから親uへ上ってき
たとする（右の子の場合も対称的に扱う）
vを根とする部分木の高さが１増えた状態（そうで
なければ修正の必要なし）
節点xに関して，その左部分木TL(x)とTR(x)に関する
状態 S(x)を以下のように定める
S(x) =
L
E
R
H(TL(x)) > TR(x))
H(TL(x)) = TR(x))
H(TL(x)) < TR(x))
AVL木の挿入(3)

挿入前のS(u)→挿入後のS(u)

S(u)=R → S(u)=E


S(u)=E → S(u)=L


修正終了
uの親に移動して修正実行，根なら終了
S(u)=L → S(u)=L

uはAVL木の条件を満たさなくなるので修正が
必要（回転処理を行う）
AVL木の回転処理(1)

S(v)=Lの場合
u
S(v)=L
S(v)=Lなので
左の木の方が
１高い
v
β
α
S(u)=L
γ
AVL木の回転処理(2)

S(v)=Lの場合
S(v)=E
v
u
α
β
γ
AVL木の回転処理(3)

S(v)=Rの場合
S(v)=R
u
v
w S(w)=L or R
α
δ
β
γ
AVL木の回転処理(4)

S(v)=Rの場合
w
u
v
α
β
γ
δ
挿入実行例
L
2 を挿入
13
L
8
E
6
10
E
E
4
14
7
E
R
15
E
挿入実行例(2の挿入)
L
13
L
u 8
L
v 6
10
E
L
4
E
2
14
7
E
R
15
E
挿入実行例(回転処理)
13
v 6
4
2
14
u 8
7
15
10
AVL木の要素削除




要素の除去は２分探索木と同様に行う
その結果，高さの減少する部分木が存在すれば，
その部分木の根から上へ修正作業を加える
挿入の場合と同様に，左の子vからその親uへ上っ
てきたとする（右の子も対称的に扱える）
vを根とする部分木の高さが１減った状態にある
AVL木の要素削除（２）

挿入前のS(u)

S(u)=L → S(u)=E



S(u)=E → S(u)=R


左部分木の高さが１減ったためS(u)=E.
uの高さが１減少し，修正はuの親へと続ける．ただし，
uが根ならば終了する
修正終了
S(u)=R → S(u)=R

uはAVL木の条件を満たさなくなるので，修正が必要
（回転処理を行う）
AVL木の回転処理(1)

S(w)=Eの場合
u
S(u)=R
w
v
α
β
高さの差２
γ
S(w)=E
δ
AVL木の回転処理(2)

S(w)=Eの場合
w
S(u)=R
S(w)=L
u
v
α
β
γ
δ
AVL木の回転処理(3)

S(w)=Rの場合
u
S(u)=R
w
v
α
β
高さの差２
γ
S(w)=R
δ
AVL木の回転処理(4)

S(w)=Rの場合
w
S(u)=E
S(w)=E
u
v
α
β
γ
δ
AVL木の回転処理(5)

S(w)=Lの場合
u
S(u)=R
w
v
S(w)=L
z
α
β
高さの差２
ε
γ
δ
AVL木の回転処理(6)

S(w)=Lの場合
z
S(u)=E or L
S(z)=E
w S(w)=E or R
u
v
α
β
γ
δ
ε
AVL木の計算量

N個の節点を持つAVL木の高さはO(log N)
であるから，探索，挿入，要素削除（回
転処理を含む）は最悪時間計算量O(log
N)で可能
他の平衡木


木の高さをO(log N)に抑えると，操作あ
たりの計算量はO(log N)に抑えることが
できる
他の平衡木として

B木，B+木，2-3木などが用いられる
B木 (B-tree)

B木の条件





根は，葉であるか，あるいは2~m個の子を
持つ
内部の節はm/2~m個の子を持つ
根から全ての葉までの経路の長さが等しい
2-3木は m=1 のB木
補助記憶装置（ハードディスク等）に
適したデータ構造
Ｂ木

子へのポインタと
キーの並び（整列済）
m=5のB木の例
12
4
2
7
4
18
7
12
21
18
30
21
30
葉にはキーで引き出されるデータが付随するが省略
B木の探索

根から順次，内部節をたどって探索する．
k1
x < k1


k2
k3
k4
k 2  x < k 3
k 4  x
k 1  x < k 2
k 3  x < k 4
内部節では，キーが整列されているので，
２分探索を用いて子へのポインタを決定す
る
以降，葉に到達するまで繰り返し
B木への挿入



根から順次，内部節をたどって挿入位置を
探索する
挿入すべき位置に，要素を入れる余裕があ
れば，挿入する
そうでなければ，節を２つに分割して，そ
のどちらかの正しい位置に挿入．親の節は，
子が増えるので順次挿入を繰り返す
B木への挿入例

25 を挿入
12
4
2
7
4
18
7
12
21
18
30
21
30
B木への挿入例

25 を挿入
12
4
2
7
4
18
7
12
21
18
25
21
30
25
30
B木への挿入例

15 を挿入
12
4
2
7
4
18
7
12
21
18
25
21
30
25
30
B木への挿入例

15 を挿入
子が一杯なので
２つに分割する
12
4
2
7
4
18
7
12
21
18
25
21
30
25
30
B木への挿入例

15 を挿入
12
4
2
21
7
4
25
7
21
15
12
18
15
18
30
25
30
B木の削除



削除対象の要素位置を探索
削除したとき，節にm/2個以上残っていれば
そのまま終了
m/2以下の時


隣の節の子の数がm/2+1個以上であれば，その節
と子を半分ずつにする
そうでなければ，隣の節と併合する．併合すると，
親にとっては子が減るので，同様の処理を親に向
かって続ける
B木の削除例

18を削除
12
4
2
7
4
18
7
12
21
18
30
21
30
B木の削除例
12
4
2
7
4
21
7
12
30
21
30
B木の削除例

４を削除
12
7
2
21
7
12
30
21
30
B木の削除例

４を削除
12
7
2
21
7
12
併合
30
21
30
B木の削除例

４を削除
12
7
2
12
7
21
12
30
21
30
B木の削除例

7
2
４を削除
12
7
21
12
30
21
30

Download Report