27.10.1. K-ary Tree Implementations¶

$K$-ary trees are trees whose internal nodes all have exactly $K$ children. Thus, a full binary tree is a 2-ary tree. The PR Quadtree discussed in Module <Spatial> is an example of a 4-ary tree. Because $K$-ary tree nodes have a fixed number of children, unlike general trees, they are relatively easy to implement. In general, $K$-ary trees bear many similarities to binary trees, and similar implementations can be used for $K$-ary tree nodes. Note that as $K$ becomes large, the potential number of null pointers grows, and the difference between the required sizes for internal nodes and leaf nodes increases. Thus, as $K$ becomes larger, the need to choose separate implementations for the internal and leaf nodes becomes more pressing.

Full K-ary trees and complete K-ary trees are analogous to full and complete binary trees, respectively.

Many of the properties of binary trees extend to $K$-ary trees. Equivalent theorems to those in Module numref`<BinSpace>` regarding the number of null pointers in a $K$-ary tree and the relationship between the number of leaves and the number of internal nodes in a $K$-ary tree can be derived. We can also store a complete $K$-ary tree in an array, using simple formulas to compute a node’s relations in a manner similar to that used in Section <CompleteTree>.