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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Расширяющееся дерево
Тип Дерево
Изобретено в 1985 году
Изобретено Дэниел Слитор и Роберт Андре Тарьян
Временная сложность
в О-символике
В среднем В худшем случае
Расход памяти O(n) O(n)
Поиск O(log n) O(log n)
Вставка O(log n) O(log n)
Удаление O(log n) O(log n)

Расширяющееся (англ. 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 (добавление элемента)[править | править вики-текст]

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

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.