м -арное дерево - m-ary tree

Пример m-арного дерева с m = 5

В теории графов , м -ичное дерево (также известный как к -ичному или K -WAY дерева) является корневым деревом , в котором каждый узел имеет не более м детей. Бинарное дерево представляет собой особый случай , когда т = 2, а тройная дерево другой случай с т = 3 , что ограничивает его ребенок до трех.

Типы м- арных деревьев

Полные м -ичного дерево представляет собой м - позиционное дерево , где на каждом уровень каждый узел имеет 0 или т детей.
Полные м -ичного дерево представляет собой м - позиционное дерево , которое является максимально эффективным пространством. Он должен быть полностью заполнен на всех уровнях, кроме последнего. Однако, если последний уровень не завершен, все узлы дерева должны быть «как можно дальше слева».
Идеальные м -ичного дерево является полными м -ичного деревом , в котором все узлы листьев находятся на одной и ту же глубину.

Свойства m -арных деревьев

Для m -арного дерева с высотой h верхняя граница максимального количества листьев равна . ${\ displaystyle m ^ {h}}$
Высота ч из м -ичного дерева не включает в себя корневой узел, с деревом , содержащим только корневой узел , имеющим высоту 0.
Высота дерева равна максимальной глубине D любого узла в дереве.
Общее количество узлов в совершенном m- мерном дереве равно , а высота h равна ${\ displaystyle N}$ ${\ textstyle \ sum _ {я = 0} ^ {h} m ^ {i} = {\ frac {m ^ {h + 1} -1} {m-1}}}$ ${\ displaystyle {\ begin {align} & {\ frac {m ^ {h + 1} -1} {m-1}} \ geq N> {\ frac {m ^ {h} -1} {m-1 }} \\ [8pt] & m ^ {h + 1} \ geq (m-1) \ cdot N + 1> m ^ {h} \\ [8pt] & h + 1 \ geq \ log _ {m} \ left ((m-1) \ cdot N + 1 \ right)> h \\ [8pt] & h \ geq \ left \ lceil \ log _ {m} ((m-1) \ cdot N + 1) -1 \ right \ rceil. \ end {выровнено}}}$ По определению Big-Ω максимальная глубина ${\ Displaystyle D = час \ geq \ влево \ lceil \ log _ {m} ((m-1) \ cdot N + 1) -1 \ вправо \ rceil = O (\ log _ {m} n) = O ( \ log n / \ log m)}$
Высота полного m -арного дерева с n узлами составляет . ${\ textstyle \ lfloor \ журнал _ {m} ((m-1) \ cdot n) \ rfloor}$
Общее количество возможных m- мерных деревьев с n узлами равно (что является каталонским числом ). ${\ textstyle C_ {n} = {\ frac {1} {(m-1) n + 1}} \ cdot {\ binom {m \ cdot n} {n}}}$

Методы обхода матричных деревьев

Обход m -арного дерева очень похож на обход двоичного дерева. Обход предварительного порядка идет к родительскому, левому поддереву и правому поддереву, а для обхода пост-порядка - по левому поддереву, правому поддереву и родительскому узлу. Для обхода по порядку, поскольку существует более двух дочерних узлов на узел при m> 2 , необходимо определить понятие левого и правого поддеревьев. Один из распространенных методов создания левых / правых поддеревьев - разделить список дочерних узлов на две группы. Определяя порядок на m дочерних элементах узла, первые узлы будут составлять левое поддерево, а узлы будут составлять правое поддерево. ${\ textstyle \ {1, \ точки, \ lfloor {\ frac {m} {2}} \ rfloor \}}$ ${\ textstyle \ {\ lceil {\ frac {m} {2}} \ rceil, \ dots, m \}}$

Преобразование m -арного дерева в двоичное дерево

Пример преобразования м-арного дерева в бинарное. м = 6

Использование массива для представления м- кратного дерева является неэффективным, так как большинство из узлов в практических применениях содержит менее м детей. В результате это приводит к разреженному массиву с большим неиспользуемым пространством в памяти. Преобразование произвольного матричного дерева в двоичное только увеличило бы высоту дерева на постоянный коэффициент и не повлияло бы на общую временную сложность наихудшего случая. Другими словами, поскольку . ${\ textstyle О (\ журнал _ {м} п) \ экв О (\ журнал _ {2} п)}$ ${\ textstyle \ log _ {2} m \ cdot \ log _ {m} n = {\ frac {\ log m} {\ log 2}} \ cdot {\ frac {\ log n} {\ log m}} = \ log _ {2} n}$

Сначала мы связываем все непосредственные дочерние узлы данного родительского узла вместе, чтобы сформировать список ссылок. Затем мы сохраняем ссылку от родителя к первому (то есть самому левому) дочернему элементу и удаляем все остальные ссылки на остальные дочерние элементы. Мы повторяем этот процесс для всех дочерних элементов (если у них есть дочерние элементы), пока мы не обработаем все внутренние узлы и не повернем дерево на 45 градусов по часовой стрелке. Полученное дерево является искомым двоичным деревом, полученным из данного m -арного дерева.

Способы хранения м -арных деревьев

Массивы

Пример хранения m-арного дерева с m = 3 в массиве

m- мерные деревья также могут храниться в порядке в ширину как неявная структура данных в массивах , и если дерево является полным m- мерным деревом, этот метод не тратит впустую места. В этом компактном расположении, если узел имеет индекс i , его c -й дочерний элемент в диапазоне {1,…, m } находится по индексу , а его родительский узел (если есть) находится по индексу (при условии, что корень имеет нулевой индекс. , что означает массив, начинающийся с 0). Преимущество этого метода заключается в более компактном хранении и лучшей локализации ссылок , особенно во время обхода перед заказом. Пространственная сложность этого метода составляет . ${\ Displaystyle м \ cdot я + с}$ ${\ textstyle \ left \ lfloor {\ frac {i-1} {m}} \ right \ rfloor}$ ${\ Displaystyle О (м ^ {п})}$

На основе указателя

У каждого узла будет внутренний массив для хранения указателей на каждого из его дочерних узлов : ${\ displaystyle m}$

Реализация m-арного дерева на основе указателя, где m = 4.

По сравнению с реализацией на основе массивов этот метод реализации имеет более высокую пространственную сложность . ${\ Displaystyle О (м \ cdot п)}$

Перечень м- ичных деревьев

Перечисление всех возможных m- мерных деревьев полезно во многих дисциплинах как способ проверки гипотез или теорий. Правильное представление м- ичных дерева объектов может значительно упростить процесс генерации. Можно построить представление битовой последовательности, используя поиск в глубину m -арного дерева с n узлами, указывающими на присутствие узла в данном индексе, используя двоичные значения. Например, битовая последовательность x = 1110000100010001000 представляет 3-арное дерево с n = 6 узлами, как показано ниже.

3-арное дерево с битовой последовательностью 1110000100010001000 и простой нулевой последовательностью 004433

Проблема с этим представлением состоит в том, что перечисление всех битовых строк в лексикографическом порядке будет означать, что две последовательные строки могут представлять два дерева, которые лексикографически очень разные. Таким образом, перечисление над двоичными строками не обязательно приводит к упорядоченной генерации всех м- ичных дерев. Лучшее представление основано на целочисленной строке, указывающей количество нулей между последовательными единицами, известной как простая нулевая последовательность . - это простая нулевая последовательность, соответствующая битовой последовательности, где j - количество нулей, необходимых в конце последовательности, чтобы строка имела соответствующую длину. Например, это простое представление нулевой последовательности на приведенном выше рисунке. Более компактное представление 00433 - это нулевая последовательность , в которой повторяющиеся основания не могут быть смежными. Это новое представление позволяет построить следующую допустимую последовательность в . Простая нулевая последовательность действительна, если ${\ textstyle S = s_ {1}, s_ {2}, \ dots, s_ {n-1}}$ ${\ textstyle 10 ^ {s_ {1}} 10 ^ {s_ {2}} \ ldots 10 ^ {s_ {n-1}} 10 ^ {j}}$ ${\ displaystyle 1110000100010001000 \ эквив 10 ^ {0} 10 ^ {0} 10 ^ {4} 10 ^ {4} 10 ^ {3} \ эквив 00433}$ ${\ displaystyle 0 ^ {2} 4 ^ {1} 3 ^ {2}}$ ${\ displaystyle O (1)}$

{\ displaystyle \ sum _ {i = 1} ^ {i = j} s_ {i} \ leq (m-1) j \ qquad \ forall j \ leq n-1.}

То есть количество нулей в битовой последовательности m -арного дерева не может превышать общее количество нулевых указателей (т. Е. Указателей без прикрепленных к ним дочерних узлов). Это суммирование накладывает ограничение на узлы, так что есть место для добавления без создания недопустимой структуры (т.е. наличия доступного нулевого указателя для присоединения к нему последнего узла).

{\ displaystyle n-1}

{\ Displaystyle п ^ {т} ч}

В таблице ниже показан список всех допустимых простых нулевых последовательностей всех 3- мерных деревьев с 4 узлами:

222	200	111	033	013
221	132	110	032	012
220	131	105	031	011
213	130	104	030	010
212	123	103	024	006
211	122	102	023	005
210	121	101	022	004
204	120	100	021	003
203	114	042	020	002
202	113	041	015	001
201	112	040	014	000

Начиная с нижнего правого угла таблицы (т. Е. С «000»), существует шаблон магистрали, который управляет генерацией возможных упорядоченных деревьев, начиная с «000» до «006». Базовый шаблон для этой группы («00X») изображен ниже, где дополнительный узел добавляется в позиции, помеченные «x».

После того, как исчерпаны все возможные позиции в шаблоне магистрали, новый шаблон будет построен путем сдвига 3-го узла на одну позицию вправо, как показано ниже, и такое же перечисление будет происходить до тех пор, пока не будут исчерпаны все возможные позиции, помеченные «X».

Возвращаясь к таблице перечисления всех m -арных деревьев, где и , мы можем легко наблюдать очевидный скачок от «006» к «010», который можно тривиально объяснить алгоритмически, как показано ниже: ${\ displaystyle m = 3}$ ${\ displaystyle n = 4}$

Псевдокод для этого перечисления приведен ниже:

Procedure NEXT(s₁, s₂, …, s_n−1)
    if s_i = 0 for all i then
        finished
    else
        i ← max {i | s_i > 0}
        s_i ← s_i − 1
        if i < n − 1 then
            s_i ← (i + 1) ⋅ (m − 1) − sum(s_j)
        end if
        for j ← i + 2, i + 3, …, n − 1
            s_j ← k − 1
    end if
end

Беспетельное перечисление

Алгоритм генерации, использующий время наихудшего случая, называется без циклов, поскольку временная сложность не может включать цикл или рекурсию. Loopless перечисление м- ичных деревьев называется loopless , если после инициализации, он генерирует последовательные объекты дерево в . Для заданной в м- кратного дерево T с является одним из его узлов и его -ю ребенок, вращение влево-т на это делаются путем корневой узел, и делая и все его поддерев дитяти , дополнительно припишем оставленное большинство дочерних элементов to и самый правый дочерний элемент остается прикрепленным к нему, пока он получает root- права , как показано ниже: ${\ displaystyle O (1)}$ ${\ displaystyle O (1)}$ ${\ displaystyle a}$ ${\ displaystyle d}$ ${\ displaystyle t}$ ${\ displaystyle a}$ ${\ displaystyle d}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle m-1}$ ${\ displaystyle d}$ ${\ displaystyle a}$ ${\ displaystyle d}$ ${\ displaystyle d}$

Convert an m-ary tree to left-tree
    for i = 1...n:
         for t = 2...m:
             while t child of node at depth i ≠ 1:
                L-t rotation at nodes at depth i
              end while
          end for
     end for

Вращения вправо-т при г является обратным этой операции. Левая цепь из Т представляет собой последовательность узлов , таких , что является корнем , и все узлы , за исключением еще одного ребенок связан с их крайним левым (то есть ) указатель. Любое м- ичного дерево может быть преобразовано в левой цепи дерево , используя последовательность конечных левой т вращений для т от 2 до м . В частности, это можно сделать, выполняя вращение влево-t на каждом узле до тех пор, пока все его поддерево не станут нулевыми на каждой глубине. Затем последовательность числа лево-т вращений выполняется на глубине я обозначается определяет кодовое слово из в м- ичного дерева , которое может быть восстановлено путем выполнения той же самой последовательности правой т вращений. ${\ displaystyle x_ {1}, x_ {2}, \ dots, x_ {n}}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {n}}$ ${\ displaystyle m [1]}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle m-1}$ ${\ displaystyle c_ {i}}$

Пусть набор представляет количество оборотов L-2, оборотов L-3 , ..., Lm- поворотов, которые произошли в корне (т. Е. I = 1). Тогда это количество Lt- поворотов, необходимых на глубине i. . ${\ displaystyle m-1}$ ${\ displaystyle c_ {1}, c_ {2}, \ dots, c_ {m-1}}$ ${\ Displaystyle с _ {(я-1) (м-1) + т-1}}$

Захват количества левых вращений на каждой глубине - это способ кодирования m- мерного дерева. Таким образом, перечисление всех возможных законных кодировок поможет нам сгенерировать все m -арные деревья для заданных m и n . Но не все последовательности из m неотрицательных целых чисел представляют собой допустимое m-арное дерево. Последовательность неотрицательных целых чисел является действительным представлением м- ичного дерева , если и только если ${\ displaystyle c_ {i}}$ ${\ Displaystyle (п-1) \ cdot (м-1) +1}$

{\ Displaystyle \ сумма _ {я = J} ^ {п} \ сумма _ {т = 2} ^ {м} с _ {(я-1) (м-1) + т-1} \ qquad \ leq nj, \ qquad \ forall j \ in 0 \ dots n.}

Лексикографически наименьшее представление кодового слова m-арного с n узлами - это все нули, а наибольшее - это n −1 единица, за которой следует m −1 ноль справа.

Initialization
    c[i] to zero for all i from 1 to n⋅(k − 1)
    p[i] set to n − 1 for i from 1 to n
    sum ← 0
    j ← m − 1

Termination Condition
    Terminate when c[1] = n − 1

Procedure NEXT
    sum ← sum + 1 − c[j + 1]
    c[j] ← c[j] + 1
    if p[q[j]] > p[q[j + 1]] + 1 then
        p[q[j]] ← p[q[j + 1]] + 1
    end if
    p[q[j + c[j]]] ← p[q[j]]
    c[j + 1] ← 0
    if sum = p[q[j]] then
        j ← j − 1
    else
        p[n] ← sum
        j ← m − 1
    end if
end

Заявление

Одно из применений m -арного дерева - создание словаря для проверки допустимых строк. Для этого пусть m будет равно количеству допустимых алфавитов (например, количеству букв английского алфавита ) с корнем дерева, представляющим начальную точку. Точно так же каждый из дочерних элементов может иметь до m дочерних элементов, представляющих следующий возможный символ в строке. Таким образом, символы на путях могут представлять действительные ключи, отмечая конечный символ ключей как «конечный узел». Например, в приведенном ниже примере «at» и «и» являются допустимыми ключевыми строками с «t» и «d», отмеченными как конечные узлы. Терминальные узлы могут хранить дополнительную информацию, которая будет связана с данным ключом. Есть аналогичные способы построения такого словаря с использованием B-дерева , Octree и / или trie .

Смотрите также

Внешние ссылки

N -арные деревья, Бруно Р. Прейсс, Ph.D, P.Eng.

Languages

In other projects