Расширяющееся дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Операции[править | править вики-текст]

Splay (расширение)[править | править вики-текст]

Основная операция дерева. Заключается в перемещении вершины в корень при помощи последовательного выполнения трёх операций: Zig, Zig-Zig и Zig-Zag. Обозначим вершину, которую хотим переместить в корень за x, её родителя - p, а родителя p (если существует) - g.

Zig: выполняется, когда p является корнем. Дерево поворачивается по ребру между x и p. Существует лишь для разбора крайнего случая и выполняется только один раз в конце, когда изначальная глубина x была нечётна.

Splay tree zig.svg

Zig-Zig: выполняется, когда и x, и p являются левыми (или правыми) сыновьями. Дерево поворачивается по ребру между g и p, а потом - по ребру между p и x.

Zigzig.gif

Zig-Zag: выполняется, когда x является правым сыном, а p - левым (или наоборот). Дерево поворачивается по ребру между p и x, а затем - по ребру между x и g.

Zigzag.gif

Search (поиск элемента)[править | править вики-текст]

Поиск выполняется как в обычном двоичном дереве поиска. При нахождении элемента запускаем Splay для него.

Insert (добавление элемента)[править | править вики-текст]

Вставка происходит как в обычном бинарном дереве поиска, после, запускаем Splay от добавляемого элемента и подвешиваем получившиеся деревья за него.

Delete (удаление элемента)[править | править вики-текст]

Находим элемент в дереве, делаем Splay для него, делаем текущим деревом Merge его детей.

Merge (объединение двух деревьев)[править | править вики-текст]

Для слияния деревьев T1 и T2, в которых все ключи T1 меньше ключей в T2, делаем Splay для максимального элемента T1, тогда у корня T1 не будет правого ребенка. После этого делаем T2 правым ребенком T1.

Split (разделение дерева на две части)[править | править вики-текст]

Для разделения дерева найдем наименьший элемент, больший или равный x и сделаем для него Splay. После этого отрезаем у корня левого ребенка и возвращаем 2 получившихся дерева.

Примечание[править | править вики-текст]

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

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

См. также[править | править вики-текст]

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

Литература[править | править вики-текст]

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 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.