Дерево оснований
-
Структура данных базисного дерева
- Базисное дерево (также известное как компактное префиксное дерево) оптимизирует пространство за счет объединения узлов с одним дочерним элементом.
- Число дочерних элементов каждого внутреннего узла равно основанию r дерева, где r = 2x для x ≥ 1.
- Ребра могут быть помечены последовательностями элементов или отдельными элементами.
-
Преимущества и применение
- Базисные деревья эффективны для небольших наборов и наборов с общими длинными префиксами.
- Используются в IP-маршрутизации и инвертированных индексах текстовых документов.
-
Операции
- Поддерживают операции вставки, удаления и поиска.
- Вставка добавляет новую строку, удаление удаляет строку, поиск включает точный поиск, поиск предшественника, поиск преемника и поиск всех строк с префиксом.
- Все операции выполняются в O(k), где k — максимальная длина всех строк.
-
История и сравнение
- Изобретены в 1968 году Дональдом Р. Моррисоном и Гернотом Гвехенбергером.
- В отличие от сбалансированных деревьев, базисные деревья выполняют поиск, вставку и удаление за O(k) времени.
- Базисные деревья не универсальны и требуют обратимого сопоставления со строками.
-
Варианты и улучшения
- Распространенное расширение использует два цвета узлов: «черный» и «белый».
- HAT-trie обеспечивает эффективное хранение и извлечение строк.
- Дерево PATRICIA хранит только положение первого бита ключа, что делает его компактнее.
- Адаптивное дерево оснований использует переменный размер узлов для лучшего использования пространства.
-
Дополнительные ресурсы
- Портал компьютерного программирования
- Дерево префиксов (Trie)
- Детерминированный ациклический конечный автомат (DAFSA)
- Попытки троичного поиска
- Окрошечное тесто
- Детерминированные конечные автоматы
- Массив Джуди
- Алгоритм поиска
- Расширяемое хэширование
- Сопоставленный массив хэшей trie
- Префиксное хэш-дерево
- Бурстсорт
- Алгоритм Лулео
- Кодирование Хаффмана
-
Исследование алгоритмов и структур данных
- Патрисия Три, Словарь алгоритмов и структур данных NIST
- Критические деревья, автор Дэниел Дж. Бернштейн
- Radix Tree API в ядре Linux, автор Джонатан Корбет
- Карта (радикальное дерево изменений ключей), автор Пол Жарк
- Адаптивное радикс-дерево: искусная индексация для баз данных в оперативной памяти, Виктор Лейс, Альфонс Кемпер, Томас Нейман
-
Реализации
- Реализация FreeBSD, используемая для подкачки, переадресации и других вещей
- Реализация ядра Linux, используемая для кэширования страниц
- Стандартная библиотека GNU C++ имеет реализацию trie
- Java-реализация параллельного дерева оснований, автор Найл Галлахер
- Реализация дерева оснований на C#
- Библиотека шаблонов практических алгоритмов, библиотека C++ для PATRICIA tries, автор Роман С. Клюйков
- Патриция Трие, реализация шаблонного класса на C++, автор Раду Груян
- Реализация стандартной библиотеки Haskell «основана на деревьях Патриции с большим числом порядковых номеров»
- Исходный код, доступный для просмотра в Интернете
- Реализация Patricia Trie на Java, авторы Роджер Капси и Сэм Берлин
- Деревья критических битов, разветвленные на C-код Дэниелом Дж. Бернштейном
- Реализация Patricia Trie на C, в libcprops
- Деревья Патриции: эффективные множества и отображения над целыми числами в OCaml, автор Жан-Кристоф Филлиатр
- Реализация базы данных Radix (Патриция Три) на языке Си, автор G. B. Версиани
- Libart — Адаптивные радикальные деревья, реализованные на C Армоном Дадгаром совместно с другими разработчиками (открытый исходный код, лицензия BSD 3-clause)
- Nim-реализация дерева критических битов
- rax, реализация радикального дерева в ANSI C, созданная Сальваторе Санфилиппо (создателем REDIS)