Y-быстрая попытка
| Y-быстрая попытка | ||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | Три | |||||||||||||||||||||||||||||
| Изобретенный | 1982 | |||||||||||||||||||||||||||||
| Изобретён | Дэн Уиллард | |||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||
В информатике — y-быстрое дерево это структура данных для хранения целых чисел из ограниченной области. Он поддерживает точные запросы, а также запросы предшественника или преемника во времени O (log log M ), используя O ( n пространство ), где n — количество сохраненных значений, а M — максимальное значение в домене. Структура была предложена Дэном Уиллардом в 1982 году. [1] чтобы уменьшить пространство O ( n log M ), используемое x-fast trie .
Структура [ править ]
Y-быстрое дерево состоит из двух структур данных: верхняя половина представляет собой x-быстрое дерево, а нижняя половина состоит из нескольких сбалансированных двоичных деревьев . Ключи разбиваются на группы по O (log M ) последовательных элементов, и для каждой группы создается сбалансированное двоичное дерево поиска. Чтобы облегчить эффективную вставку и удаление, каждая группа содержит не менее (log M )/4 и не более 2 log M элементов. [2] представитель r Для каждого сбалансированного двоичного дерева поиска выбирается . Эти представители хранятся в дереве x-fast. Представитель r не обязательно должен быть элементом связанного с ним дерева, но он должен быть целым числом, меньшим, чем преемник r и минимальный элемент дерева, связанный с этим преемником, и больше, чем предшественник r и максимальный элемент. дерева, связанного с этим предшественником. Первоначально представителем дерева будет целое число между минимальным и максимальным элементом в его дереве.
Поскольку дерево x-fast хранит O ( n / log M ) представителей и каждый представитель встречается в хеш-таблицах O (log M ), эта часть дерева y-fast использует O ( n пространство ). Сбалансированные деревья двоичного поиска хранят в общей сложности n элементов, которые используют пространство O ( n ). Следовательно, в общей сложности y-быстрое дерево использует пространство O ( n ).
Операции [ править ]
Подобно деревьям Ван Эмде Боаса и попыткам x-fast, попытки y-fast поддерживают операции упорядоченного ассоциативного массива . Сюда входят обычные операции с ассоциативными массивами, а также еще две заказа операции , Successor и Predecessor :
- Найти ( k ): найти значение, связанное с данным ключом.
- Преемник ( k ): найдите пару ключ/значение с наименьшим ключом, большим или равным заданному ключу.
- Предшественник ( k ): найдите пару ключ/значение с наибольшим ключом, меньшим или равным заданному ключу.
- Вставить ( k , v ): вставить данную пару ключ/значение.
- Удалить ( k ): удалить пару ключ/значение с данным ключом.
Найти [ править ]
Ключ 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 (log log M ). [1]
Преемник и предшественник [ править ]
Как и сам ключ k , его преемник может храниться либо в дереве наименьшего представителя r, большего, чем k , либо в дереве предшественника r . Следовательно, чтобы найти преемника ключа k , сначала нужно найти в x-быстром дереве наименьший представитель, больший, чем k . Затем этот представитель используется для поиска его предшественника в дереве x-fast. Эти два представителя указывают на два сбалансированных двоичных дерева поиска, которые ищут преемника k . [3]
Поиск наименьшего представителя r, большего, чем k, в x-быстром дереве занимает время O (log log M ), а использование r для поиска его предшественника занимает постоянное время. Поиск в двух сбалансированных двоичных деревьях поиска, содержащих O (log M ) элементов, занимает O (log log M ) времени. Следовательно, преемник ключа k может быть найден и его значение получено за O (log log M ). время [1]
Поиск предшественника ключа k очень похож на поиск его преемника. В x-быстром дереве выполняется поиск наибольшего представителя r, меньшего, чем k, и используется r для поиска его предшественника в x-быстром дереве. Наконец, в двух сбалансированных двоичных деревьях поиска этих двух представителей производится поиск предшественника k . Это занимает время O (log log M ).
Вставить [ править ]
Чтобы вставить новую пару ключ/значение ( k , v ), сначала необходимо определить, в какое сбалансированное двоичное дерево поиска нужно вставить k . Для этого находится дерево T, содержащее наследника k . Затем вставляется k в T . Чтобы гарантировать, что все сбалансированные двоичные деревья поиска содержат элементы O (log M ), нужно разбить T на два сбалансированных двоичных дерева и удалить его представителя из x-быстрого дерева, если оно содержит более 2 log M. элементов Каждое из двух новых сбалансированных двоичных деревьев поиска содержит не более log M + 1 элементов. Для каждого дерева выбирают представителя и вставляют его в дерево x-fast.
Поиск преемника 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 ). [3]
Удалить [ править ]
Удаление очень похоже на вставку. Сначала нужно найти ключ k в одном из сбалансированных деревьев двоичного поиска и удалить его из этого дерева T . Чтобы гарантировать, что все сбалансированные деревья двоичного поиска содержат элементы O (log M объединяется ), T со сбалансированным деревом двоичного поиска его преемника или предшественника, если оно содержит менее (log M )/4 элементов. Представители объединенных деревьев удаляются из дерева x-fast. Объединенное дерево может содержать более 2 log M. элементов В этом случае вновь сформированное дерево разбивается на два дерева примерно одинакового размера. Затем выбирают нового представителя для каждого из новых деревьев и вставляют их в дерево x-fast.
Поиск ключа k занимает время O (log log M ). Удаление k из сбалансированного двоичного дерева поиска, которое содержит элементы O (log M ), также занимает время O (log log M ). Слияние и, возможно, разделение сбалансированных двоичных деревьев поиска занимает время O (log log M ). Наконец, удаление старых представителей и вставка новых представителей в дерево x-fast занимает время O (log M ). Однако слияние и, возможно, разделение сбалансированного двоичного дерева поиска выполняется не чаще одного раза для каждых O (log M ) вставок и удалений. Следовательно, требуется постоянное амортизируемое время. Таким образом, удаление пары ключ/значение занимает O (log log M ) амортизированного времени. [3]
Обратите внимание: если элемент, который мы хотим удалить, является листом X-быстрого дерева, то мы ставим пометку о том, что это число здесь просто для разделения двух бинарных деревьев поиска, и это число не будет возвращено. В этом случае номер фактически не будет удален. Это займет O (1) времени, а поиск ключа k занимает O (log log M ) времени. Следовательно, временная сложность равна O (log log M ). [4]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с Уиллард, Дэн Э. (1983). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ( N )». Письма об обработке информации . 17 (2). Эльзевир: 81–84. дои : 10.1016/0020-0190(83)90075-3 . ISSN 0020-0190 .
- ^ Бозе, Просенджит ; Дуеб, Карим; Дуймович, Вида ; Ховат, Джон; Морин, Пэт (2010), Быстрый локальный поиск и обновления в ограниченных вселенных (PDF) , Материалы 22-й Канадской конференции по вычислительной геометрии (CCCG2010), стр. 261–264.
- ^ Jump up to: Перейти обратно: а б с Шульц, Андре; Кристиано, Пол (04 марта 2010 г.). «Конспекты лекций из лекции 9 о расширенных структурах данных (весна '10, 6.851)» (PDF) . Проверено 14 апреля 2011 г.
- ^ «13 структур данных для целых чисел» . opendatastructures.org . Проверено 7 марта 2024 г.