The binary tree of Figure 7.18(a) is balanced; the binary tree of (b) is not. Balanced trees are important in information retrieval applications; they will be discussed fully in Chapter 9. In information retrieval, the data are stored at the tree's nodes. The depth of the tree determines the search times for retrieval and, with balanced trees, the tree's depth is controllable and can be limited, as will be shown in Chapter 9. Here we consider the "worst case" of such trees.
A binary tree is a Fibonacci tree if it is balanced and has the minimum number of nodes among all balanced binary trees with its depth. Fibonacci trees represent the worst case for balanced trees, since they contain the fewest nodes (and hence the least storage capacity) among all balanced trees with a specified depth. The binary tree in Figure 7.19 is a Fibonacci tree of depth 4. This is a Fibonacci tree because it is balanced, and no balanced binary tree with a depth of 4 has fewer than 7 nodes. Any complete binary tree of depth 4, for example, will not be a Fibonacci tree because, although balanced, it will have more than the minimum number of nodes (7) for this depth.
Figure 7.19 A Fibonacci Tree of Depth 4
The Fibonacci numbers are a well-known sequence of integers defined by the following recursive definition:
F0 = 0, F1 = 1,
Fn = Fn-1 + Fn-2 for n > 1
The first few are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . . These numbers seem to appear in the most unexpected places. In computer science they often arise in the analysis of algorithms. The number of nodes in a Fibonacci tree of depth d can be shown to be Fd+2 - 1 (see Exercise 34b). For example, if d is 4, then Fd+2 - 1 = F6 - 1 = 8 - 1 = 7.
Example 7.6
The task now is to develop an algorithm to generate a Fibonacci tree of depth d. If possible, apply the method of recursion to find a recursive definition of the solution. n
Clearly, if d = 0, there is only one Fibonacci tree of depth d, the null binary tree. If d = 1, there is only one Fibonacci tree of depth d, the tree with one node?/FONT>its root.
Any subtree of a balanced binary tree must also be balanced, or else the tree itself would not be balanced. Any subtree of a Fibonacci tree must therefore be balanced and must also be a Fibonacci tree. Otherwise it could be replaced by a Fibonacci tree of that depth with fewer nodes. This is the key to the recursive solution. We can now construct a Fibonacci tree of depth d > 1 as follows: Since d > 1, the Fibonacci tree must have a root, and its two subtrees must be Fibonacci trees. One (say, the right) must have depth d - 1 (so the tree itself has depth d). The other, the left subtree, must be a Fibonacci tree and must differ in depth from d - 1 by at most 1. Hence it must have depth d - 2 or d - 1. It has just been demonstrated that a Fibonacci tree of depth d - 1 has at least one subtree of depth d - 2. Hence the Fibonacci tree of depth d - 1 has more nodes than the Fibonacci tree of depth d - 2. Thus the left subtree of the Fibonacci tree being constructed must have depth d - 2. (Why?) This gives the complete recursive solution.
To construct a Fibonacci tree of depth d:
1. If d = 0, then construct the null tree,
2. else if d = 1, then construct the tree with one node, its root,
3. else if d > 1, then
a. construct a root,
b. construct a Fibonacci tree of depth d - 2 and make it the left subtree of the root, and
c. construct a Fibonacci tree of depth d - 1 and make it the right subtree of the root.
The explicit constructions are given by the algorithm's statements 1 and 2 for d = 0 and d = 1. Statement 3 gives the implicit construction for d > 1. You should apply this definition to the case d = 4, and confirm that it constructs the example given earlier of a Fibonacci tree of depth 4. It should also be clear that other Fibonacci trees of depth 4 exist.
The recursive program can be written directly from the definition.
Recursive Version 1?/FONT>Linked Representation with Records Stored in an Array
For concreteness, we have chosen to implement the constructed tree using a linked representation. The tree itself will be stored in the records array (Section 7.4.2) with the fields of a record being info, leftptr, and rightptr.Records is assumed to be a global variable. When the routine returns, tree will point to its root record in the array representation.
Using implementation with pointer variables for the binary tree, the procedure becomes the following.fibonaccitree (d, ptree)
/* Creates a Fibonacci tree, tree, of depth d. */
int d;
binarytreepointer *ptree;
{binarytreepointer tl, tr, avail ( );
*ptree = avail ( );
if (d == 0)
*ptree = NULL;
else if (d == 1)
{records [*ptree].leftptr = NULL;
records [*ptree].rightptr = NULL;
}
else
{fibonaccitree (d-2,&tl);
records [*ptree].leftptr = tl;
fibonaccitree (d-1,&tr);
records [*ptree].rightptr = tr;
}
}