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