.. _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://algoviz.org/OpenDSA for more details. .. Copyright (c) 2012-2013 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. 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:``.