Lecture02-Binary Search Trees 通信情報システム専攻 岩間伊藤研究室 M1 前田圭介.

Presentation on theme: "Lecture02-Binary Search Trees 通信情報システム専攻 岩間伊藤研究室 M1 前田圭介."— Presentation transcript:

1 Lecture02-Binary Search Trees 通信情報システム専攻 岩間伊藤研究室 M1 前田圭介

2 前回の復習 ・データ構造のモデル (List) ・ find(x) はリストの最初から始める。 ・最初から i 番目の要素へのアクセスにはコスト i が必要 ・ 2 つの隣接した要素の入れ替えにはコスト 1 が必要 ・ある要素を見つけたとき、その要素を前方へ動かすのにコストは必要ない ・・・ i123 List

3 今回の発表内容 今回の発表ではデータ構造として二分木を扱う。 ・ Binary Search Trees ( 二分探索木 ) の定義 ・モデルの定義 ・二分探索木についてのアルゴリズム ・ Splay Trees( スプレー木 )

4 二分探索木 (Binary Search Trees) 例 7 3 5 9 811 左の子の要素の値 < 現在のノードの要素の値 <= 右の子の要素の値 全て 7 未満全て 7 以上

5 二分探索木の探索コスト ・二分探索木における操作は次の 3 つである。 ・ポインタを右に移動させる ・ポインタを左に移動させる ・現在のノードを回転させる（後述、 List における swap に対応した操作） 7 3 5 9 811 find(5) 5 < 7 5 > 3 コスト 3

6 競合比 (competitiveness) ・アルゴリズムを評価する際に用いられる指標 あるアルゴリズムが k-competitive であるとは、どんな入力列 x に対しても が成立することである。 : 評価したいアルゴリズムの x に対するコスト : x に対する最小のコスト（オフラインで計算） あるオンラインアルゴリズムが optimal であるとは、 それが O(1)-competitive であることをいう。

7 今回の発表内容 今回の発表ではデータ構造として二分木を扱う。 ・ Binary Search Trees ( 二分探索木 ) の定義 ・モデルの定義 ・二分探索木についてのアルゴリズム ・ Splay Trees( スプレー木 ) の定義 ・スプレー木の計算量解析 ・スプレー木についての結果

8 stochastic and static model ・ stochastic( 確率 ) model ・ static( 静的 ) model n 個の変数に対して、アクセスされる確率が毎回それぞれ独立である。 1 2 ・ ・・ i n n 個の変数に対して、アクセスされる確率が毎回独立でなくてもよい。 木の rotate を許さない。 ( 木が初期状態から動かない ) 例 アクセス列 {1 2 1 2 1 2 1 2 ….} ・ stochastic and static model n 個の変数に対して、アクセスされる確率が毎回それぞれ独立である。 木の rotate を許さない。 ( 木が初期状態から動かない )

9 stochastic model ・ stochastic model かそうでないかの違いは大きなものである。 [ 前回の復習 ] List 型のデータ構造における Transpose アルゴリズム ・・・ n/2123n 110723 find(3) → 3 を一つ前に持ってくる。

10 stochastic model ・ stochastic model かそうでないかの違いは大きなものである。 [ 前回の復習 ] List 型のデータ構造における Transpose アルゴリズム ・・・ n/2123n 110723 find(3) → 3 を一つ前に持ってくる。 ・ stochastic model でない場合 アクセス列 {3 2 3 2 3 2 3 2 3 2 3…} に対して、最も良い場合に比べて O(n) 倍 のコストがかかる。 ・ stochastic model の場合 2 3 1/2 のようなアクセスに対しても、 optimal である。

11 subproblems は、 個あり、 root の選び方は n 通りあるので、 合計 時間で解くことができる 最適な二分探索木 静的モデルの最適な二分探索木は動的計画法 (dynamic programming, DP) を 用いて求めることができる。 ある r を root にして、その左の部分木 ( r) の optimal を求める。 このとき、 OPT は次のように表現される。 ただし、であり、これはハフマン木のエントロピーである。 左の木が探索される確率

12 dynamic model 木の rotate 変換を許すモデル 7 3 5 9 811 rotate 3 7 3 5 9 811

13 動的モデルの二分探索木における最適コストの求め方はまだわかっていない。 当然、 O(1)-competitive かどうかもわかっていない。 一般に AVL 木や赤黒木のような平衡二分探索木の場合、 探索コストが O(log n) かかることになる n log n 木の rotate をうまく利用することで探索コストを o(log n) にできないかを考える。

14 今回の発表内容 今回の発表ではデータ構造として二分木を扱う。 ・ Binary Search Trees ( 二分探索木 ) の定義 ・モデルの定義 ・二分探索木についてのアルゴリズム ・ Splay Trees( スプレー木 )

15 アクセス頻度の反映  各ノードのアクセス頻度は一定でない  頻繁にアクセスするノードをより浅い位置に置く  オンラインアルゴリズムを考えるので、アクセス列 全体を見て頻繁にアクセスされるノードを上に持っ ていくことはできない  最後にアクセスしたノードを浅い位置に持っていく アクセス頻度 多 少

16 Transpose アルゴリズム ・最後にアクセスしたノードを一つ上のノードに持っていく（一回 rotate する）。 A BG HCD EF find(D) A DG HBF CE D B G H CEC A rotate(D)

17 Transpose の探索コスト ・ Transpose アルゴリズムは等確率で各ノードにアクセスするような確率モデル においては平均探索コストが と悪くなってしまう。 B C A C B AB CAA B C B A C [ ノード数が 3 つの場合 ] 全てのノードのアクセス確率が等確率のとき、全ての状態が等確率で出現する。 1/5

18 Move to root アルゴリズム ・最後にアクセスしたノードが root にくるまで rotate をおこなう。 A BG HCD EF find(D) D B G H CEC A rotate(D),rotate(D)

19 Move to root の探索コスト (1) Move to root の探索コストの解析は List 型の Move to front の解析と ほとんど同様である。 i < j としたとき、 i が j の祖先となっている確率を b(i, j) とする。 A BE CD F B は F の祖先 E は F の祖先でない このとき、

20 Move to root の探索コスト (2) Move to root の探索コスト Cost(MR) は、 ここで、とすると

21 Move to root の探索コスト (3) y = 1/x

22 Move to root の探索コスト (3) ・ Move to root アルゴリズムの平均探索コストは stochastic OPT となる。 ・これは stochastic であるという条件の下で成立するものであり、 意地の悪いアクセス列を想定した場合はもっと悪くなってしまう。

23 今回の発表内容 今回の発表ではデータ構造として二分木を扱う。 ・ Binary Search Trees ( 二分探索木 ) の定義 ・モデルの定義 ・二分探索木についてのアルゴリズム ・ Splay Trees( スプレー木 )

24 スプレー木 (Splay Tree) [Sleator and Tarjan 1985]  Move to root の一種。  アクセスしたノードを単純に root まで持っていくだ けでなく、平衡状態をできるだけ保つようにして移 動させる。  rotate をおこなうときに、直前のノードだけでなく２ つ上のノードまで見て rotate 操作の方法を決める。

25 スプレー木の rotate 操作 (1) Zig case: 二つ上のノードが存在しない場合 A BE C root rotate(B) A B E C root D D 今までと同じように rotate 操作をする。

26 スプレー木の rotate 操作 (2) Zig-Zig case: B C3 1 rotate(B),rotate(C) 2 A 4 1 2A 34 C B

27 スプレー木の rotate 操作 (3) Zig-Zag case: B 1C 2 rotate(C),rotate(C) 3 A 4 B 3412 C A Move to root アルゴリズムと同様の操作である。

28 スプレー木の rotate 操作 (4) Zig case, Zig-Zig case, Zig-Zag case の 3 つを組み合わせてアクセスしたノードを root まで移動させる。 B 1C 23 A 4 D E 5 6 rotate(C), rotate(C) rotate(D), rotate(C) B 1 C 2 3 A 4 D E 56

29 スプレー木と Move to root(1) ・ Move to root は均衡をとらない 12 3 4 5 6 1 23 4 5 6

30 スプレー木と Move to root(2) ・スプレー木は均衡をとる 12 3 4 5 6 1 3 4 2 5 6 Move to root アルゴリズムよりは探索コストが少なくて済みそう

31 スプレー木の計算量  償却計算量 (amortized complexity) を用いて解析する。  スプレー操作１回ごとに計算  木構造自体にポテンシャルを保持させる。  不均衡な木：ポテンシャルが大きい  均衡な木：ポテンシャルが小さい

32 計算量解析 ・各ノードは次のように表現されるポテンシャルを保持していると定義する。 xy T0T0 T 0 (x) T 0 (y) T1T1 x T 1 (x) スプレー操作 すべての部分木の和をとったものが C i ノード数の和 T i ： スプレー操作を i 回おこなった木

33 ・ C i は平衡な木ほど小さな値になる。 3 1 1 3 1 2

34 ZigZig Case の計算量 B C 3 12 A 4 A C B 3 1 2 4 T i-1 TiTi

35 ZigZig Case の計算量 のとき より が得られて

36 ZigZig Case の計算量 B C 3 12 A 4 A C B 3 1 2 4 ここで、が成立するので、 が成立 より

37 ZigZig Case の計算量 B C 3 12 A 4 A C B 3 1 2 4 ここで、

38 全体の計算量 ZigZig Case ZigZag Case Zig Case

39 Access Lemma スプレー木における１回のスプレー操作の償却計算量 a i は として上界を抑えることができる。 この Access lemma を用いて、スプレー木に対する様々な結果を導くことができる。

40 スプレー木の計算量 アクセスした要素を root に移動させるまでスプレー操作を m 回おこなうとする。 アクセス回数を k 回とすると、 より

41 スプレー木の計算量の結果 スプレー木における１回あたりの探索コストは ・これは、スプレー木の探索コストが平衡二分木と 同程度であることを示している。 [Logarithmic Access Cost] 以上のことから次のような結果が得られる。

42 今回の計算量解析ではポテンシャルとしてノード数の和を用いた。 ノード数の和ではなく出現確率の和としてポテンシャルをとると、 次のような結果が得られる。 スプレー木における１回あたりの探索コストは ・これは、 static tree の OPT と同程度の探索コストで 探索できることを示している。 [Static Optimality Theorem]

43

44 B C 3 12 A 4 A C B 3 1 2 4 T i-1 TiTi

45 スプレー木における１回あたりの探索コストは [Static Finger Theorem] 探索を root から始めるのではなく、あるノード f を指定して そこから探索を始めるようなモデルを考える。 このときポテンシャルとして をとると次のような結果が得られる