1. No category

情報システム基礎論２：第 4 回 (担当： 古賀)
データ探索：SPLAY 木
2014 年 5 月 13 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
データベース
1
データベースは大量のデータ (record と呼ばれる) を保持する。各データは
< key, attribute >
という構造であり、異なるデータは異なる key を持つ。つまり、key によってデータを一意に特定できる。
no.
key
attribute
1
2
n
• S: データベース
• データ i: key i を持つデータ
データベースに対する操作
2
データベースからデータを検索する「検索」とデータベースの内容を変更する「更新」がある。
2.1
検索操作
• access(k)： データ k を S から検索。k が見つかればそのデータを返し、見つからないければ null を
返す。
2.2
更新操作
• 挿入操作 insert(k): データ k を S に挿入。k を検索して既登録でないことを確認後に挿入。
• 削除操作 delete(k): データ k を S から削除。k を検索して削除対象データを決定後に削除。
最初はデータベース S は空。データの挿入・削除を繰り返して S が構築される。
1
13
9
15
7
図 1: 2 分探索木
データ構造
3
データベースを実現するデータ構造により操作の処理速度は変わる。
• n: S に登録されたデータ数
線形リストでは、access は平均で
スト走査が必要。
n
2
回のリスト走査が必要である。insert は n 回、delete は平均
n
2
回のリ
単純な 2 分探索木
4
閉路のないグラフを木と呼ぶ。木は根ノードを最上層とした階層構造を持ち、各ノードは親ノードと子
ノードを持つ。正確には
• 根ノードでないノードは親ノードを 1 つもつ
• 葉ノードでないノードは子ノードを 1 つ以上もつ
木で各ノードの子の数が高々2 であるものを 2 分木と呼ぶ。
Definition 1 (2 分探索木) 2 分木において以下の条件でデータを格納したもの。
条件: あるノード i がデータ k を格納しているとする。この時、
• ノード i の左部分木には k より小さいデータが格納される。
• ノード i の右部分木には k より大きいデータが格納される。
4.1
データ検索
木の根からスタートして木を降りながらデータ検索を行う。例えばデータ k を探す場合、
Step 1: k と木のノードに格納されたデータ (i とする) との比較を行う。k = i であれば検索完了。そうで
ない場合は Step 2 へ Step 2: 木を降りる。
2
• if k < i であれば木を左下にたどる。
• if k > i であれば木を右下にたどる。
葉ノードに到達し，それ以上降りれない場合は「k が S に含まれていない」(検索失敗)。そうでなければ
Step 1 に戻る。
access(k) の実行時間： k を格納するノードの根からの深さで決まる。
• 2 分探索木が完全にバランスしていたら、access 操作の実行時間はせいぜい O(log n)。
• 逆にバランスがとれていない木では access 操作の実行時間は最悪で O(n)。
ここで「バランス」とは左部分木と右部分木の高さが違わないという意味。
4.2
データ挿入
データ k の挿入: k に access して検索失敗したらそこにノード挿入。結果として k は葉として挿入さ
れる。
4.3
データ削除
データ k の削除: k を access して削除すべきノードを決定後、ノード削除。
5
AVL 木
単純な 2 分探索木ではノードの挿入・削除を繰り返すと、バランスがとれなくなり検索性能が低下する
危険性がある。そこで木のバランスが取れなくなったら木を再構成する手法が考えられた。代表例が AVL
木。AVL 木は最悪でも O(log n) でデータ検索を完了できる。
ノードの挿入や削除により、左部分木と右部分木の高さの差が 2 以上になるノードが発生したら再構成
AVL 木では再構成により，全ノードの左部分木の高さと右部分木の高さの差を 1 以下に維持する。しか
し、各ノードで左右の部分木のバランス状態を記憶する必要がある。
6
回転操作
回転は木のバランスを変更するための基本操作。左回転と右回転がある。木 T の根ノードを r とし、r
の左の子供を Lr , 右の子供を Rr とする。
木 T の左回転： 左部分木を拡大し、右部分木を縮小させる。
1. Rr を木の根にし、r を Rr の左の子供にする。
3
2. Rr の左部分木を r の右部分木として付け替える。
木 T の右回転： 右部分木を拡大し、左部分木を縮小させる。
1. Lr を木の根にし、r を Lr の右の子供にする。
2. Lr の右部分木を r の左部分木として付け替える。
r
Rr
Lr
Rr
r
left
rotation
Lr
T4
T1
T2
T3
T4
T3
T1
r
T2
Lr
Lr
Rr
r
right
rotation
Rr
T1
T1
T2
T3
T4
T2
T3
T4
図 2: 回転操作
splay 木
7
splay 木はバランス状態を明示的に把握することなく、左右部分木をバランスさせる 2 分探索木である。
この意味で splay 木は自己調整木 (self adjusting tree) とも呼ばれる。splay 木の特徴は splay 操作と呼ば
れる再構成操作を利用することである。また、splay 木では過去の access, insert の履歴 (参照の局所性) を
考慮するので、現実のデータベース操作列に対してよい性能を示す。
7.1
基本アイデア
move-to-root 操作: access 操作と insert 操作の時に木の再構成を行い、操作対象のデータを根に移動。
splay 木では、最近使用されたデータは根に近い位置に存在する。従って、よく使用されるデータほど
根に近くなり高速に検索できる、ほとんど使用されないデータは根から遠くなるが、滅多に検索されない
ので時間がかかってもよい。splay 木の実例としては web proxy キャッシュがある。
4
7.2
move-to-root 操作
move-to-root(x): データ x を根まで splay 操作の繰り返しにより移動する。
hx : x の深さを表す変数。hx = 1 の時，x は根と一致。 while(hx 6= 1){
if(hx = 2){
zig splaying 実行;
hx = hx − 1.
}
else /* hx ≥ 3 */ {
x と x の親ノード, 祖父ノードとの位置関係により、zig-zig または zig-zag splaying 実行;
hx = hx − 2;
}
}
7.3
splay 操作
データ x を根に移動する際の基本操作。以下の 3 種類ある。
• zig splaying： 深さ hx = 2 の時に使用。x が根となるように回転。zig splaying によって、深さ hx
は 1 減少。
x
y
zig
x
y
A
B
C
A
C
B
図 3: zig splaying
• zig-zig splaying: 深さ hx ≥ 3 の時に使用。祖父ノードまで、x から同じ方向に 2 回連続で進んで辿
り着く状況で使用（例：左 2 回連続、右 2 回連続)。zig-zig splaying により、hx は 2 減る。
x の親を p(x)、祖父を g(x) とする。
1. p(x) を g(x) 側に回転。
2. 続いて、x を p(x) 側に回転。
• zig-zag splaying : 深さ hx ≥ 3 の時に使用。祖父ノードまで、x から辿る際に異なる方向に進む必要
がある状況で使用（例：左 → 右、右 → 左）。zig-zag splaying によって、hx は 2 減る。
1. x を p(x) 側に回転。
2. さらに、x を g(x) 側に回転。
5
z
x
y
y
zig-zig
D
A
x
A
Z
B
C
C
B
D
図 4: zig-zig splaying
z
x
D
y
zig-zag
y
Z
x
A
A
B
B
C
D
C
図 5: zig-zag splaying
move-to-root の例
7.4
ノード a を根に移動する例。
f
e
d
f
e
G
F
d
a
f
a
G
F
b
G
b
c
a
E
E
zig-zag
D
b
zig-zig
b
A c
B
C
C
e
e
c
zig
G
d
c
a
A
C
A
C
d
f
A
B
D
B
6
D
E
F
B
D
E
F