Войти
| Y-fast trie | |
|---|---|
| Тип | Trie |
| Изобретено | 1982 |
| Изобретено | Дэном Уиллардом |
| Асимптотическая сложность. в нотации большого O | |
| Пробел | O (n) |
| Поиск | O (log log M) |
| Insert | O (log log M) амортизированное среднее |
| Удалить | O (log log M) амортизированное среднее |
В информатике, y-fast trie - это структура данных для хранения целых чисел из ограниченного домена. Он поддерживает точные и предшествующие или последующие запросы во времени O (журнал журнала M), используя пространство O (n), где n - количество сохраненных значений, а M - максимальное значение в домене. Структура была предложена Дэном Уиллардом в 1982 году для уменьшения пространства O (n log M), используемого x-fast trie.
Пример y-fast trie. Узлы, показанные в x-быстром дереве, являются представителями сбалансированных бинарных деревьев поиска O (n / log M). Y-быстрое дерево состоит из двух структур данных: верхняя половина - это x-быстрое дерево и нижняя половина состоит из ряда сбалансированных двоичных деревьев. Ключи делятся на группы из O (log M) последовательных элементов, и для каждой группы создается сбалансированное двоичное дерево поиска. Чтобы облегчить эффективную вставку и удаление, каждая группа содержит не менее (log M) / 4 и не более 2 log M элементов. Для каждого сбалансированного бинарного дерева поиска выбирается представитель r. Эти представители хранятся в x-fast trie. Представитель r не обязательно должен быть элементом дерева, связанного с ним, но он должен быть целым числом, меньшим, чем последователь r и минимальным элементом дерева, связанным с этим преемником, и большим, чем предшественник r и максимальный элемент дерева, связанного с этим предшественником. Первоначально представителем дерева будет целое число между минимальным и максимальным элементом в его дереве.
Поскольку x-быстрое дерево хранит O (n / log M) представителей, и каждый представитель встречается в хэш-таблицах O (log M), эта часть y-быстрого дерева использует O (n) пространства. Сбалансированные бинарные деревья поиска хранят всего n элементов, которые занимают пространство O (n). Следовательно, всего y-быстрое дерево использует пространство O (n).
Как и деревья Ван Эмде Боаса и попытки x-fast, попытки y-fast поддерживают операции упорядоченного ассоциативного массива . Сюда входят обычные операции с ассоциативным массивом, а также еще две операции с порядком, Преемник и Предшественник:
Ключ k можно сохранить либо в дереве наименьшего представителя r, превышающего k, либо в дереве предшественника r, поскольку представитель двоичного дерева поиска не обязательно должен быть элементом, хранящимся в его дереве. Следовательно, сначала нужно найти наименьшего представителя r, превышающего k, в x-быстром дереве. Используя этого представителя, можно получить предшественника r. Эти два представителя указывают на два сбалансированных бинарных дерева поиска, каждое из которых ищет k.
Нахождение наименьшего представителя r, превышающего k в x-быстром дереве, занимает O (log log M). Используя r, поиск его предшественника занимает постоянное время. Поиск в двух сбалансированных двоичных деревьях поиска, содержащих O (log M) элементов, занимает время O (log log M). Следовательно, ключ k можно найти и получить его значение за время O (журнал журнала M).
Аналогично самому ключу k его преемник может быть сохранен либо в дереве наименьшего представителя r, превышающем k, либо в дереве предшественника r. Следовательно, чтобы найти преемника ключа k, сначала выполняется поиск в x-быстром дереве наименьшего представителя, превышающего k. Затем этот представитель используется для извлечения своего предшественника в x-fast trie. Эти два представителя указывают на два сбалансированных бинарных дерева поиска, в которых выполняется поиск преемника k.
Поиск наименьшего представителя r, превышающего k в x-быстром дереве, занимает время O (log log M) и использование r, чтобы найти своего предшественника, требуется постоянное время. Поиск в двух сбалансированных двоичных деревьях поиска, содержащих O (log M) элементов, занимает время O (log log M). Следовательно, преемник ключа k может быть найден и его значение получено за время O (log log M).
Поиск предшественника ключа k очень похож на поиск его преемника. Один ищет в x-быстром дереве наибольшего представителя r, меньшего, чем k, и другой использует r для получения его предшественника в x-быстром дереве. Наконец, в двух сбалансированных двоичных деревьях поиска этих двух представителей ищется предшественник k. Это занимает время O (log log M).
Чтобы вставить новую пару ключ / значение (k, v), сначала нужно определить, в какое сбалансированное двоичное дерево поиска нужно вставить k. Для этого нужно найти дерево T, содержащее преемника k. Затем вставляется k в T. Чтобы гарантировать, что все сбалансированные бинарные деревья поиска содержат O (log M) элементов, T разбивает T на два сбалансированных бинарных дерева и удаляет его представителя из x-быстрого дерева, если оно содержит более 2 log M элементы. Каждое из двух новых сбалансированных двоичных деревьев поиска содержит не более log M + 1 элементов. Для каждого дерева выбирается представитель и вставляется в x-fast trie.
Поиск преемника k занимает время O (log log M). Вставка k в сбалансированное двоичное дерево поиска, которое содержит O (log M) элементов, также занимает O (log log M) времени. Разделение двоичного дерева поиска, содержащего O (log M) элементов, может быть выполнено за O (log log M) времени. Наконец, вставка и удаление трех представителей занимает время O (log M). Однако, поскольку дерево разбивается не чаще одного раза за каждые O (log M) вставок и удалений, это требует постоянного амортизированного времени. Следовательно, вставка новой пары ключ / значение занимает O (log log M) амортизированного времени.
Удаление очень похоже на вставку. Сначала находят ключ k в одном из сбалансированных двоичных деревьев поиска и удаляют его из этого дерева T. Чтобы гарантировать, что все сбалансированные двоичные деревья поиска содержат O (log M) элементов, объединяют T со сбалансированным двоичным деревом поиска его преемника. или предшественник, если он содержит менее (log M) / 4 элементов. Представители объединенных деревьев удаляются из x-fast trie. Объединенное дерево может содержать более 2 элементов журнала M. В этом случае вновь сформированное дерево разбивается на два дерева примерно равного размера. Затем выбирается новый представитель для каждого нового дерева и вставляется в x-fast trie.
На поиск ключа k требуется время O (log log M). Удаление k из сбалансированного двоичного дерева поиска, содержащего O (log M) элементов, также занимает O (log log M) времени. Слияние и возможное разделение сбалансированных двоичных деревьев поиска занимает время O (log log M). Наконец, удаление старых представителей и вставка новых представителей в x-fast trie занимает время O (log M). Однако слияние и возможное разделение сбалансированного двоичного дерева поиска выполняется не более одного раза для каждых O (log M) вставок и удалений. Следовательно, требуется постоянное амортизированное время. Следовательно, удаление пары ключ / значение занимает O (журнал журнал M) амортизированного времени.
