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

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

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

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

Содержание 1 См. также 2 Операции 2.1 Splay (расширение) 2.2 Search (поиск элемента) 2.3 Insert (добавление элемента) 2.4 Delete (удаление элемента) 2.5 Join (объединение двух деревьев) 2.6 Split (разделение дерева на две части) 3 Примечание 4 Литература

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

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

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

[править] Операции

[править] 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.

Это незавершённая статья по информатике. Вы можете помочь проекту, исправив и дополнив её.