In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary, k-way or generic tree) is an arborescence (or, for some authors, an ordered tree) in which each node has no more than m children. A binary tree is an important case where m = 2; similarly, a ternary tree is one where m = 3.
Types of m-ary trees A full m-ary tree is an m-ary tree where within each level every node has 0 or m children. A complete m-ary tree (or, less commonly, a perfect m-ary tree) is a full m-ary tree in which all leaf nodes are at the same depth.
Properties of m-ary trees For an m-ary tree with height h, the upper bound for the maximum number of leaves is m h {\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 N {\displaystyle N} in a complete m-ary tree is ∑ i = 0 h m i = m h + 1 − 1 m − 1 {\textstyle \sum _{i=0}^{h}m^{i}={\frac {m^{h+1}-1}{m-1}}} , while the height h is
m h + 1 − 1 m − 1 ≥ N > m h − 1 m − 1 m h + 1 ≥ ( m − 1 ) ⋅ N + 1 > m h h + 1 ≥ log m ( ( m − 1 ) ⋅ N + 1 ) > h h ≥ ⌈ log m ( ( m − 1 ) ⋅ N + 1 ) − 1 ⌉ . {\displaystyle {\begin{aligned}&{\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{aligned}}} By the definition of Big-Ω, the maximum depth
D = h ≥ ⌈ log m ( ( m − 1 ) ⋅ N + 1 ) − 1 ⌉ = O ( log m n ) = O ( log n / log m ) . {\displaystyle D=h\geq \left\lceil \log _{m}((m-1)\cdot N+1)-1\right\rceil =O(\log _{m}n)=O(\log n/\log m).}
… excerpt ends here. Continue reading the full article.
