(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
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 4 May 2007.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "k-ary tree", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 4 May 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/karyTree.html
