.. _Kary: .. raw:: html .. |--| unicode:: U+2013 .. en dash .. |---| unicode:: U+2014 .. em dash, trimming surrounding whitespace :trim: .. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :author: Cliff Shaffer :topic: General Trees K-ary Tree Implementations ========================== K-ary Tree Implementations -------------------------- :math:`K`-ary trees are trees whose internal nodes all have exactly :math:`K` children. Thus, a full binary tree is a 2-ary tree. The PR Quadtree discussed in Module :numref:`` is an example of a 4-ary tree. Because :math:`K`-ary tree nodes have a fixed number of children, unlike general trees, they are relatively easy to implement. In general, :math:`K`-ary trees bear many similarities to binary trees, and similar implementations can be used for :math:`K`-ary tree nodes. Note that as :math:`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 :math:`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. .. raw:: html .. TODO:: :type: Slideshow Slideshow of Book Figure 6.16: shows full and complete \Kary\ trees for K=3. In practice, most applications of \Kary\ trees 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 :math:`K`-ary trees. Equivalent theorems to those in Module numref`` regarding the number of ``null`` pointers in a :math:`K`-ary tree and the relationship between the number of leaves and the number of internal nodes in a :math:`K`-ary tree can be derived. We can also store a complete :math:`K`-ary tree in an array, using simple formulas to compute a node's relations in a manner similar to that used in Section :numref:``.