Изменения
Нет описания правки
'''Сплей-дерево (Splay-tree)''' {{---}} это двоичное дерево поиска, позволяющее .Оно позволяет находить быстрее те данные, которые использовались недавно. Относится к разряду сливаемых деревьев. Сплей-дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.
Очевидно, что для того, чтобы доступ к недавно найденным данным был быстрее, надо, чтобы эти данные находились ближе к корню. Этого мы можем добиться, используя эвристику "Move to Root", которая совершает повороты вокруг ребра <tex>(x, p)</tex>, где <tex>x</tex> - найденная вершина, а <tex>p</tex> - ее предок, пока <tex>x</tex> не окажется корнем дерева. Но эта эвристика не даст нам никакого улучшения времени работы. Поэтому мы будем использовать операцию "Splay" для перемещения <tex>x</tex> в корень.
==Find(Tree, x)==
Эта операция выполняется как для обычного [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F бинарного дерева] , только после нее запускается операция Splay.
==Merge(Tree1, Tree2)==
