Изменения

'''Сплей-дерево ''' (англ. ''Splay-tree)''' {{---}} ) — это двоичное дерево поиска. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

* '''Move to Root''' {{---}} совершает повороты вокруг ребра <tex>(x, p)</tex>, где <tex>x</tex> - — найденная вершина, <tex>p</tex> - — ее предок, пока <tex>x</tex> не окажется корнем дерева. Однако можно построить такую последовательность операций, что амортизированное время доступа к вершине будет <tex> O\Omega(n) </tex>.

===Splaysplay(Treetree, x)==="Splaysplay" делится на 3 случая:====Zigzig====Если <tex>p</tex> - — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.

[[file:Зиг.png|800px|Zig - zig — поворот]]====Zigzig-Zigzig====Если <tex>p</tex> - — не корень дерева, а <tex>x</tex> и <tex>p</tex> - — оба левые или оба правые дети, то делаем поворот ребра <tex>(p, g)</tex>, где <tex>g</tex> отец <tex>p</tex>, а затем поворот ребра <tex>(x, p)</tex>.

[[file:Зиг_зиг.png|800px|Zigzig-zig - — поворот]]====Zigzig-Zagzag====Если <tex>p</tex> - — не корень дерева и <tex>x</tex> - — левый ребенок, а <tex>p</tex> - — правый, или наоборот, то делаем поворот вокруг ребра <tex>(x, p)</tex>, а затем поворот нового ребра <tex>(x, g)</tex>, где <tex>g</tex> - — бывший родитель <tex>p</tex>.

[[file:Зиг_заг2.png|900px|Zigzig-zag - — поворот]]

Данная операция занимает <tex>O(d)</tex> времени, где <tex>d</tex> - — длина пути от <tex>x</tex> до корня.

===Findfind(Treetree, x)===Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного дерева]], только после нее запускается операция Splaysplay.

===Mergemerge(Tree1tree1, Tree2tree2)===У нас есть два дерева <tex>Tree1\mathtt{tree1}</tex> и <tex>Tree2\mathtt{tree2}</tex>, причём подразумевается, что все элементы первого дерева меньше элементов второго. Запускаем Splay splay от самого большого элемента в дереве <tex>Tree1\mathtt{tree1}</tex> (пусть это элемент <tex>i</tex>). После этого корень <tex>Tree1\mathtt{tree1}</tex> содержит элемент <tex>i</tex>, при этом у него нет правого ребёнка. Делаем <tex>Tree2\mathtt{tree2}</tex> правым поддеревом <tex>i</tex> и возвращаем полученное дерево.

===Splitsplit(Treetree, x)===Запускаем Splay splay от элемента <tex>x</tex> и возвращаем два дерева, полученные отсечением правого или левого поддерева от корня, в зависимости от того, содержит корень элемент больше или не больше, чем <tex>x</tex>.

===Addadd(Treetree, x)===Запускаем Splitsplit(Treetree, x), который нам возвращает деревья <tex>Tree1\mathtt{tree1}</tex> и <tex>Tree2\mathtt{tree2}</tex>, их подвешиваем к <tex>x</tex> как левое и правое поддеревья соответственно.

===Removeremove(Treetree, x)=== Запускаем Splay splay от <tex>x</tex> элемента и возвращаем Merge от его детей.

'''Zigzig'''. Поскольку выполнен один поворот, то амортизированное время выполнения шага <tex>T = 1 + r'(x) + r'(p) - r(x) - r(p)</tex> (поскольку только у вершин <tex>x</tex> и <tex>p</tex> меняется ранг). Ранг вершины <tex>p</tex> уменьшился, поэтому <tex>T \le leqslant 1 + r'(x) - r(x)</tex>. Ранг вершины <tex>x</tex> увеличился, поэтому <tex>r'(x) - r(x) \ge geqslant 0</tex>. Следовательно, <tex>T \le leqslant 1 + 3r'(x) - 3r(x)</tex>.

'''Zigzig-zig'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(x) + r'(p) + r'(g) - r(p) - r(x) - r(g)</tex>. Поскольку после поворотов поддерево с корнем в <tex>x</tex> будет содержать все вершины, которые были в поддереве с корнем в <tex>g</tex> (и только их), поэтому <tex>r'(x) = r(g)</tex>. Используя это равенство, получаем: <tex>T = 2 + r'(p) + r'(g) - r(x) - r(p) \le leqslant 2 + r'(p) + r'(g) - 2r(x)</tex>, поскольку <tex>r(x) \le leqslant r(p)</tex>.

Далее, так как <tex>r'(p) \le leqslant r'(x)</tex>, получаем, что <tex>T \le leqslant 2 + r'(x) + r'(g) - 2r(x)</tex>.

Мы утверждаем, что эта сумма не превосходит <tex>3(r'(x) - r(x))</tex>, то есть, что <tex>r(x) + r'(g) - 2r'(x) \le leqslant -2</tex>. Преобразуем полученное выражение следующим образом: <tex>(r(x) - r'(x)) + (r'(g) - r'(x)) = \log_2 \fracdfrac {C(x)}{C'(x)} + \log_2 \fracdfrac {C'(g)}{C'(x)}</tex>.

Из рисунка видно, что <tex>C'(g) + C(x) \le leqslant C'(x)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов <tex>\log_2 a + \log_2 b = \log_2 ab</tex>. При <tex>a + b \le leqslant 1</tex> произведение <tex>ab</tex> по неравенству между средними не превышает <tex>1/4</tex>. А поскольку логарифм - — функция возрастающая, то <tex>\log_2 ab \le leqslant -2</tex>, что и является требуемым неравенством.

'''Zigzig-zag'''. Выполнено два поворота, амортизированное время выполнения шага <tex>T = 2 + r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g)</tex>. Поскольку <tex>r'(x) = r(g)</tex>, то <tex>T = 2 + r'(p) + r'(g) - r(x) - r(p)</tex>. Далее, так как <tex>r(x) \le leqslant r(p)</tex>, то <tex>T \le leqslant 2 + r'(p) + r'(g) - 2r(x)</tex>.

Мы утверждаем, что эта сумма не превосходит <tex>2(r'(x) - r(x))</tex>, то есть, что <tex>r'(p) + r'(g) - 2r'(x) \le leqslant -2</tex>. Но, поскольку <tex>r'(p) + r'(g) - 2r'(x) = \log_2 \fracdfrac {C'(p)}{C'(x)} + \log_2 \fracdfrac {C'(g)}{C'(x)} \le leqslant -2</tex> - аналогично доказанному ранее, что и требовалось доказать.

Итого, получаем, что амортизированное время шага zig-zag не превосходит <tex>2(r'(x) - r(x)) \le leqslant 3(r'(x) - r(x))</tex>.

Поскольку за время выполнения операции splay выполняется не более одного шага типа zig, то суммарное время не будет превосходить <tex>3r(t) - 3r(x) + 1</tex>, поскольку утроенные ранги промежуточных вершин сокращаются (входят в сумму как с плюсом, так и с минусом). Тогда суммарное время работы splay <tex>T_{splay} \le leqslant 3\log_2 N - 3\log_2 C(x) + 1 = O(\log_2 N)</tex>, где <tex>N</tex> - — число элемнтов элементов в дереве.

Если к ключам <tex>1</tex>, ...<tex>\ldots </tex>, <tex>n</tex>, сложенным в сплей-дерево выполняется <tex>m</tex> запросов, к <tex>i</tex>-му ключу осуществляется <tex>k_i</tex> запросов, где <tex>k_i</tex> > 0, то суммарное время работы не превышает <tex>O(m * \cdot H(p_1, p_2, ..\ldots , p_n))</tex>, где <tex>p_i = k_i / m</tex>, <tex>H</tex> - — шенноновская энтропия

Известно, что <tex>H(p_1, p_2, ..\ldots , p_n) = -c \cdot \displaystyle \sum_{i=1}^n (p_i \cdot \log_{2}p_i)</tex> {{---}} [[Энтропия_случайного_источника | шенноновская энтропия]].

Из предыдущей теоремы известно, что <tex>a_{splay} \leqslant 1+3(r(r)-r(x))</tex>

<tex>m+3mr(r)-3 \displaystyle \sum_{i=1}^n k_ir(x_i) \leqslant m+3mr(r)-3 \displaystyle \sum_{i+1}^n k_i\log_{2}w(x_i) =</tex> <tex> m+3mr(r)-3 \displaystyle \sum_{i=1}^n (p_i\cdot m\cdot \log_{2}p_i) = m(1+3r(r)-3 \displaystyle \sum_{i=1}^n p_i\log_{2}p_i) = (*)</tex>Так как вершина <tex>r</tex> {{---}} корень <tex>splay</tex>-дерева, то очевидно, что <tex>s = \displaystyle \sum_{y} w(y) = 1</tex>, следовательно <tex>r(r) = \log_{2}s(r)=0</tex>. Поэтому <tex>(*) = m(1+H(p_1,...\ldots ,p_n)) = O(mH(p_1,...\ldots ,p_n))</tex>, ч.т.д.

<tex> T = \displaystyle \sum_{i=1}^{m} t_{i} = \sum_{i=1}^{m} \left(a_{i} + \Phi_{i-1} - \Phi_{i} \right) = \sum_{i=1}^{m} a_{i} + \sum_{i=1}^{m} \left( \Phi_{i-1} - \Phi_{i} \right) </tex> <tex> (\ast) </tex>.

* Весом узла с ключом <tex> q </tex> будем называть величину <tex> w(q) =\displaystyle \frac dfrac {1}{\left(\lvert q - f \rvert + 1 \right )^{2}} </tex>.

Пусть <tex> W </tex> {{---}} вес дерева. Тогда <tex> W = \displaystyle \sum_{q=1}^{n} w(q) = \sum_{q=1}^{n} \frac dfrac {1}{\left(\lvert q - f \rvert + 1 \right)^{2}} \leqslant 2 \cdot \sum_{q=1}^{+\infty} \frac dfrac {1}{ \left ( \lvert q - f \rvert + 1 \right)^{2}} = O(1) </tex>.

Из определения размера узла следует, что <tex> w(q) \leqslant s(q) \leqslant W </tex>.

Также заметим, что для любого <tex> q </tex> от <tex> 1 </tex> до <tex> n </tex> верно, что <tex> w(q) \geqslant \displaystyle \frac dfrac {1}{n^{2}} </tex>, так как максимальное значение знаменателя в определении <tex> w(q) </tex> достигается при <tex> q = n </tex> и <tex> f = 1 </tex> или наоборот.

<tex>\displaystyle \sum_{i=1}^{m} \left( \Phi_{i-1} - \Phi_{i} \right) = \Phi_{0} - \Phi_{m} \leqslant \sum_{q=1}^{n} \log_{2} W - \sum_{q=1}^{n} \log_{2}w(q) = \sum_{q=1}^{n} \log_{2} \frac dfrac {W}{w(q)} </tex> <tex> \displaystyle = O \Biggl(\sum_{q=1}^{n} \log_{2} n^{2}\Biggr) = </tex> <tex> \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left(n \log_{2}n\right) </tex>.

<tex> \displaystyle a_{i} = 3 \cdot \left( r(t) - r(q_{i}) \right) + 1 = O\left(\log_{2} \fracdfrac {s(t)}{s\left(q_{i}\right)}\right) + 1 = O\left(\log_{2} \fracdfrac {W}{w(q_{i})}\right) + 1 = </tex> <tex> O\left(\log_{2} \left(W \cdot \left(\lvert q_{i} - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left(\log_{2} \left(\lvert q_{i} - f \rvert + 1 \right) \right ) + 1 </tex>.

Для любого <tex> i </tex> верно, что <tex> a_{i} = O(\log_{2}(n)) </tex>, так как <tex> \lvert q_{i} - f \rvert + 1 \leqslant n </tex>, и <tex> \Phi_{i} = O(n\log_{2}(n)) </tex>, как было показано выше. Так как количество операций на запрос <tex>k = O(n) </tex>, то <tex> a_{i} = O(f(k,n)) </tex> и <tex> \Phi_{i} = O(kf(k,n)) </tex>, где <tex> f(k,n) </tex> {{---}} функция из теоремы о методе потенциалов, равная в данном случае <tex> \log_{2}n </tex>. Следовательно, потенциал удовлетворяет условию теоремы.

<tex>T=\displaystyle \sum_{i=1}^{m} \left ( O \left( \log_{2} \left ( \lvert q_{i} - f \rvert + 1 \right) \right) + 1 \right ) + O\left ( n \log_{2} n \right) = </tex> <tex> \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_{2} \left( \lvert q_{i} - f \rvert + 1 \right) \right)</tex>.

==ЛитератураИсточники информации==