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