Экспоненциальное дерево

Экспоненциальное дерево
Тип	дерево
Изобретенный	1995
Изобретён	Арне Андерссон
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск O(min( √ log n , log n /log w + log log n , log w log log n )) O(min( √ log n , log n /log w + log log n , log w log log n )) Вставлять O(min( √ log n , log n /log w + log log n , log w log log n )) O(min( √ log n , log n /log w + log log n , log w log log n )) Удалить O(min( √ log n , log n /log w + log log n , log w log log n )) O(min( √ log n , log n /log w + log log n , log w log log n )) Пространственная сложность Космос На ​ ) На ​ )

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

Экспоненциальные деревья достигают оптимальной асимптотической сложности при выполнении некоторых операций. Они имеют преимущественно теоретическое значение.

Древовидная структура

Экспоненциальное дерево — это корневое дерево , в котором каждый узел содержит разделитель, а каждый листовой узел содержит значение. Значение может отличаться от значения сплиттера. Экспоненциальное дерево с $n$ значения определяются рекурсивно:

• Корень имеет $\Theta (n^{1/k})$ дети
• Разделитель корня такой же, как и разделитель самого левого дочернего элемента.
• Разделители всех дочерних элементов хранятся в локальной структуре данных.
• Поддеревья представляют собой экспоненциальные деревья с $\Theta (n^{1-1/k})$ ценности

Дополнительным условием является то, что поиск значения с использованием разделителей должен привести к правильному узлу (т. е. узлу, содержащему значение). Следовательно, если корень поддерева содержит разделитель $s$ и это правильный брат содержит сплиттер $s'$, то это поддерево может содержать только ключи в диапазоне $[s,s')$.

Локальная структура данных

Дерево использует статическую структуру данных в каждом внутреннем узле, чтобы обеспечить быстрый поиск значений. Должна быть возможность построить эту структуру с $d$ ценности во времени $O(d^{k-1})$. Время поиска в этой структуре обозначается $S(d)$.

дерево Fusion В качестве этой структуры данных можно использовать .

Операции

Поиск

Экспоненциальное дерево можно искать так же, как и обычное дерево поиска. В каждом узле можно использовать локальную структуру данных для быстрого поиска следующего дочернего элемента.

Позволять $T(n)$ обозначают временную сложность поиска. Тогда он удовлетворяет следующему повторению:

$T(n)\leq T(n^{1-1/k})+O(S(n))$

Ссылки

• Андерссон, Арне (октябрь 1996 г.). «Более быстрая детерминированная сортировка и поиск в линейном пространстве» . Материалы 37-й конференции по основам информатики . стр. 135–141. дои : 10.1109/SFCS.1996.548472 . ISBN  0-8186-7594-2 . S2CID   13603426 .
• Андерссон, Арне; Торуп, Миккель (1 июня 2007 г.). «Динамические упорядоченные множества с экспоненциальными деревьями поиска» . Журнал АКМ . 54 (3): 13–с. arXiv : cs/0210006 . дои : 10.1145/1236457.1236460 . ISSN   0004-5411 . S2CID   8175703 .