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 3 September 2019.
HTML page formatted Fri Sep 6 15:26:10 2019.

Cite this as:
Paul E. Black, "k-ary tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 3 September 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/karyTree.html