NIST

k-ary tree

(data structure)

Definition: A tree with no more than k children for each node.

Also known as k-way tree.

Generalization (I am a kind of ...)
tree, multiway tree.

Specialization (... is a kind of me.)
binary tree, ternary search tree.

Note: A k-ary tree may be thought of as a multiway tree limited to k children.

Each node may be implemented as an array, a linked list, a tree (see binary tree representation of trees), or more elaborate schemes such as mentioned at multiway tree.

In an array implementation for a tree without insertions, nodes might be overlapped in one big array, since many entries are note used. Such an improvement is also referred to as "packed" or "compressed".

Author: PEB

More information

explanation and example


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 4 May 2007.
HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:
Paul E. Black, "k-ary tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 May 2007. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/karyTree.html