Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

Complete Trees

 

The preceding chapter introduces the idea of a perfect tree (see Definition gif). Complete trees and perfect trees are closely related, yet quite distinct. As pointed out in the preceding chapter, a perfect binary tree of height h has exactly tex2html_wrap_inline65527 internal nodes. Since, the only permissible values of n are

displaymath65519

there is no perfect binary tree which contains, say 2, 4, 5, or 6 nodes.

However, we want a data structure that can hold an arbitrary number of objects so we cannot use a perfect binary tree. Instead, we use a complete binary tree, which is defined as follows:

Definition (Complete Binary Tree)  A complete binary tree   of height tex2html_wrap_inline63063, is a binary tree tex2html_wrap_inline65533 with the following properties.
  1. If h=0, tex2html_wrap_inline63843 and tex2html_wrap_inline63845.
  2. For h>0 there are two possibilities:
    1. tex2html_wrap_inline63147 is a perfect binary tree of height h-1 and tex2html_wrap_inline63149 is a complete binary tree of height h-1; or
    2. tex2html_wrap_inline63147 is a complete binary tree of height h-1 and tex2html_wrap_inline63149 is a perfect binary tree of height h-2.

Figure gif shows an example of a complete binary tree of height four. Notice that the left subtree of node 1 is a complete binary tree of height three; and the right subtree is a perfect binary tree of height two. This corresponds to case 2 (b) of Definition gif. Similarly, the left subtree of node 2 is a perfect binary tree of height two; and the right subtree is a complete binary tree of height two. This corresponds to case 2 (a) of Definition gif.

   figure23468
Figure: A complete binary tree.

Does there exist a complete binary with exactly n nodes for every integer n>0? The following theorem addresses this question indirectly by defining the relationship between the height of a complete tree and the number of nodes it contains.

Theorem  A complete binary tree of height tex2html_wrap_inline63063 contains at least tex2html_wrap_inline63187 and at most tex2html_wrap_inline63175 nodes.

extbfProof First, we prove the lower bound by induction. Let tex2html_wrap_inline65569 be the minimum number of nodes in a complete binary tree of height h. To prove the lower bound we must show that tex2html_wrap_inline65573.

Base Case There is exactly one node in a tree of height zero. Therefore, tex2html_wrap_inline65575.

Inductive Hypothesis Assume that tex2html_wrap_inline65573 for tex2html_wrap_inline63073, for some tex2html_wrap_inline60883. Consider the complete binary tree of height k+1 which has the smallest number of nodes. Its left subtree is a complete tree of height k having the smallest number of nodes and its right subtree is a perfect tree of height k-1.

From the inductive hypothesis, there are tex2html_wrap_inline58271 nodes in the left subtree and there are exactly tex2html_wrap_inline65591 nodes in the perfect right subtree. Thus,

eqnarray23653

Therefore, by induction tex2html_wrap_inline65573 for all tex2html_wrap_inline63063, which proves the lower bound.

Next, we prove the upper bound by induction. Let tex2html_wrap_inline65597 be the maximum number of nodes in a complete binary tree of height h. To prove the upper bound we must show that tex2html_wrap_inline65601.

Base Case There is exactly one node in a tree of height zero. Therefore, tex2html_wrap_inline65603.

Inductive Hypothesis Assume that tex2html_wrap_inline65601 for tex2html_wrap_inline63073, for some tex2html_wrap_inline60883. Consider the complete binary tree of height k+1 which has the largest number of nodes. Its left subtree is a perfect tree of height k and its right subtree is a complete tree of height k having the largest number of nodes.

There are exactly tex2html_wrap_inline65617 nodes in the perfect left subtree. From the inductive hypothesis, there are tex2html_wrap_inline65617 nodes in the right subtree. Thus,

eqnarray23665

Therefore, by induction tex2html_wrap_inline65601 for all tex2html_wrap_inline63063, which proves the upper bound.

It follows from Theorem gif that there exists exactly one complete binary tree that contains exactly n internal nodes for every integer tex2html_wrap_inline58503. It also follows from Theorem gif that the height of a complete binary tree containing n internal nodes is tex2html_wrap_inline65631.

Why are we interested in complete trees? As it turns out, complete trees have some useful characteristics. For example, in the preceding chapter we saw that the internal path length of a tree, i.e., the sum of the depths of all the internal nodes, determines the average time for various operations. A complete binary tree has the nice property that it has the smallest possible internal path length:

Theorem  The internal path length of a binary tree with n nodes is at least as big as the internal path length of a complete binary tree with n nodes.

extbfProof Consider a binary tree with n nodes that has the smallest possible internal path length. Clearly, there can only be one node at depth zero--the root. Similarly, at most two nodes can be at depth one; at most four nodes can be at depth two; and so on. Therefore, the internal path length of a tree with n nodes is always at least as large as the sum of the first n terms in the series

displaymath65520

But this summation is precisely the internal path length of a complete binary tree!

Since the depth of the average node in a tree is obtained by dividing the internal path length of the tree by n, Theorem gif tells us that complete trees are the best possible in the sense that the average depth of a node in a complete tree is the smallest possible. But how small is small? That is, is does the average depth grow logarithmically with n. The following theorem addresses this question:

Theorem  The internal path length   of a complete binary tree with n nodes is

displaymath65521

extbfProof The proof of Theorem gif is left as an exercise for the reader (Exercise gif).

From Theorem gif we may conclude that the internal path length of a complete tree is tex2html_wrap_inline59353. Consequently, the depth of the average node in a complete tree is tex2html_wrap_inline59347.


next up previous index

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