X-быстрая попытка
| X-быстрая попытка | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | Три | |||||||||||||||||||||||
| Изобретенный | 1982 | |||||||||||||||||||||||
| Изобретён | Дэн Уиллард | |||||||||||||||||||||||
| ||||||||||||||||||||||||
В информатике x -fast trie — это структура данных для хранения целых чисел из ограниченной области. Он поддерживает точные запросы, а также запросы предшественника или преемника во времени O (log log M ), используя O ( n log M пространство ), где n — количество сохраненных значений, а M — максимальное значение в домене. Структура была предложена Дэном Уиллардом в 1982 году. [1] наряду с более сложным y-fast trie , как способ улучшить использование пространства деревьями Ван Эмде Боаса , сохраняя при этом время запроса O (log log M ).
Структура [ править ]
X-fast trie — это побитовое дерево : двоичное дерево , в котором каждое поддерево хранит значения, двоичные представления которых начинаются с общего префикса. Каждый внутренний узел помечен общим префиксом значений в его поддереве, и обычно левый дочерний элемент добавляет 0 в конец префикса, а правый дочерний элемент добавляет 1. Двоичное представление целого числа от 0 до M — 1 использует ⌈log 2 M ⌉ бит, поэтому высота дерева равна O (log M ).
Все значения в дереве x-fast хранятся на листьях. Внутренние узлы сохраняются только в том случае, если в их поддереве есть листья. Если внутренний узел не имеет левого дочернего элемента, вместо этого он сохраняет указатель на самый маленький лист в своем правом поддереве, называемый указателем потомка . Аналогично, если у него нет правого дочернего элемента, он сохраняет указатель на самый большой лист своего левого поддерева. Каждый лист хранит указатель на своего предшественника и преемника, тем самым образуя двусвязный список . Наконец, для каждого уровня существует хеш-таблица , содержащая все узлы этого уровня. Вместе эти хэш-таблицы образуют структуру поиска уровня (LSS). Чтобы гарантировать время запроса в наихудшем случае, эти хеш-таблицы должны использовать динамическое идеальное хеширование или хеширование с кукушкой .
Общее использование пространства равно O ( n log M ), поскольку каждый элемент имеет путь от корня к листу длиной O (log M ).
Операции [ править ]
Подобно деревьям Ван Эмде Боаса , x-fast пытается поддерживать операции с упорядоченным ассоциативным массивом . Сюда входят обычные операции с ассоциативными массивами, а также еще две заказа операции , Successor и Predecessor :
- Найти ( k ): найти значение, связанное с данным ключом.
- Преемник ( k ): найдите пару ключ/значение с наименьшим ключом, большим или равным заданному ключу.
- Предшественник ( k ): найдите пару ключ/значение с наибольшим ключом, меньшим или равным заданному ключу.
- Вставить ( k , v ): вставить данную пару ключ/значение.
- Удалить ( k ): удалить пару ключ/значение с данным ключом.
Найти [ править ]
Поиск значения, связанного с ключом k , который находится в структуре данных, можно выполнить за постоянное время, просматривая k в LSS [0], который представляет собой хеш-таблицу на всех листьях. [2]
Например, если мы ищем цифру 4 на приведенном выше графике, мы выполним следующие шаги:
- Шаг 1: Преобразуйте десятичную цифру 4 в двоичную, то есть 100.
- Шаг 2: Начните с корня и попытайтесь пройти путь до каждого уровня. Первая цифра 100 равна 1, поэтому следуйте по правильному пути (1) от корня к узлу «1».
- Шаг 3: Повторите шаг 2, вторая цифра 100 равна 0, поэтому следуйте по левому пути (0) от узла «1» к узлу «10».
- Шаг 4: Повторите шаг 3, третья цифра 100 равна 0, поэтому следуйте по левому пути (0) от узла «10» к узлу «100».
и предшественник Преемник
Чтобы найти преемника или предшественника ключа k , мы сначала находим A k , самого низкого предка k . Это узел в дереве, который имеет самый длинный общий префикс с k . Чтобы найти A k , мы выполняем бинарный поиск по уровням. Мы начинаем с уровня h /2, где h — высота дерева. На каждом уровне мы запрашиваем соответствующую хеш-таблицу в структуре поиска уровней с префиксом k правильной длины. Если узел с таким префиксом не существует, мы знаем, что A k должен находиться на более высоком уровне, и ограничиваем наш поиск только ими. узел с таким префиксом существует, Ak Если не может находиться на более высоком уровне, поэтому мы ограничиваем наш поиск текущим и более низким уровнями.
Найдя низшего предка k , мы знаем, что у него есть листья в одном из поддеревьев (иначе его не было бы в дереве), а k должен находиться в другом поддереве. Следовательно, указатель потомка указывает на преемника или предшественника k . В зависимости от того, какой из них мы ищем, нам, возможно, придется сделать один шаг в связанном списке к следующему или предыдущему листу.
Поскольку дерево имеет высоту O (log M ), двоичный поиск наименьшего предка занимает время O (log log M ). После этого преемника или предшественника можно найти за постоянное время, поэтому общее время запроса равно O (log log M ). [1]
Например, если мы ищем предшественника 3 на приведенном выше графике, мы выполним следующие шаги:
- Шаг 1: Преобразуйте десятичную цифру 4 в двоичную, то есть 011.
- Шаг 2: Начните с корня и попытайтесь пройти путь до каждого уровня. Первая цифра 011 равна 0, поэтому следуйте по левому пути (0) корня к узлу «0».
- Шаг 3: Повторите шаг 2, вторая цифра 011 равна 1, поэтому постарайтесь следовать по правильному пути (1). Однако у узла «0» нет правильного пути, поэтому следуйте указателю к узлу «001».
- Шаг 4: 001 меньше, чем 011, поэтому он представляет предшественника 011. Следовательно, предшественником 3 является 1 (001).
Вставить [ править ]
Чтобы вставить пару ключ-значение ( k , v ), мы сначала находим предшественника и преемника k . Затем мы создаем новый лист для k , вставляем его в связанный список листьев между преемником и предшественником и присваиваем ему указатель на v . Далее мы идем от корня к новому листу, создавая необходимые узлы на пути вниз, вставляя их в соответствующие хеш-таблицы и обновляя указатели потомков там, где это необходимо.
Поскольку нам нужно пройти всю высоту дерева, этот процесс занимает время O (log M ). [3]
Удалить [ править ]
Чтобы удалить ключ k , мы находим его лист, используя хеш-таблицу листьев. Удалим его из связанного списка, но вспомним, кто был преемником и предшественником. Затем мы идем от листа к корню дерева, удаляя все узлы, поддерево которых содержит только k , и обновляя указатели потомков там, где это необходимо. Указатели потомков, которые раньше указывали на k, теперь будут указывать либо на преемника, либо на предшественника k , в зависимости от того, какое поддерево отсутствует.
Как и вставка, это занимает время O (log M ), поскольку нам приходится проходить каждый уровень дерева. [3]
Обсуждение [ править ]
Уиллард представил попытки x-fast в основном как введение в попытки y-fast , которые обеспечивают такое же время запроса, используя при этом только пространство O ( n ) и позволяя вставки и удаления за время O (log log M ). [1]
Техника сжатия, аналогичная методу Patricia Trys, может быть использована для значительного сокращения использования пространства при использовании x-fast Trys на практике. [4]
Используя экспоненциальный поиск перед бинарным поиском по уровням и запрашивая не только текущий префикс x , но и его преемник x + 1, x-fast пытается ответить на запросы предшественника и преемника за время O (log log Δ ), где Δ — это разница между значением запроса и его предшественником или преемником. [2]
Ссылки [ править ]
- ^ Перейти обратно: а б с Уиллард, Дэн Э. (1983). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ( N )». Письма об обработке информации . 17 (2). Эльзевир: 81–84. дои : 10.1016/0020-0190(83)90075-3 . ISSN 0020-0190 .
- ^ Перейти обратно: а б Бозе, Просенджит ; Дуеб, Карим; Дуймович, Вида ; Ховат, Джон; Морин, Пэт (2010), Быстрый локальный поиск и обновления в ограниченных вселенных (PDF) , Материалы 22-й Канадской конференции по вычислительной геометрии (CCCG2010), стр. 261–264.
- ^ Перейти обратно: а б Шульц, Андре; Кристиано, Пол (04 марта 2010 г.). «Конспекты лекций из лекции 9 о расширенных структурах данных (весна '10, 6.851)» (PDF) . Проверено 13 апреля 2011 г.
- ^ Кеменцицидис, Анастасиос; Ван, Мин (2009), Оценка запроса на происхождение: что в этом такого особенного? , Материалы 18-й конференции ACM по управлению информацией и знаниями, стр. 681–690.