Большое дерево
-
Определение и свойства m-арных деревьев
- m-арное дерево — это дерево с не более чем m дочерними элементами на каждом узле.
- Бинарное дерево — это m-арное дерево с m = 2.
- Полное m-арное дерево имеет 0 или m дочерних элементов на каждом уровне.
- Высота полного m-арного дерева равна O(log m n).
-
Методы обхода многомерных деревьев
- Обход многомерного дерева похож на обход бинарного дерева.
- Для обхода по порядку необходимо определить левое и правое поддеревья.
-
Преобразование многомерного дерева в бинарное
- Преобразование увеличивает высоту дерева на постоянный коэффициент.
- Процесс включает связывание дочерних узлов и удаление ссылок на остальных.
-
Способы хранения многомерных деревьев
- Массивы: компактное хранение, но требует O(m^n) пространства.
- Основанный на указателе: O(m⋅n) пространства, но более компактный.
-
Подсчет множества деревьев
- Перечисление всех возможных m-арных деревьев полезно для проверки гипотез.
- Представление битовой последовательности не всегда упорядочивает деревья.
- Простая нулевая последовательность позволяет упорядочить деревья.
-
Циклическое перечисление
- Алгоритм генерации, принимающий O(1) времени в худшем случае.
- Поворот влево и вправо на узле изменяет структуру дерева.
- Левостороннее дерево можно преобразовать в m-арное дерево, выполняя повороты влево.
-
Кодирование математического дерева
- Поддерево становится нулевым на каждой глубине
- Последовательность поворотов влево определяет кодовое слово
- Кортеж из m-1 чисел представляет количество L-2, L-3, …, L-m оборотов в корне
- c(i-1)(m-1)+t-1 — число L-t оборотов на глубине i
-
Допустимые кодировки
- Не все последовательности c(i-1)(m-1)+t-1 представляют допустимое m-арное дерево
- Последовательность действий (n-1)⋅(m-1)+1 неотрицательных целых чисел допустима, если ∑i=j n ∑t=2 m c(i-1)(m-1)+t-1 ≤ n-j для всех j ∈ 0…n
-
Лексикографическое расположение
- Лексикографически наименьшее кодовое слово состоит из нулей
- Наибольшее кодовое слово состоит из n−1 единиц и m−1 нуля
-
Применение m-ary tree
- Создание словаря для проверки допустимых строк
- m равно количеству допустимых алфавитов
- Корень дерева представляет начальную точку
- Дочерние элементы представляют следующий возможный символ
- Символы вдоль путей представляют действительные ключи
- Терминальные узлы хранят дополнительную информацию
-
Альтернативные методы
- Использование B-дерева, Octree и/или trie для создания словаря