210
правок
Изменения
м
}}
Нет описания правки
Тогда, воспользовавшись полученными оценками, найдем изменение потенциала сплей-дерева после <tex> m </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 {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> s(q) = W </tex>, а минимальное при <tex> s(q) = w(q) </tex>, а значит изменение потенциала не превышает разности этих величин.
Обозначим за <tex> t </tex> корень сплей-дерева. Тогда, воспользовавшись вышеуказанной [[#Lemma1|леммой]] (можно показать, что она верна для любого фиксированного определения веса узла) получаем, что
<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>.
}}
Данная теорема показывает, что сплей-деревья поддерживают достаточно эффективный доступ к ключам, которые находятся близко к какому-то фиксированному ключу.
==Splay-деревья по неявному ключу==
==Литература==
*[http[wikipedia://en.wikipedia.org/wiki/Splay_tree :Splay_Tree|Википедия - Splay tree]]
*[http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf Sleator, Daniel D.; Tarjan, Robert E."Self-Adjusting Binary Search Trees"]
