K-ary Tree Implementations¶
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 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.
Todo
| type: | Slideshow |
|---|
Slideshow of Book Figure 6.16: shows full and complete Karytrees for K=3. In practice, most applications of Karytrees limit them to be either full or complete.
Full and complete 3-ary trees. (a)~This tree is full (but not complete). (b)~This tree is complete (but not full).}{ThreeTree}
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 .
