Оглавление
Экспоненциальное дерево
-
Экспоненциальное дерево
- Тип дерева поиска с экспоненциальным уменьшением числа дочерних узлов с глубиной.
- Значения хранятся только в конечных узлах.
- Каждый узел содержит разделитель, меньший или равный всем значениям в поддереве.
-
Структура данных
- Экспоненциальные деревья используют локальную структуру данных для быстрого поиска.
- Локальная структура данных строится за время O(d^k-1), где d — количество значений.
- Время поиска в локальной структуре данных обозначается S(d).
-
Операции
- Поиск выполняется аналогично обычному дереву поиска.
- Временная сложность поиска удовлетворяет повторению: T(n) ≤ T(n^1-1/k) + O(S(n)).
- Вставить и удалить значения можно аналогично обычным деревьям.
-
Теоретическое значение
- Экспоненциальные деревья имеют теоретическое значение и используются редко.
- Они достигают оптимальной асимптотической сложности для некоторых операций.