Y-быстрая пробка
-
Структура y-fast trie
- Состоит из x-fast trie и сбалансированных бинарных деревьев
- Ключи разделены на группы по O(log M) элементов
- Каждая группа содержит не менее (log M)/4 и не более 2 log M элементов
- Для каждого дерева выбирается репрезентативный r-элемент
-
Операции
- Поддерживает операции с упорядоченным ассоциативным массивом
- Включает Find(k), Преемник(k), Предшественник(k), Вставить(k, v), Удалить(k)
-
Поиск
- Ключ k может быть найден за O(log log M) времени
- Поиск в x-fast trie занимает O(log log M) времени
- Поиск в сбалансированных деревьях бинарного поиска занимает O(log log M) времени
-
Преемник и предшественник
- Поиск преемника занимает O(log log M) времени
- Поиск предшественника занимает O(log log M) времени
-
Вставка
- Вставляется в дерево, содержащее преемника k
- Разбиение дерева на два, если оно содержит более 2 log M элементов
- Вставка и удаление представителей занимает O(log M) времени
- Вставка занимает O(log log M) амортизированного времени
-
Удаление
- Удаляется из дерева, содержащего ключ k
- Слияние деревьев, если они содержат менее (log M)/4 элементов
- Удаление и вставка представителей занимает O(log M) времени
- Удаление занимает O(log log M) амортизированного времени