286
правок
Изменения
Нет описания правки
'''Сплей-дерево''' (англ. ''Splay-tree'') — это [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в <tex>1983 </tex> году.
==Эвристики==
* '''Splay''' {{---}} также совершает повороты, но чередует различные виды поворотов, благодаря чему достигается логарифмическая амортизированная оценка. Она будет подробно описана ниже.
'''Пример''': При последовательном использовании операций "move to root" для вершин <tex>A</tex> и <tex>B</tex> требуется по <tex>6 </tex> поворотов, в то время как при использовании операции "splay" для вершины <tex>B</tex> достаточно <tex>3 </tex> поворотов.
[[file:Move_to_root.png|750px]]
===splay(tree, x)===
"splay" делится на <tex>3 </tex> случая:
====zig====
Если <tex>p</tex> — корень дерева с сыном <tex>x</tex>, то совершаем один поворот вокруг ребра <tex>(x, p)</tex>, делая <tex>x</tex> корнем дерева. Данный случай является крайним и выполняется только один раз в конце, если изначальная глубина <tex>x</tex> была нечетной.
==Splay-деревья по неявному ключу==
Splay-дерево по неявному ключу полностью аналогично [[Декартово дерево по неявному ключу|декартову дереву по неявному ключу]], неявным ключом также будет количество элементов дерева, меньших данного. Аналогично, будем хранить вспомогательную величину <tex>C(x)</tex> — количество вершин в поддереве. К операциям, которые уже были представлены в декартовом дереве, добавляется splay, но пересчет <tex>C(x)</tex> в ней тривиален, так как мы точно знаем, куда перемещаются изменяемые поддеревья.
== См. также ==
* [[2-3 дерево]]
* [[B-дерево]]
* [[B+-дерево]]
* [[АВЛ-дерево]]
* [[Красно-черное дерево]]
==Источники информации==
