Java Reference
In-Depth Information
A
A
B
B
(A)
(B)
A
A
EMPTY
EMPTY
B
B
(C)
(D)
Figure5.2
Two different binary trees. (a) A binary tree whose root has a non-
empty left child. (b) A binary tree whose root has a non-empty right child. (c) The
binary tree of (a) with the missing right child made explicit. (d) The binary tree
of (b) with the missing left child made explicit.
(A)
(B)
Figure5.3
Examples of full and complete binary trees. (a) This tree is full (but
not complete). (b) This tree is complete (but not full).
not full. The heap data structure (Section 5.5) is an example of a complete binary
tree. The Huffman coding tree (Section 5.6) is an example of a full binary tree.
5.1.1
The Full Binary Tree Theorem
Some binary tree implementations store data only at the leaf nodes, using the inter-
nal nodes to provide structure to the tree. More generally, binary tree implementa-
tions might require some amount of space for internal nodes, and a different amount
for leaf nodes. Thus, to analyze the space required by such implementations, it is
useful to know the minimum and maximum fraction of the nodes that are leaves in
a tree containing n internal nodes.
Unfortunately, this fraction is not fixed. A binary tree of n internal nodes might
have only one leaf. This occurs when the internal nodes are arranged in a chain
ending in a single leaf as shown in Figure 5.4. In this case, the number of leaves
is low because each internal node has only one non-empty child. To find an upper
bound on the number of leaves for a tree of n internal nodes, first note that the upper
