Close Window

Show Source |    | About   «  27.9. General Tree Implementations   ::   Contents   ::   28.1. Limits to Computing  »

27.10. K-ary Tree Implementations

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 20.1 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.



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 12.16.

   «  27.9. General Tree Implementations   ::   Contents   ::   28.1. Limits to Computing  »

Close Window