Дерево Ван Эмде Боас
-
Описание дерева ван Эмде Боаса
- Древовидная структура данных для ассоциативного массива с m-разрядными целыми ключами
- Изобретено Питером ван Эмде Боасом в 1975 году
- Выполняет операции за O(log m) времени
-
Поддерживаемые операции
- Вставка, удаление, поиск, FindNext, FindPrevious, Minimum, Maximum
- Операции выполняются за O(1) время
-
Структура данных
- Корневой узел хранит массив T.children и значения T.min, T.max, T.aux
- Данные хранятся в поддеревьях T.children[i]
- T.aux отслеживает непустые поддеревья
-
FindNext
- Поиск преемника элемента x выполняется за O(1) время
- Рекурсия по поддеревьям во вселенной M/2
-
Insert
- Вставка элемента x выполняется за O(1) время, если дерево пусто
-
Delete
- Удаление элемента x выполняется за O(1) время, если дерево пусто
-
Практические аспекты
- Операции x/M и x%M могут быть заменены битовыми операциями
- Переключение на массив битов для повышения производительности
- Оптимизация путем удаления пустых поддеревьев
-
Ограничения и альтернативы
- Использование пространства O(M) приводит к накладным расходам
- Альтернативы: trie, хэш-таблицы, x-fast, y-fast, деревья слияния
-
Реализации и рекомендации
- Проверенная реализация в Isabelle
- Эффективный императивный стандартный ML-код
- Дальнейшее чтение: Эрик Демейн, Сэм Фингерет, Шравас Рао, Пол Кристиано
-
Деревья слияния
- Ассоциативный массив из w-разрядных целых чисел
- Используют параллелизм на уровне слов и методы манипулирования битами
- Время O(logw n) для запросов предшественника/преемника и обновлений
- Пространство O(n)
- Могут быть динамичными с помощью хэширования или экспоненциальных деревьев
-
Реализации
- Проверенная реализация в Isabelle (proof assistant)
- Доказана функциональная корректность и временные рамки
- Может быть сгенерирован эффективный императивный стандартный ML-код
-
Смотрите также
- Целочисленная сортировка
- Дерево танго
-
Рекомендации
- Дальнейшее чтение
- Эрик Демейн, Сэм Фингерет, Шравас Рао, Пол Кристиано
- Массачусетский технологический институт
- 851: Расширенные структуры данных (весна 2012)
- Примечания к лекции 11
- 22 марта 2012 года