Раскидистое дерево
-
Развернутое дерево
- Бинарное дерево поиска с дополнительным свойством быстрого доступа к недавно использованным элементам.
- Выполняет основные операции за O(log n) амортизированного времени.
- Для произвольного доступа время может быть больше логарифмического.
-
Преимущества
- Самооптимизируется, часто используемые узлы перемещаются ближе к корню.
- Наихудшая высота O(n), средняя O(log n).
- Полезно для кэшей и алгоритмов сбора мусора.
-
Недостатки
- Высота может быть линейной, что увеличивает фактическую стоимость операций.
- Представление может изменяться при доступе «только для чтения».
- Непригодно для многопоточной среды и чисто функционального программирования.
-
Операции
- Растопыренный: перемещение узла в корневой каталог.
- Сплайсинг: последовательность шагов для перемещения узла ближе к корню.
- Зигзагообразные шаги: повороты дерева для решения проблемы четности.
- Присоединяйтесь: объединение двух деревьев.
- Расщеплять: разделение дерева на два поддерева.
- Вставка: вставка и скручивание узла.
- Удаление: замена узла и расширение родительского элемента.
-
Реализация и варианты
- Развертывание выполняется во время второго прохода.
- Альтернативные методы: сохранение родительского указателя, перестройка дерева во время доступа.
- Semisplaying: изменение схемы zig-zig для уменьшения реструктуризации.
-
Анализ
- Амортизированная стоимость операций: O(log n).
- Фактическая стоимость операций: O(log n) + уменьшение потенциала.
-
Обозначение big O
- Обозначение big O используется для обозначения времени выполнения операций в разветвленных деревьях.
- Минимальный ранг узла равен 0, максимальный — log(n).
-
Взвешенный анализ
- Присвойте каждому узлу вес w(r).
- Определите размер(r) как сумму весов узлов в поддереве с корнем в узле r.
- Определите ранг(r) и Φ аналогично.
- Амортизированная стоимость операции расширения равна O(W).
-
Теоремы о производительности
- Теорема о балансе: стоимость выполнения последовательности S равна O(m log n + n log n).
- Теорема о статической оптимальности: стоимость выполнения S равна O(m + ∑x∈tree qx log m/qx).
- Теорема о статическом пальце: стоимость выполнения S равна O(m + n log n + ∑x∈sequence log(|x-f|+1)).
- Теорема о динамическом пальце: стоимость выполнения S равна O(m + n + ∑x,y∈sequence m log(|y-x|+1)).
- Теорема о рабочем множестве: стоимость выполнения S равна O(m + n log n + ∑x∈sequence log(t(x)+1)).
-
Гипотеза о динамической оптимальности
- Гипотеза утверждает, что сплайсированные деревья работают так же хорошо, как и любой другой алгоритм бинарного дерева поиска.
- Следствия гипотезы остаются недоказанными.
-
Варианты
- Полурастекание: элемент растекается только наполовину по направлению к корню.
- Полное разделение: выполняется только при превышении порогового значения длины пути доступа.
- CBTree: дополняет разветвленное дерево количеством обращений на каждом узле.
- LazyCBTree: выполняет не более одного оборота при каждом поиске.
-
Дополнительные структуры данных
- Дерево AVL
- B-дерево
- Пальчиковое дерево
- Геометрия бинарных деревьев поиска
- Структура рабочего набора Iacono
- Связать/срезать дерево
- Список структур данных
- Дерево козлов отпущения
- Splaysort
- Т-образное дерево
- Трепать
- Вращение дерева
- Деревья
- Молния (структура данных)
- Записи
- Рекомендации