Advanced Data Structure 第3回

Presentation on theme: "Advanced Data Structure 第3回"— Presentation transcript:

1 Advanced Data Structure 第3回
黒橋研究室 M1 真鍋 宏史

2 第三回の内容 Wilber の下限 Tango tree アクセス列に対する、二分探索木のコストの下限 (アクセス列の関数)
総コストが、Wilber の下限の O(lg lg n)倍 現時点で最善

3 Wilberの第二下限 二分探索木において、 アクセス列に対する総コストの下限 すべてのアクセスに対するWilber 数の合計
ある要素がアクセスされた時、前のその要素への アクセスまでさかのぼって調べる その要素に最も近いものの場所を左右別々に記録 最も近いものの位置が更新されたとき、前回と 左右が逆なら Wilber 数を1増やす

4 Wilber数(実例) アクセス列: a, i, h, j, g, f, c, l, k, e, n, d, b, p, m, o, i 1個前の o から、最初から 2番目の i まで(逆順) a(i):左側の最大 b(i)：右側の最小 a(i), b(i) の初期値はそれぞれ-∞, +∞ a i h j g f c l k e n d b p m o i Wilber数: 3 4 5 6 2 1 a(i) b(i) a b c d e f g h i j k l m n o p

5 Key independent optimality
Working-set property を持っていれば、 アクセス列のキーをランダムに入れ替えた時 アクセス時間の期待値は 入れ替えの例: 2, 3, 6, 3, 6, 6, 2, 2 ,4, 1, 5, 1, 2, 5, ↓ 4, 6, 1, 6, 1, 1, 4, 4, 3, 2, 5, 2, 4, 5, 1 Working-set bound は順番には関係ないので O(・)は自明

6 Ω(・)の証明(概略) 今のアクセスを xj として wilber2(xj)は xj の working-set のみに依存
W={前の xj から今までにアクセスされた要素} xj は一定の確率で「だいたい」真ん中に来る E[ai が増加する回数] = Θ(lg|W|) E[bi が減少する回数] = Θ(lg|W|) 主張:aiの増加とbiの減少は一定割合が 互い違いになる⇒E[wilber2(xj)]= Θ(lg|W|)

7 Wilberの第一下限 元々の二分木とは別に、lower bound tree を 考える Lower bound tree とは？
元々のキーを j, j+1, …, k とすると、 内部ノードが j+1/2, j+3/2, …, k-1/2で、 葉が j, j+1, …, k の二分木 ここでは、完全二分木を考える

8 Wilber の第一下限 3 T(元の木) 1 6 2 4 7 5 8 4.5 P(LBT) 2.5 6.5 1.5 3.5 5.5 7.5
要求列： 3, 7, 2, 4, 3, 5, 1, 2

9 Transition point 3 T(元の木) 1 6 2 4 7 5 8 4.5 P(LBT) 2.5 6.5 1.5 3.5 5.5
7.5 1 2 3 4 5 6 7 8

10 Transition point 3 T(元の木) 1 6 2 4 7 5 8 4.5 P(LBT) 2.5 6.5 1.5 3.5 5.5
7.5 1 2 3 4 5 6 7 8 * そのノードの右部分木と左部分木にアクセスする間に、必ず transition point に触れる

11 Transition Point Well-defined Z に触るまで変わらない

12 Wilber の第一下限 3 T(元の木) 1 6 2 4 7 5 8 4.5 P(LBT) 2.5 6.5 1.5 3.5 5.5 7.5
要求列： 3, 7, 2, 4, 3, 5, 1, 2

13 Tango tree O(lg lg n)-competitive
Lower bound tree の preferred path を使って 補助木を構築 それぞれの補助木は平衡二分木

14 補助木 4.5 P 2.5 6.5 1.5 3.5 5.5 7.5 2 3 4 5 6 7 8 1

15 補助木 4.5, 2.5, 3.5, 3 6.5, 5.5, 5 1.5, 2 4 1 7.5, 8 6 7

16 補助木-「6」を検索(1) 3 2.5 4.5 3.5 4 6.5, 5.5, 5 1.5, 2

17 補助木-「6」を検索(2) 5.5 5 6.5 7.5, 8 6

18 競合比 一個の補助木の検索時間＝O(lg lg n) 全体の検索時間＝O(検索する補助木の数×lg lg n)
補助木の間を移動する回数＝ 変わる preferred path の本数 検索する補助木の数＝ 変わる preferred path の本数+1 変わる preferred path の本数＝ L と R のラベルの変化の回数 OPT＝O(LとRのラベルの変化の回数) (Wilber の第一下限)

19 補助木の更新(「2」を検索) P 4.5 2.5 6.5 1.5 3.5 5.5 7.5 1 2 3 4 5 6 7 8