Материал из Викиконспекты
| Теорема (о близких запросах в сплей-дереве): |
Пусть в сплей-дерево сложены ключи [math] 1, \dotsc, n [/math], зафиксируем один из ключей [math] f [/math], пусть выполняется [math] m [/math] запросов к ключам. Тогда суммарное время на запросы есть [math] \displaystyle O(n \log_{2} n + m + \sum_{i=1}^{m} \log_2 ( \lvert q_{i} - f \rvert + 1)) [/math], где [math] q_{i} [/math] — [math] i [/math]-й запрос. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для доказательства теоремы воспользуемся методом потенциалов:
[math] a_{i} = t_{i} + \Phi_{i} - \Phi_{i-1} [/math]
По условию выполняется [math] m [/math] запросов, следовательно
[math] 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_{i} + \Delta \Phi [/math] [math] (\ast) [/math]
Для удобства введем обозначения:
- Весом узла с ключом [math] q [/math] будем называть величину [math] w(q) =\displaystyle \frac {1}{\left(\lvert q - f \rvert + 1 \right )^{2}} [/math].
- Размером узла, содержащего ключ [math] q [/math], будем называть величину [math] s(q) = \displaystyle \sum_{y} w(y) [/math], где [math] y [/math] — узлы поддерева с корнем в [math] q [/math].
- [math] r(q) = \log_{2}s(q) [/math] — ранг узла.
- Потенциал дерева обозначим как [math] \Phi = \displaystyle \sum_{q=1}^{n} r(q) = \displaystyle \sum_{q=1}^{n} \log_{2}s(q) [/math].
Пусть [math] W [/math] — вес дерева. Тогда [math] 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) [/math].
Из определения размера узла следует, что [math] w(q) \leqslant s(q) \leqslant W [/math].
Также заметим, что для любого [math] q [/math] от [math] 1 [/math] до [math] n [/math] верно [math] w(q) \geqslant \displaystyle \frac {1}{n^{2}} [/math].
Тогда изменение потенциала
[math] \Delta\Phi \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)} = O \Biggl(\sum_{q=1}^{n} \log_{2} n^{2}\Biggr) = [/math] [math] \displaystyle O\Biggl(2 \cdot\sum_{q=1}^{n} \log_{2} n\Biggr) = O\left(n \log_{2}n\right) [/math].
Обозначим за [math] t [/math] корень сплей-дерева. Тогда, воспользовавшись вышеуказанной леммой, получаем, что
[math] \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 = [/math] [math] 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 [/math]
Тогда, подставляя найденные значения в формулу [math] (\ast) [/math], получаем, что
[math]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) = [/math] [math] \displaystyle O \left (n \log_{2} n + m + \displaystyle \sum_{i=1}^{m} \log_2 \left( \lvert q_{i} - f \rvert + 1 \right) \right)[/math] |
| [math]\triangleleft[/math] |
