Дерево слияния
-
Описание дерева слияния
- Дерево слияния — это древовидная структура данных для ассоциативного массива из w-разрядных целых чисел.
- Использует O(n) пространства и O(logw n) времени для поиска.
- Изобретено Майклом Фредманом и Дэном Уиллардом в 1990 году.
-
История и развитие
- В 1999 году показано, как реализовать деревья слияния в модели AC0.
- В 1996 году предложена динамическая версия с хэш-таблицами.
- В 2007 году предложена динамическая версия с экспоненциальным деревом.
- В 2010 году показано, что деревья динамического слияния могут выполнять операции за O(logw n) времени.
-
Принцип работы
- Дерево слияния использует параллелизм на уровне слов для повышения эффективности.
- Каждый ключ сжимается до k-1 бита, что позволяет проводить параллельные сравнения.
- Создание эскизов и параллельное сравнение помогают найти требуемое решение.
-
Создание эскизов
- Каждый ключ x сжимается до k-1 бита.
- Эскиз сохраняет порядок расположения клавиш.
- Приблизительный эскиз использует побитовое умножение и И для упаковки битов.
-
Параллельное сравнение
- Эскиз узла позволяет выполнять поиск ключей за постоянное время.
- Параллельное сравнение вычисляет индекс i, где sketch(xi) ≥ y.
- Для произвольного запроса q вычисляется самый длинный общий префикс.
-
Термоядерное хеширование
- Применение деревьев слияния к хэш-таблицам.
- Хэш-таблица внешнего уровня с хэш-цепочкой объединяется с деревом слияния.
-
Хэш-цепочка и дерево fusion
- В хэш-цепочке средний размер цепочки постоянен
- С высокой вероятностью все цепочки имеют размер O(log n / log log n)
- Дерево fusion может выполнять поиск и обновление за постоянное время
- Время выполнения всех операций с высокой вероятностью постоянно
-
Вычислительная модель и допущения
- Вычислительная модель включает текстовую память с арифметическими и логическими командами
- Удаление инструкции по умножению с двойной точностью делает сортировку невозможной быстрее O(n log n)
-
Рекомендации
- Внешние ссылки на лекции MIT CS 6.897 и 6.851 по деревьям слияния