.. raw:: html

   <script>ODSA.SETTINGS.MODULE_SECTIONS = [];</script>

.. _Kary:


.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Kary";ODSA.SETTINGS.MODULE_LONG_NAME = "K-ary Tree Implementations";ODSA.SETTINGS.MODULE_CHAPTER = "modules"; ODSA.SETTINGS.BUILD_DATE = "2022-11-29 16:52:11"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| 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:`<Spatial>` 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

   <a id="todo0"></a>

.. 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`<BinSpace>` 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:`<CompleteTree>`.