60
правок
Изменения
Нет описания правки
'''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
==Эвристики==
'''Пример''': При последовательном использовании операций "move to root" для вершин <tex>A</tex> и <tex>B</tex> требуется по 6 поворотов, в то время как при использовании операции "splay" для вершины <tex>B</tex> достаточно 3 поворотов.
[[file:Move_to_root.png|700px750px]]
[[file:Splay.png|800px750px]]
==Операции со splay-деревом==
==Анализ операции splay==
[[Амортизационный анализ | Амортизационный анализ]] сплей-дерева проводится с помощью метода потенциалов. Потенциалом рассматриваемого дерева назовём сумму рангов его вершин. Ранг вершины <tex>x</tex> — это величина, обозначаемая <tex>r(x)</tex> и равная <tex>\log_2 C(x)</tex>, где <tex>C(x)</tex> — количество вершин в поддереве с корнем в <tex>x</tex>.
{{Лемма
Мы утверждаем, что эта сумма не превосходит <tex>3(r'(x) - r(x))</tex>, то есть, что <tex>r(x) + r'(g) - 2r'(x) \leqslant -2</tex>. Преобразуем полученное выражение следующим образом: <tex>(r(x) - r'(x)) + (r'(g) - r'(x)) = \log_2 \dfrac {C(x)}{C'(x)} + \log_2 \dfrac {C'(g)}{C'(x)}</tex>.
Из рисунка видно, что <tex>C'(g) + C(x) \leqslant C'(x)</tex>, значит, сумма выражений под логарифмами не превосходит единицы. Далее, рассмотрим сумму логарифмов <tex>\log_2 a + \log_2 b = \log_2 ab</tex>. При <tex>a + b \leqslant 1</tex> произведение <tex>ab</tex> по неравенству между средними не превышает <tex>\dfrac{1/}{4}</tex>. А поскольку логарифм — функция возрастающая, то <tex>\log_2 ab \leqslant -2</tex>, что и является требуемым неравенством.
'''zig-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) \leqslant r(p)</tex>, то <tex>T \leqslant 2 + r'(p) + r'(g) - 2r(x)</tex>.
{{Теорема
|statement=
Если к ключам <tex>1 \ldots n</tex>, сложенным в сплей-дерево выполняется <tex>m</tex> запросов, к <tex>i</tex>-му ключу осуществляется <tex>k_i</tex> запросов, где <tex>k_i> 0</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> — шенноновская энтропия
|proof=
Известно, что <tex>H(p_1, p_2, \ldots , p_n) = -c \cdot \displaystyle \sum_{i=1}^n (p_i \cdot \log_{2}p_i)</tex> {{---}} [[Энтропия_случайного_источника | шенноновская энтропия]].
