Splay-дерево

Расширяющееся дерево (англ. splay tree) является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву. Учётная стоимость в расчёте на одну операцию с деревом составляет O(logn).

Расширяющееся дерево придумали Роберт Тарьян и Даниель Слейтор в 1983 г.

См. также

• Сбалансированные (самобалансирующиеся) деревья:

• Красно-чёрное дерево
• АВЛ-дерево
• Идеально сбалансированное дерево

Операции

Splay (расширение)

Search (поиск элемента)

Insert (добавление элемента)

Delete (удаление элемента)

Join (обьединение двух деревьев)

Split (разделение дерева на две части)

Примечание

Расширяющееся дерево предоставляет самоизменяющуюся структуру - структуру, характеризующуюся тенденцией хранить узлы, к которым часто происходит обращение, вблизи верхушки дерева, в то время как узлы к которым обращение происходит редко перемещаются ближе к листьям. Таким образом время обращения к часто посещаемым узлам будет меньше, а время обращения к редко посещаемым узлам - больше среднего.

Расширяющееся дерево не обладает никакими явными функциями балансировки, но процесс скоса узлов к корню способствует поддержанию дерева в сбалансированном виде.

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4
• Daniel Sleator, Robert Tarjan A data structure for dynamic trees. — Journal of Computer and System Sciences, 1983. — С. 262-391.