Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Complete N-ary Trees

The definition for complete binary trees can be easily extended to trees with arbitrary fixed degree tex2html_wrap_inline65441 as follows:

Definition (Complete N-ary Tree)  A complete N-ary tree   of height tex2html_wrap_inline62845, is an N-ary tree tex2html_wrap_inline65453 with the following properties.
  1. If h=0, tex2html_wrap_inline65457 for all i, tex2html_wrap_inline65461.
  2. For h>0 there exists a j, tex2html_wrap_inline65467 such that
    1. tex2html_wrap_inline62605 is a perfect binary tree of height h-1 for all tex2html_wrap_inline65473;
    2. tex2html_wrap_inline62627 is a complete binary tree of height h-1; and,
    3. tex2html_wrap_inline62605 is a perfect binary tree of height h-2 for all i:j<i<N.

Note that while it is expressed in somewhat different terms, the definition of a complete N-ary tree is consistent with the definition of a binary tree for N=2. Figure gif shows an example of a complete ternary (N=3) tree.

   figure23663
Figure: A complete ternary tree.

Informally, a complete tree is a tree in which all the levels are full except for the bottom level and the bottom level is filled from left to right. For example in Figure gif, the first three levels are full. The fourth level which comprises nodes 14-21 is partially full and has been filled from left to right.

The main advantage of using complete binary trees is that they can be easily stored in an array. Specifically, consider the nodes of a complete tree numbered consecutively in level-order  as they are in Figures gif and gif. There is a simple formula that relates the number of a node with the number of its parent and the numbers of its children.

Consider the case of a complete binary tree. The root node is node 1 and its children are nodes 2 and 3. In general, the children of node i are 2i and 2i+1. Conversely, the parent of node i is tex2html_wrap_inline65499. Figure gif illustrates this idea by showing how the complete binary tree shown in Figure gif is mapped into an array.

   figure23963
Figure: Array representation of a complete binary tree.

A remarkable characteristic of complete trees is that filling the bottom level from left to right corresponds to adding elements at the end of the array! Thus, a complete tree containing n nodes occupies the first n consecutive array positions.

The array subscript calculations given above can be easily generalized to complete N-ary trees. Assuming that the root occupies position 1 of the array, its N children occupy positions 2, 3, ..., N+1. In general, the children of node i occupy positions

displaymath65435

and the parent of node i is found at

displaymath65436


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.