Java Reference
In-Depth Information
23.9
The height of full or complete trees.
In later chapters, the height of trees that are either full or
complete will be important in our discussions of efficiency. Figure 23-7 shows some full trees that
get progressively taller. We can compute the number of nodes that each tree contains as a function
of its height. Beginning at the root of the tallest tree in the figure, we can see that the number of
nodes at each level doubles as we move toward the leaves. The total number of nodes in this tallest
tree is 1
+
2
+
4
+
8
+
16, or, 31. In general, the number of nodes in a full binary tree is
h
-
¦
1
2
i
i
=
0
where
h
is the tree's height. This sum is equal to 2
h
-
1. You can convince yourself that this result is
true by examining Figure 23-7, and you can prove it as an exercise by using mathematical induction.
FIGURE 23-7
The number of nodes in a full binary tree as a function of the
tree's height
Full Tree
Height
Number
of Nodes
2
1
1
1
1
2
2
2
3
1
2
3
3
7
1
2
4
4
15
1
Number of
nodes per level
1
2
4
8
16
2
5
5
31
1
Now, if
n
is the number of nodes in a full tree, we have the following results:
n
=
2
h
-
1
2
h
=
n
+
1
h
=
log
2
(
n
+
1)
That is, the height of a full tree that has
n
nodes is log
2
(
n
+
1).
