X-быстрый триммер
-
Структура x-fast trie
- Побитовое дерево с двоичным представлением значений
- Высота дерева O(log M)
- Внутренние узлы хранят указатели на листья
- Листья образуют двусвязный список
- Хэш-таблицы на уровнях для поиска
-
Операции
- Поиск значения: O(log log M)
- Преемник и предшественник: O(log log M)
- Вставка: O(log M)
- Удаление: O(log M)
-
Пример поиска
- Поиск значения 4: O(log log M)
- Поиск преемника 3: O(log log M)
-
Обсуждение
- X-fast trie как введение в y-fast trie
- Метод сжатия для сокращения пространства
- Экспоненциальный поиск для ускорения запросов