M-ary tree

Properties of m-ary trees

• For an m-ary tree with height h, the upper bound for the maximum number of leaves is ${\displaystyle m^h}$.
• The height h of an m-ary tree does not include the root node, with a tree containing only a root node having a height of 0.
• The height of a tree is equal to the maximum depth D of any node in the tree.
• The total number of nodes ${\displaystyle N}$ in a complete m-ary tree is $\sum _{i=0}^h{m}^i=\frac{m^{h+1}-1}{m-1}$, while the height h is

$${\displaystyle \begin{array}{cc}& \frac{m^{h+1}-1}{m-1}\ge N>\frac{m^h-1}{m-1}\\ & m^{h+1}\ge (m-1)\cdot N+1>m^h\\ & h+1\ge {\log }_m\left((m-1)\cdot N+1\right)>h\\ & h\ge \lceil {\log }_m((m-1)\cdot N+1)-1\rceil .\end{array}}$$ By the definition of Big-Ω, the maximum depth $${\displaystyle D=h\ge \lceil {\log }_m((m-1)\cdot N+1)-1\rceil =O({\log }_{m}n)=O(\log n/\log m).}$$

• The height of a complete m-ary tree with n nodes is $\lfloor {\log }_m((m-1)\cdot n)\rfloor$.
• The total number of possible m-ary tree with n nodes is $C_n=\frac{1}{(m-1)n+1}\cdot (\genfrac{}{}{0ex}{}{m\cdot n}{n})$ (which is a Catalan number).

Traversal methods for m-ary trees

Traversing a m-ary tree is very similar to traversing a binary tree. The pre-order traversal goes to parent, left subtree and the right subtree, and for traversing post-order it goes by left subtree, right subtree, and parent node. For traversing in-order, since there are more than two children per node for m > 2, one must define the notion of left and right subtrees. One common method to establish left/right subtrees is to divide the list of children nodes into two groups. By defining an order on the m children of a node, the first $\{1,\dots ,\lfloor \frac{m}{2}\rfloor \}$ nodes would constitute the left subtree and $\{\lceil \frac{m}{2}\rceil ,\dots ,m\}$ nodes would constitute the right subtree.

Convert a m-ary tree to binary tree

Using an array for representing a m-ary tree is inefficient, because most of the nodes in practical applications contain less than m children. As a result, this fact leads to a sparse array with large unused space in the memory. Converting an arbitrary m-ary tree to a binary tree would only increase the height of the tree by a constant factor and would not affect the overall worst-case time complexity. In other words, $O({\log }_{m}n)\equiv O({\log }_{2}n)$ since ${\log }_{2}m\cdot {\log }_{m}n=\frac{\log m}{\log 2}\cdot \frac{\log n}{\log m}={\log }_{2}n$.

First, we link all the immediate children nodes of a given parent node together in order to form a link list. Then, we keep the link from the parent to the first (i.e., the leftmost) child and remove all the other links to the rest of the children. We repeat this process for all the children (if they have any children) until we have processed all the internal nodes and rotate the tree by 45 degrees clockwise. The tree obtained is the desired binary tree obtained from the given m-ary tree.

Methods for storing m-ary trees

Arrays

m-ary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete m-ary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its c-th child in range {1,…,m} is found at index ${\displaystyle m\cdot i+c}$, while its parent (if any) is found at index $\lfloor \frac{i-1}{m}\rfloor$ (assuming the root has index zero, meaning a 0-based array). This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal. The space complexity of this method is ${\displaystyle O(m^n)}$.

Pointer-based

Each node would have an internal array for storing pointers to each of its ${\displaystyle m}$ children:

Compared to array-based implementation, this implementation method has superior space complexity of ${\displaystyle O(m\cdot n)}$.

Enumeration of m-ary trees

Listing all possible m-ary trees is useful in many disciplines as a way of checking hypotheses or theories. Proper representation of m-ary tree objects can greatly simplify the generation process. One can construct a bit sequence representation using the depth-first search of a m-ary tree with n nodes indicating the presence of a node at a given index using binary values. For example, the bit sequence x=1110000100010001000 is representing a 3-ary tree with n=6 nodes as shown below.

The problem with this representation is that listing all bit strings in lexicographic order would mean two successive strings might represent two trees that are lexicographically very different. Therefore, enumeration over binary strings would not necessarily result in an ordered generation of all m-ary trees. A better representation is based on an integer string that indicates the number of zeroes between successive ones, known as Simple Zero Sequence. $S=s_1,s_2,\dots ,s_{n-1}$ is a Simple Zero Sequence corresponding to the bit sequence ${10}^{s_1}{10}^{s_2}\dots {10}^{s_{n-1}}{10}^j$ where j is the number of zeroes needed at the tail end of the sequence to make the string have the appropriate length. For example, ${\displaystyle 1110000100010001000\equiv {10}^0{10}^0{10}^4{10}^4{10}^3\equiv 00433}$ is the simple zero sequence representation of the above figure. A more compact representation of 00433 is ${\displaystyle 0^2{4}^1{3}^2}$, which is called zero sequence, which duplicate bases cannot be adjacent. This new representation allows to construct a next valid sequence in ${\displaystyle O(1)}$. A simple zero sequence is valid if $${\displaystyle \sum _{i=1}^{i=j}{s}_i\le (m-1)j\mathrm{\forall }j\le n-1.}$$That is to say that number of zeros in the bit sequence of a m-ary tree cannot exceed the total number of null pointers (i.e., pointers without any child node attached to them). This summation is putting restriction on ${\displaystyle n-1}$ nodes so that there is room for adding the ${\displaystyle n^{t}h}$ without creating an invalid structure (i.e. having an available null pointer to attached the last node to it).

The table below shows the list of all valid simple zero sequences of all 3-ary trees with 4 nodes:

Starting from the bottom right of the table (i.e., "000"), there is a backbone template that governs the generation of the possible ordered trees starting from "000" to "006". The backbone template for this group ("00X") is depicted below, where an additional node is added in the positions labeled "x".

Once one has exhausted all possible positions in the backbone template, a new template will be constructed by shifting the 3rd node one position to the right as depicted below, and the same enumeration would occur until all possible positions labeled "X" is exhausted.

Going back to the table of enumeration of all m-ary trees, where ${\displaystyle m=3}$ and ${\displaystyle n=4}$, we can easily observe the apparent jump from "006" to "010" can be explained trivially in an algorithmic fashion as depicted below:

The pseudocode for this enumeration is given below:

<b id="mwASI">Procedure</b> NEXT(<i id="mwASM">s</i><sub id="mwASQ">1</sub>, <i id="mwASU">s</i><sub id="mwASY">2</sub>, …, <i id="mwASc">s</i><sub id="mwASg"><i id="mwASk">n</i>−1</sub>) <b id="mwASo">if</b> <i id="mwASs">s<sub id="mwASw">i</sub></i> = 0 for all <i id="mwAS0">i</i> <b id="mwAS4">then</b> finished <b id="mwAS8">else</b> <i id="mwATA">i</i> ← max {<i id="mwATE">i</i> | <i id="mwATI">s<sub id="mwATM">i</sub></i> > 0} <i id="mwATQ">s<sub id="mwATU">i</sub></i> ← <i id="mwATY">s<sub id="mwATc">i</sub></i> − 1 <b id="mwATg">if</b> <i id="mwATk">i</i> < <i id="mwATo">n</i> − 1 <b id="mwATs">then</b> <i id="mwATw">s<sub id="mwAT0">i</sub></i> ← (<i id="mwAT4">i</i> + 1) ⋅ (<i id="mwAT8">m</i> − 1) − sum(<i id="mwAUA">s<sub id="mwAUE">j</sub></i>) <b id="mwAUI">end if</b> <b id="mwAUM">for</b> <i id="mwAUQ">j</i> ← <i id="mwAUU">i</i> + 2, <i id="mwAUY">i</i> + 3, …, <i id="mwAUc">n</i> − 1 <i id="mwAUg">s<sub id="mwAUk">j</sub></i> ← <i id="mwAUo">k</i> − 1 <b id="mwAUs">end if</b> <b id="mwAUw">end</b>

Loopless enumeration

A generation algorithm that takes ${\displaystyle O(1)}$ worst-case time are called loopless since the time complexity cannot involve a loop or recursion. Loopless enumeration of m-ary trees is said to be loopless if after initialization, it generates successive tree objects in ${\displaystyle O(1)}$. For a given a m-ary tree T with ${\displaystyle a}$ being one of its nodes and ${\displaystyle d}$ its ${\displaystyle t}$-th child, a left-t rotation at ${\displaystyle a}$ is done by making ${\displaystyle d}$ the root node, and making ${\displaystyle b}$ and all of its subtrees a child of ${\displaystyle a}$, additionally we assign the ${\displaystyle m-1}$ left most children of ${\displaystyle d}$ to ${\displaystyle a}$ and the right most child of ${\displaystyle d}$ stays attached to it while ${\displaystyle d}$ is promoted to root, as shown below:

<b id="mwAWY">Convert an m-ary tree to left-tree</b> <b id="mwAWc">for</b> <i id="mwAWg">i</i> = 1...<i id="mwAWk">n</i>: <b id="mwAWo">for</b> <i id="mwAWs">t</i> = 2...<i id="mwAWw">m</i>: <b id="mwAW0">while</b> <i id="mwAW4">t</i> child of node at depth <i id="mwAW8">i</i> ≠ 1: L-t rotation at nodes at depth <i id="mwAXA">i</i> <b id="mwAXE">end while</b> <b id="mwAXI">end for</b> <b id="mwAXM">end for</b>

A right-t rotation at d is the inverse of this operation. The left chain of T is a sequence of ${\displaystyle x_1,x_2,\dots ,x_n}$ nodes such that ${\displaystyle x_1}$ is the root and all nodes except ${\displaystyle x_n}$ have one child connected to their left most (i.e., ${\displaystyle m[1]}$) pointer. Any m-ary tree can be transformed to a left-chain tree using sequence of finite left-t rotations for t from 2 to m. Specifically, this can be done by performing left-t rotations on each node ${\displaystyle x_i}$ until all of its ${\displaystyle m-1}$ sub-tree become null at each depth. Then, the sequence of number of left-t rotations performed at depth i denoted by ${\displaystyle c_i}$ defines a codeword of a m-ary tree that can be recovered by performing the same sequence of right-t rotations.

Let the ${\displaystyle m-1}$ tuple of ${\displaystyle c_1,c_2,\dots ,c_{m-1}}$ represent the number of L-2 rotations, L-3 rotations, ..., L-m rotations that has occurred at the root (i.e., i=1).Then, ${\displaystyle c_{(i-1)(m-1)+t-1}}$ is the number of L-t rotations required at depth i.

Capturing counts of left-rotations at each depth is a way of encoding an m-ary tree. Thus, enumerating all possible legal encoding would helps us to generate all the m-ary trees for a given m and n. But, not all ${\displaystyle c_i}$ sequences of m non-negative integers represent a valid m-ary tree. A sequence of ${\displaystyle (n-1)\cdot (m-1)+1}$ non-negative integers is a valid representation of a m-ary tree if and only if $${\displaystyle \sum _{i=j}^n\sum _{t=2}^m{c}_{(i-1)(m-1)+t-1}\le n-j,\mathrm{\forall }j\in 0\dots n.}$$

Lexicographically smallest code-word representation of a m-ary with n nodes is all zeros and the largest is n−1 ones followed by m−1 zero on its right.

<b id="mwAag">Initialization</b> c[i] to zero for all i from 1 to <i id="mwAak">n</i>⋅(<i id="mwAao">k</i> − 1) p[i] set to <i id="mwAas">n</i> − 1 for i from 1 to n <i id="mwAaw">sum</i> ← 0 <i id="mwAa0">j</i> ← <i id="mwAa4">m</i> − 1 <b id="mwAa8">Termination Condition</b> Terminate when c[1] = <i id="mwAbA">n</i> − 1 <b id="mwAbE">Procedure</b> NEXT<sup about="#mwt88" class="mw-ref reference" id="cite_ref-karyrotationgeneration_8-1" rel="dc:references" typeof="mw:Extension/ref" data-mw='{"name":"ref","attrs":{"name":"karyrotationgeneration"}}'><a href="./M-ary_tree#cite_note-karyrotationgeneration-8" id="mwAbI"><span class="mw-reflink-text" id="mwAbM"><span class="cite-bracket" id="mwAbQ">[</span>8<span class="cite-bracket" id="mwAbU">]</span></span></a></sup> <i id="mwAbY">sum</i> ← <i id="mwAbc">sum</i> + 1 − <i id="mwAbg">c</i>[<i id="mwAbk">j</i> + 1] <i id="mwAbo">c</i>[j] ← <i id="mwAbs">c</i>[<i id="mwAbw">j</i>] + 1 <b id="mwAb0">if</b> <i id="mwAb4">p</i>[<i id="mwAb8">q</i>[<i id="mwAcA">j</i>]] > <i id="mwAcE">p</i>[<i id="mwAcI">q</i>[<i id="mwAcM">j</i> + 1]] + 1 <b id="mwAcQ">then</b> <i id="mwAcU">p</i>[<i id="mwAcY">q</i>[<i id="mwAcc">j</i>]] ← <i id="mwAcg">p</i>[<i id="mwAck">q</i>[<i id="mwAco">j</i> + 1]] + 1 <b id="mwAcs">end if</b> <i id="mwAcw">p</i>[<i id="mwAc0">q</i>[<i id="mwAc4">j</i> + <i id="mwAc8">c</i>[<i id="mwAdA">j</i>]]] ← <i id="mwAdE">p</i>[<i id="mwAdI">q</i>[<i id="mwAdM">j</i>]] <i id="mwAdQ">c</i>[<i id="mwAdU">j</i> + 1] ← 0 <b id="mwAdY">if</b> <i id="mwAdc">sum</i> = <i id="mwAdg">p</i>[<i id="mwAdk">q</i>[<i id="mwAdo">j</i>]] <b id="mwAds">then</b> <i id="mwAdw">j</i> ← <i id="mwAd0">j</i> − 1 <b id="mwAd4">else</b> <i id="mwAd8">p</i>[<i id="mwAeA">n</i>] ← <i id="mwAeE">sum</i> <i id="mwAeI">j</i> ← <i id="mwAeM">m</i> − 1 <b id="mwAeQ">end if</b> <b id="mwAeU">end</b>

Application

One of the applications of m-ary tree is creating a dictionary for validation of acceptable strings. In order to do that, let m be equal to the number of valid alphabets (e.g., number of letters of the English alphabet) with the root of the tree representing the starting point. Similarly, each of the children can have up to m children representing the next possible character in the string. Thus, characters along the paths can represent valid keys by marking the end character of the keys as "terminal node". For example, in the example below "at" and "and" are valid key strings with "t" and "d" marked as terminal nodes. Terminal nodes can store extra information to be associated with a given key. There are similar ways to building such a dictionary using B-tree, Octree and/or trie.