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 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 ${\frac {k^{h+1}-1}{k-1}}$ , while the height h is

\left\lceil\log_k (k - 1) + \log_k (\text{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: The 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) \cdot (\text{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 in range [1..c] is found at index $k\cdot i+c$ , while its parent (if any) is found at index $\left\lfloor {\frac {i-1}{k}}\right\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.

References

1 2 "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, Ph.D, 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	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast

Spatial data partitioning trees	Ball 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 Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

This article is issued from Wikipedia - version of the 6/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.