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> была нечетной.
