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 ^[1] k-ary tree in which all leaf nodes are at the same depth.^[2]
A complete k-ary tree is a k-ary tree which is maximally space efficient. It must be completely filled on every level (meaning that each node on that level has k children) 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". ^[1]

Properties of k-ary trees

For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$ .
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 total number of nodes in a perfect k-ary tree is $\left\lfloor\frac{k^{h+1} - 1}{k-1}\right\rfloor$ , while the height h is

\left\lceil\log_k (k - 1) + \log_k (\mathit{number\_of\_nodes}) - 1\right\rceil.

Note : A Tree containing only one node is taken to be of height 0 for this formula to be applicable.

Note : Formula is not applicable for a 2-ary tree with height 0, as the ceiling operator approximates and simplifies the true formula, which can be described as

\log_k [(k - 1) * \mathit{number\_of\_nodes} + 1] - 1, k \ge 2.

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 is found at index $k*i+1+c$ , while its parent (if any) is found at index $\left \lfloor \frac{i-1}{k} \right \rfloor$ (assuming the root has index zero). This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal.

References

↑ 1.0 1.1 "Ordered Trees". Retrieved 19 November 2012.
↑ Black, Paul E. (20 April 2011). "perfect k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 10 October 2011.

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, P.Eng.

Tree data structures

Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red-black Scapegoat Splay T Treap UB Weight-balanced

Heaps	Binary Binomial Fibonacci Leftist Pairing Skew Van Emde Boas

Tries	Hash Radix Suffix Ternary search X-fast Y-fast

Spatial data partitioning trees	BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X

Other trees	Cover Exponential Fenwick Finger Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top