k-ary tree

In graph theory, a k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.

Types of k-ary trees

• A full k-ary tree is a k-ary tree where within each level every node has either 0 or k children.
• A perfect k-ary tree is a full k-ary tree in which all leaf nodes are at the same depth.
• A complete k-ary tree is a k-ary tree which is maximally space efficient. It must be completely filled on every level except for the last level. However, if the last level is not complete, then all nodes of the tree must be "as far left as possible".

Properties of k-ary trees

• For a k-ary tree with height h, the upper bound for the maximum number of leaves is [math]\displaystyle{ k^h }[/math].
• The height h of a k-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 maximun depth D of any node in the tree
• The total number of nodes [math]\displaystyle{ N }[/math] in a perfect k-ary tree is [math]\displaystyle{ \sum_{i=0}^h k^i = \frac{k^{h+1} - 1}{k-1} }[/math], while the height h is

[math]\displaystyle{ \frac{k^{h+1} - 1}{k-1} \geq N \gt \frac{k^{h} - 1}{k-1} }[/math]

[math]\displaystyle{ k^{h+1} \geq (k - 1) \cdot N + 1 \gt k^{h} }[/math]

[math]\displaystyle{ h+1 \geq log_k \left((k - 1) \cdot N + 1\right) \gt h }[/math]

[math]\displaystyle{ h \gt = \left\lceil\log_k ((k - 1) \cdot N + 1) - 1\right\rceil. }[/math]

By the definition of Big-Ω, the maximum depth

[math]\displaystyle{ D = h \gt = \left\lceil\log_k ((k - 1) \cdot N + 1) - 1\right\rceil =O(log_k(n)) = O(log(n)/log(k)) }[/math]

Methods for storing k-ary trees

Arrays

k-ary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete k-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..k] is found at index [math]\displaystyle{ k\cdot i+c }[/math], while its parent (if any) is found at index [math]\displaystyle{ \left \lfloor \frac{i-1}{k} \right \rfloor }[/math] (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.

See also

• Left-child right-sibling binary tree
• Binary tree

References

• Storer, James A. (2001). An Introduction to Data Structures and Algorithms. Birkhäuser Boston. ISBN 3-7643-4253-6. 

External links

• N-ary trees, Bruno R. Preiss, Ph.D, P.Eng.