В теории графов , м -ичное дерево (также известный как к -ичному или K -WAY дерева) является корневым деревом , в котором каждый узел имеет не более м детей. Бинарное дерево представляет собой особый случай , когда т = 2 , а тройная дерево другой случай с т = 3 , что ограничивает его ребенок до трех.
Типы м- арных деревьев
- Полные м -ичного дерево представляет собой м - позиционное дерево , где на каждом уровень каждый узел имеет 0 или т детей.
- Полные м -ичного дерево представляет собой м - позиционное дерево , которое является максимально эффективным пространством. Он должен быть полностью заполнен на всех уровнях, кроме последнего. Однако, если последний уровень не завершен, все узлы дерева должны быть «как можно дальше слева». [1]
- Идеальные м -ичного дерево является полным [1] м -ичного деревом , в котором все узлы листьев находятся на одной и ту же глубину. [2]
Свойства m -арных деревьев
- Для m -арного дерева с высотой h верхняя граница максимального количества листьев равна.
- Высота ч из м -ичного дерева не включает в себя корневой узел, с деревом , содержащим только корневой узел , имеющим высоту 0.
- Высота дерева равна максимальной глубине D любого узла в дереве.
- Общее количество узлов в идеальных м -ичного деревом является, а высота h равна
- По определению Big-Ω максимальная глубина
- Высота полного m -арного дерева с n узлами равна.
- Общее количество возможных m -арных деревьев с n узлами равно(это каталонское число ). [3]
Методы обхода матричных деревьев
Обход m -арного дерева очень похож на обход двоичного дерева. Обход предварительного порядка идет к родительскому, левому поддереву и правому поддереву, а для обхода пост-порядка - по левому поддереву, правому поддереву и родительскому узлу. Для обхода по порядку, поскольку существует более двух дочерних узлов на узел при m> 2 , необходимо определить понятие левого и правого поддеревьев. Один из распространенных методов создания левых / правых поддеревьев - разделить список дочерних узлов на две группы. Определяя порядок на m дочерних элементах узла, первый узлы будут составлять левое поддерево и узлы составят правильное поддерево.
Преобразование m -арного дерева в двоичное дерево
Использование массива для представления м- кратного дерева является неэффективным, так как большинство из узлов в практических применениях содержит менее м детей. В результате это приводит к разреженному массиву с большим неиспользуемым пространством в памяти. Преобразование произвольного матричного дерева в двоичное только увеличило бы высоту дерева на постоянный коэффициент и не повлияло бы на общую временную сложность наихудшего случая. Другими словами, поскольку .
Сначала мы связываем все непосредственные дочерние узлы данного родительского узла вместе, чтобы сформировать список ссылок. Затем мы сохраняем ссылку от родителя к первому (то есть самому левому) дочернему элементу и удаляем все остальные ссылки на остальные дочерние элементы. Мы повторяем этот процесс для всех дочерних элементов (если у них есть дочерние элементы), пока мы не обработаем все внутренние узлы и не повернем дерево на 45 градусов по часовой стрелке. Полученное дерево является искомым двоичным деревом, полученным из данного m -арного дерева.
Способы хранения м -арных деревьев
Массивы
m- мерные деревья также могут храниться в порядке в ширину как неявная структура данных в массивах , и если дерево является полным m- мерным деревом, этот метод не тратит впустую места. В этом компактном расположении, если узел имеет индекс i , его c -й дочерний элемент в диапазоне {1, ..., m } находится по индексу, в то время как его родитель (если есть) находится по индексу (при условии, что корень имеет нулевой индекс, что означает массив, начинающийся с 0). Преимущество этого метода заключается в более компактном хранении и лучшей локализации ссылок , особенно во время обхода перед заказом. Пространственная сложность этого метода составляет.
На основе указателя
Каждый узел будет иметь внутренний массив для хранения указателей на каждый из своих дети:
По сравнению с реализацией на основе массивов этот метод реализации имеет более высокую пространственную сложность, чем .
Перечень м- ичных деревьев
Перечисление всех возможных m- мерных деревьев полезно во многих дисциплинах как способ проверки гипотез или теорий. Правильное представление м- ичных дерева объектов может значительно упростить процесс генерации. Можно построить представление битовой последовательности, используя поиск в глубину m -арного дерева с n узлами, указывающими на присутствие узла в данном индексе, используя двоичные значения. Например, битовая последовательность x = 1110000100010001000 представляет 3-арное дерево с n = 6 узлами, как показано ниже.
Проблема с этим представлением состоит в том, что перечисление всех битовых строк в лексикографическом порядке будет означать, что две последовательные строки могут представлять два дерева, которые лексикографически очень разные. Таким образом, перечисление над двоичными строками не обязательно приводит к упорядоченной генерации всех м- ичных дерев. [4] Лучшее представление основано на целочисленной строке, которая указывает количество нулей между последовательными единицами, известная как простая нулевая последовательность . простая нулевая последовательность, соответствующая битовой последовательности где j - количество нулей, необходимых в конце последовательности, чтобы строка имела соответствующую длину. Например,представляет собой простое представление нулевой последовательности на приведенном выше рисунке. Более компактное представление 00433 :, которая называется нулевой последовательностью , дублирующие основания которой не могут быть смежными. Это новое представление позволяет построить следующую допустимую последовательность в. Простая нулевая последовательность действительна, если
В таблице ниже показан список всех допустимых простых нулевых последовательностей всех 3- мерных деревьев с 4 узлами:
Начиная с нижнего правого угла таблицы (т. Е. С «000»), существует шаблон магистрали, который управляет генерацией возможных упорядоченных деревьев, начиная с «000» до «006». Базовый шаблон для этой группы («00X») изображен ниже, где дополнительный узел добавляется в позиции, помеченные «x».
После того, как исчерпаны все возможные позиции в шаблоне магистрали, новый шаблон будет построен путем смещения 3-го узла на одну позицию вправо, как показано ниже, и такое же перечисление будет происходить до тех пор, пока не будут исчерпаны все возможные позиции, помеченные «X».
Возвращаясь к таблице перечисления всех m -арных деревьев, где а также , мы можем легко наблюдать очевидный скачок от «006» к «010», который можно тривиально объяснить алгоритмически, как показано ниже:
Псевдокод для этого перечисления приведен ниже: [4]
Процедура NEXT () если для всех я тогда законченный еще если я <п-1, то конец, если для конец, если конец
Беспетельное перечисление
Алгоритм генерации, который принимает время наихудшего случая называется без цикла, поскольку временная сложность не может включать цикл или рекурсию. Loopless перечисление м- ичных деревьев называется loopless , если после инициализации, он генерирует последовательные объекты дерева в. Для заданного в м- кратного дерева T с являясь одним из его узлов и это ребенок, вращение влево-t на делается путем создания корневой узел, и делая и все его поддеревья являются дочерними элементами , дополнительно присваиваем оставил большинство детей к и самый правый ребенок остается привязанным к нему, пока повышается до root, как показано ниже:
Convert an m-ary tree to left-tree
for : for : while t child of node at depth : L-t rotation at nodes at depth i end while end for end for
Вращения вправо-т при г является обратным этой операции. Левая цепь из Т представляет собой последовательность такие узлы, что это корень и все узлы, кроме иметь одного ребенка, подключенного к левому краю (т. е. ) указатель. Любое м- ичного дерево может быть преобразовано в левой цепи дерево , используя последовательность конечных левой т вращений для т от 2 до м . В частности, это можно сделать, выполнив вращение влево-t на каждом узле. пока все его поддерево становится нулевым на каждой глубине. Затем последовательность из числа вращений влево-t, выполненных на глубине i, обозначенная какопределяет кодовое слово из более м- ичного дерева , которые могут быть извлечены с помощью выполнения той же самой последовательности правой т вращений.
Пусть кортеж из представляют количество оборотов L-2 , L-3 , ..., Lm- поворотов, которые произошли в корне (т. е. i = 1). Тогда,- количество оборотов Lt, необходимых на глубине i .
Захват количества левых вращений на каждой глубине - это способ кодирования m- мерного дерева. Таким образом, перечисление всех возможных законных кодировок поможет нам сгенерировать все m -арные деревья для заданных m и n . Но не всепоследовательности m неотрицательных целых чисел представляют действительное m-арное дерево. Последовательностьнеотрицательные целые числа являются действительным представлением м- ичного дерева тогда и только тогда , когда [5]
Лексикографически наименьшее представление кодового слова m-арного с n узлами - это все нули, а наибольшее - n-1 , за которым следует m-1 ноль справа.
Initialization
c[i] to zero for all i from 1 to p[i] set to for i from 1 to n Termination Condition Terminate when c[1] = n-1Procedure NEXT [5] if then end if if then else end ifend
Заявление
Одно из применений m -арного дерева - создание словаря для проверки допустимых строк. Для этого пусть m будет равно количеству допустимых алфавитов (например, количеству букв английского алфавита ) с корнем дерева, представляющим начальную точку. Точно так же каждый из дочерних элементов может иметь до m дочерних элементов, представляющих следующий возможный символ в строке. Таким образом, символы на путях могут представлять действительные ключи, отмечая конечный символ ключей как «конечный узел». Например, в приведенном ниже примере «at» и «и» являются допустимыми ключевыми строками с «t» и «d», отмеченными как конечные узлы. Терминальные узлы могут хранить дополнительную информацию, которая будет связана с данным ключом. Есть аналогичные способы построения такого словаря с использованием B-дерева , Octree и / или trie .
Смотрите также
Рекомендации
- ^ a b «Упорядоченные деревья» . Проверено 19 ноября 2012 года .
- ^ Блэк, Пол Э. (20 апреля 2011 г.). "идеальное к-арное дерево" . Национальный институт стандартов и технологий США . Проверено 10 октября 2011 года .
- ^ Грэм, Рональд Л .; Knuth, Donald E .; Паташник, Орен (1994). Конкретная математика: фонд компьютерных наук (2-е издание) . AIP.
- ^ а б Baronaigien, Доминик Руланс ван (2000). «Генерация карильных деревьев без зацикливания». Журнал алгоритмов . 35 (1): 100–107. DOI : 10.1006 / jagm.1999.1073 .
- ^ а б Корш, Джеймс Ф (1994). «Беспетельная генерация k-арных древовидных последовательностей». Письма об обработке информации . Эльзевир. 52 (5): 243–247. DOI : 10.1016 / 0020-0190 (94) 00149-9 .
- Сторер, Джеймс А. (2001). Введение в структуры данных и алгоритмы . Birkhäuser Boston. ISBN 3-7643-4253-6.