210
правок
Изменения
Нет описания правки
Так как вершина <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,...,p_n)) = O(mH(p_1,...,p_n))</tex>, ч.т.д.
}}
==Теорема о близких запросах в сплей-дереве==
{{Теорема
|about =
о близких запросах в сплей-дереве
|statement =
Пусть в сплей-дерево сложены ключи <tex> 1, \dotsc, n </tex>, зафиксируем один из ключей <tex> f </tex>, пусть выполняется <tex> m </tex> запросов к ключам. Тогда суммарное время на запросы есть <tex> \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) </tex>, где <tex> q_{i} </tex> {{---}} значение элемента, к которому обращаются в <tex> i </tex>-й ый запрос.
|proof =
По условию выполняется <tex> m </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} + \Phi_{0} - \Phi_{m} = \sum_{i=1}^{m} a_\left( \Phi_{i-1} + - \Delta Phi_{i} \Phi right) </tex> <tex> (\ast) </tex>.
Введем следующие обозначения:
* <tex> r(q) = \log_{2}s(q) </tex> {{---}} ранг узла.
* Потенциал дерева после <tex> i </tex>-го запроса обозначим как <tex> \Phi Phi_{i} = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) </tex>.
Пусть <tex> W </tex> {{---}} вес дерева. Тогда <tex> W = \displaystyle \sum_{q=1}^{n} w(q) = \sum_{q=1}^{n} \frac {1}{\left(\lvert q - f \rvert + 1 \right)^{2}} \leqslant 2 \cdot \sum_{q=1}^{+\infty} \frac {1}{ \left ( \lvert q - f \rvert + 1 \right)^{2}} = O(1) </tex>.
Также заметим, что для любого <tex> q </tex> от <tex> 1 </tex> до <tex> n </tex> верно, что <tex> w(q) \geqslant \displaystyle \frac {1}{n^{2}} </tex>, так как максимальное значение знаменателя в определении <tex> w(q) </tex> достигается при <tex> q = n </tex> и <tex> f = 1 </tex> или наоборот.
Тогда , воспользовавшись полученными оценками, найдем изменение потенциаласплей-дерева после <tex> m </tex> запросов:
<tex> \Deltadisplaystyle \sum_{i=1}^{m} \left( \Phi_{i-1} - \Phi Phi_{i} \right) = \Phi_{0} - \Phi_{m} \leqslant \displaystyle \sum_{q=1}^{n} \log_{2} W - \sum_{q=1}^{n} \log_{2}w(q) = \sum_{q=1}^{n} \log_{2} \frac {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> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной [[#Lemma1|леммой]](можно показать, что она верна для любого фиксированного определения веса узла) получаем, что
<tex> \displaystyle a_{i} = 3 \cdot \left( r(t) - r(q_{i}) \right) + 1 = O\left(\log_{2} \frac{s(t)}{s\left(q_{i}\right)}\right) + 1 = O\left(\log_{2} \frac{W}{w(q_{i})}\right) + 1 = </tex> <tex> O\left(\log_{2} \left(W \cdot \left(\lvert q - f \rvert + 1 \right)^{2} \right ) \right ) + 1 = O\left(\log_{2} \left(\lvert q - f \rvert + 1 \right) \right ) + 1 </tex>.
Докажем, что данное определение потенциала удовлетворяет условию [[Амортизационный анализ|теоремы о методе потенциалов]].
Для любого <tex> i </tex> верно, что <tex> a_{i} = O(\log_{2}(n)) </tex>, так как <tex> \lvert q - 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> (\ast) </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 log_{2} \left( \lvert q_{i} - f \rvert + 1 \right) \right)</tex>. Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу.
}}
