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

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

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

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

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

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

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

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

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 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 に触れる

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

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

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

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

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

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

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

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

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