Войти
| X-fast trie | |
|---|---|
| Тип | Trie |
| Изобретено | 1982 |
| Изобретен | Дэном Уиллардом |
| Асимптотическая сложность. в нотации большого O | |
| Пробел | O (n log M) |
| Поиск | O (log log M) |
| Вставить | O (log M) Амортизированное среднее |
| Удалить | O (log M) амортизированное среднее |
В информатике x-fast trie - это структура данных для хранения целых чисел из ограниченного домена. Он поддерживает точные запросы и запросы-предшественники или последователи во времени O (журнал журнала M), используя пространство O (n log M), где n - количество сохраненных значений, а M - максимальное значение в домене. Структура была предложена Дэном Уиллардом в 1982 году вместе с более сложным y-fast trie как способ улучшить использование пространства деревьями ван Эмде Боаса, сохраняя при этом время запроса O (log log M).
Х-быстрое дерево, содержащее целые числа 1 (001 2), 4 (100 2) и 5 (101 2). Синие края обозначают указатели-потомки. Быстрое x-дерево - это побитовое дерево : двоичное дерево, где каждое поддерево хранит значения, двоичные представления которых начинаются с общего префикса. Каждый внутренний узел помечен общим префиксом значений в своем поддереве, и обычно левый дочерний элемент добавляет 0 в конец префикс, а правый дочерний элемент добавляет 1. Двоичное представление целого числа от 0 до M - 1 использует ⌈log 2 M⌉ битов, поэтому высота дерева равна O (log M).
Все значения в x-fast trie хранятся в листьях. Внутренние узлы сохраняются, только если у них есть листья в их поддереве. Если внутренний узел w не может иметь левого дочернего элемента, вместо этого он хранит указатель на самый маленький лист в своем правом поддереве, называемый указателем-потомком. Точно так же, если бы у него не было правого дочернего элемента, он сохраняет указатель на самый большой лист в своем левом поддереве. Каждый лист хранит указатель на своего предшественника и преемника, тем самым формируя двусвязный список . Наконец, для каждого уровня существует хэш-таблица , содержащая все узлы на этом уровне. Вместе эти хеш-таблицы образуют структуру поиска по уровням (LSS). Чтобы гарантировать наихудшее время запроса, эти хеш-таблицы должны использовать динамическое идеальное хеширование или хеширование с кукушкой.
. Общее использование пространства составляет O (n log M), поскольку каждый элемент имеет корень -листный путь длины O (журнал M).
Как и деревья Ван Эмде Боаса, x-fast пытается поддерживать операции упорядоченного ассоциативного массива . Это включает в себя обычные операции с ассоциативным массивом, а также еще две операции с порядком, Преемник и Предшественник:
Поиск значения, связанного с ключ k, который находится в структуре данных, может быть выполнен за постоянное время путем поиска k в LSS [0], который является хеш-таблицей на всех листьях.
К находим преемника или предшественника ключа k, сначала мы находим A k, младшего предка k. Это узел в дереве, который имеет самый длинный общий префикс с k. Чтобы найти A k, мы выполняем двоичный поиск по уровням. Начнем с уровня h / 2, где h - высота дерева. На каждом уровне мы запрашиваем соответствующую хеш-таблицу в структуре поиска по уровням с префиксом k правильной длины. Если узел с этим префиксом не существует, мы знаем, что A k должен быть на более высоком уровне, и ограничиваем наш поиск только этими. Если узел с этим префиксом действительно существует, A k не может быть на более высоком уровне, поэтому мы ограничиваем наш поиск текущим и более низким уровнями.
Как только мы находим младшего предка k, мы знаем, что у него есть листья в одном из его поддеревьев (иначе его не было бы в дереве), а k должен быть в другом поддереве. Следовательно, указатель потомка указывает на преемника или предшественника k. В зависимости от того, какой из них мы ищем, нам, возможно, придется сделать один шаг в связанном списке к следующему или предыдущему листу.
Поскольку дерево имеет высоту O (log M), двоичный поиск самого нижнего предка занимает O (log log M) времени. После этого преемник или предшественник может быть найден за постоянное время, поэтому общее время запроса равно O (журнал журнала M).
Чтобы вставить пару ключ-значение (k, v), мы сначала находим предшественника и преемника k. Затем мы создаем новый лист для k, вставляем его в связанный список листьев между преемником и предшественником и даем ему указатель на v. Затем мы переходим от корня к новому листу, создавая необходимые узлы по пути вниз, вставляя их в соответствующие хеш-таблицы и обновляя при необходимости указатели-потомки.
Поскольку мы должны пройти всю высоту дерева, этот процесс занимает время O (log M).
Чтобы удалить ключ k, мы находим его лист, используя хеш-таблицу на листьях. Мы удаляем его из связанного списка, но помним, какие были преемником и предшественником. Затем мы переходим от листа к корню дерева, удаляя все узлы, поддерево которых содержало только k, и обновляя указатели потомков там, где это необходимо. Указатели потомков, которые раньше указывали на k, теперь будут указывать либо на преемника, либо на предшественника k, в зависимости от того, какое поддерево отсутствует.
Как и вставка, это занимает время O (log M), так как мы должны пройти через все уровни дерева.
Уиллард представил в основном попытки x-fast в качестве введения в y-fast try, которые обеспечивают то же время запроса, используя только пространство O (n) и разрешая вставки и удаления за время O (журнал журнала M).
Техника сжатия, аналогичная patricia пытается, может быть использована для значительного уменьшения использования пространства на практике x-fast.
Используя экспоненциальный поиск перед двоичным поиск по уровням и запрос не только текущего префикса x, но и его преемника x + 1, попытки x-fast могут ответить на запросы предшественника и последователя за время O (журнал журнала Δ), где Δ - разница между значением запроса и его предшественник или преемник.
