## 3.5 Optimal Binary Search Trees Next we obtain an algorithm for determining the optimal way of organizing a set of items in a binary search tree. Before discussing what kind of organization is considered optimal, let's review such trees. For any node in a binary tree, the subtree whose root is the left child of the node is called the ***left subtree*** of the node. The left subtree of the root of the tree is called the left subtree of the tree. The ***right subtree*** is defined analogously. Definition A ***binary search tree*** is a binary tree of items (ordinarily called keys), that come from an ordered set, such that 1. Each node contains one key. 2. The keys in the left subtree of a given node are less than or equal to the key in that node. 3. The keys in the right subtree of a given node are greater than or equal to the key in that node. [Figure 3.10](#ch03fig10) shows two binary search trees, each with the same keys. In the tree on the left, look at the right subtree of the node containing "Ralph." That subtree contains "Tom," "Ursula," and "Wally," and these names are all greater than "Ralph" according to an alphabetic ordering. Although, in general, a key can occur more than once in a binary search tree, for simplicity we assume that the keys are distinct. [](fig3-10_0.jpg) Figure 3.10: Two binary search trees. The ***depth*** of a node in a tree is the number of edges in the unique path from the root to the node. This is also called the ***level*** of the node in the tree. Usually we say that a node *has* a depth and that the node is *at* a level. For example, in the tree on the left in [Figure 3.10](#ch03fig10), the node containing "Ursula" has a depth of 2. Alternatively, we could say that the node is at level 2. The root has a depth of 0 and is at level 0. The ***depth*** of a tree is the maximum depth of all nodes in the tree. The tree on the left in [Figure 3.10](#ch03fig10) has a depth of 3, whereas the tree on the right has a depth of 2. A binary tree is called ***balanced*** if the depth of the two subtrees of every node never differ by more than 1. The tree on the left in [Figure 3.10](#ch03fig10) is not balanced because the left subtree of the root has a depth of 0, and the right subtree has a depth of 2. The tree on the right in [Figure 3.10](#ch03fig10) is balanced. Ordinarily, a binary search tree contains records that are retrieved according to the values of the keys. Our goal is to organize the keys in a binary search tree so that the average time it takes to locate a key is minimized. (See Section A.3.2 for a discussion of the average.) A tree that is organized in this fashion is called ***optimal***. It is not hard to see that, if all keys have the same probability of being the ***search key***, the tree on the right in [Figure 3.10](#ch03fig10) is optimal. We are concerned with the case where the keys do not have the same probability. An example of this case would be a search of one of the trees in [Figure 3.10](#ch03fig10) for a name picked at random from people in the United States. Because "Tom" is a more common name than "Ursula," we would assign a greater probability to "Tom." (See [Section A.8.1](LiB0100.html#1340) in [Appendix A](LiB0093.html#1281) for a discussion of randomness.) We will discuss the case in which it is known that the search key is in the tree. A generalization to the case where it may not be in the tree is investigated in the exercises. To minimize the average search time, we need to know the time complexity of locating a key. Therefore, before proceeding, let's write and analyze an algorithm that searches for a key in a binary search tree. The algorithm uses the following data types: ``` struct nodetype { keytype key; nodetype* left; nodetype* right; }; typedef nodetype* node_pointer; ``` This declaration means that a node\_pointer variable is a pointer to a nodetype record. That is, its value is the memory address of such a record. Algorithm 3.8: Search Binary Tree****Problem: Determine the node containing a key in a binary search tree. It is assumed that the key is in the tree. Inputs: a pointer *tree* to a binary search tree and a key *keyin.* Outputs: a pointer *p* to the node containing the key. ``` void search (node_pointer tree, keytype keyin, node_pointer& p) { bool found; p = tree; found = false; while (! found) if (p->key == keyin) found = true; else if (keyin < p-> key); p = p-> left; // Advance to left child. else p = p-> right; // Advance to right child. } ``` **** The number of comparisons done by procedure *search* to locate a key is called the ***search time.*** Our goal is to determine a tree for which the average search time is minimal. As discussed in [Section 1.2](LiB0009.html#36), we assume that comparisons are implemented efficiently. With this assumption, only one comparison is done in each iteration of the **while** loop in the previous algorithm. Therefore, the search time for a given key is  where *depth* (*key*) is the depth of the node containing the key. For example, because the depth of the node containing "Ursula" is 2 in the left tree in [Figure 3.10](#ch03fig10), the search time for "Ursula" is  Let *Key*1, *Key*2,…, *Keyn* be the *n* keys in order, and let *pi* be the probability that *Keyi* is the search key. If *ci* is the number of comparisons needed to find *Keyi* in a given tree, the average search time for that tree is  This is the value we want to minimize. Example 3.7****[Figure 3.11](#ch03fig11) shows the five different trees when *n* = 3. The actual values of the keys are not important. The only requirement is that they be ordered. If  the average search times for the trees in [Figure 3.11](#ch03fig11) are: 1. 3 (0.7) + 2 (0.2) + 1 (0.1) = 2.6 2. 2 (0.7) + 3 (0.2) + 1 (0.1) = 2.1 3. 2 (0.7) + 1 (0.2) + 2 (0.1) = 1.8 4. 1 (0.7) + 3 (0.2) + 2 (0.1) = 1.5 5. 1 (0.7) + 2 (0.2) + 3 (0.1) = 1.4 The fifth tree is optimal. **** [](fig3-11_0.jpg) Figure 3.11: The possible binary search trees when there are three keys. In general, we cannot find an optimal binary search tree by considering all binary search trees because the number of such trees is at least exponential in *n.* We prove this by showing that if we just consider all binary search trees with a depth of *n* − 1, we have an exponential number of trees. In a binary search tree with a depth of *n* - 1, the single node at each of the *n* − 1 levels beyond the root can be either to the left or to the right of its parent, which means there are two possibilities at each of those levels. This means that the number of different binary search trees with a depth of *n* − 1 is 2*n*−1. Dynamic programming will be used to develop a more efficient algorithm. To that end, suppose that keys *Keyi* through *Keyj* are arranged in a tree that minimizes  where *cm* is the number of comparisons needed to locate *Keym* in the tree. We will call such a tree ***optimal*** for those keys and denote the optimal value by *A* \[*i*\] \[*j*\]. Because it takes one comparison to locate a key in a tree containing one key, *A* \[*i*\] \[*i*\] = *pi.* Example 3.8****Suppose we have three keys and the probabilities in [Example 3.7](#ch03ex15). That is,  To determine *A* \[2\] \[3\] we must consider the two trees in [Figure 3.12](#ch03fig12). For those two trees we have the following: 1. 1 (*p*2) + 2 (*p*3) = 1 (0.2) + 2 (0.1) = 0.4 2. 2 (*p*2) + 1 (*p*3) = 2 (0.2) + 1 (0.1) = 0.5 [](fig3-12_0.jpg) Figure 3.12: The binary search trees composed of *Key*2 and *Key*3. The first tree is optimal, and  **** Notice that the optimal tree obtained in [Example 3.8](#ch03ex16) is the right subtree of the root of the optimal tree obtained in [Example 3.7](#ch03ex15). Even if this tree was not the exact same one as that right subtree, the average time spent searching in it would have to be the same. Otherwise, we could substitute it for that subtree, resulting in a tree with a smaller average search time. In general, any subtree of an optimal tree must be optimal for the keys in that subtree. Therefore, the principle of optimality applies. Next, let tree 1 be an optimal tree given the restriction that *Key*1 is at the root, tree 2 be an optimal tree given the restriction that *Key*2 is at the root, …, tree *n* be an optimal tree given the restriction that *Keyn* is at the root. For 1 ≤ *k* ≤ *n*, the subtrees of tree *k* must be optimal, and therefore the average search times in these subtrees are as depicted in [Figure 3.13](#ch03fig13). This figure also shows that for each *m* ≠ *k* it takes exactly one more comparison (the one at the root) to location *Keym* in tree *k* than it does to locate that key in the subtree that contains it. This one comparison adds 1 x *pm* to the average search time for *Keym* in tree *k.* We've established that the average search time for tree *k* is given by [](figu121_1_0.jpg) [](fig3-13_0.jpg) Figure 3.13: Optimal binary search tree given that *Keyk* is at the root. which equals  Because one of the *k* trees must be optimal, the average search time for the optimal tree is given by  where *A* \[1\] \[0\] and *A* \[*n* + 1\] \[*n*\] are defined to be 0. Although the sum of the probabilities in this last expression is clearly 1, we have written it as a sum because we now wish to generalize the result. To that end, there is nothing in the previous discussion that requires that the keys be *Key*1 through *Keyn.* That is, in general, the discussion pertains to *Keyi* through *Keyj*, where *i* < *j.* We have therefore derived the following:  Using Equality 3.6, we can write an algorithm that determines an optimal binary search tree. Because *A* \[*i*\] \[*j*\] is computed from entries in the *i*th row but to the left of *A* \[*i*\] \[*j*\] and from entries in the *j*th column but beneath *A* \[*i*\] \[*j*\], we proceed by computing in sequence the values on each diagonal (as was done in [Algorithm 3.6](LiB0028.html#301)). Because the steps in the algorithm are so similar to those in [Algorithm 3.6](LiB0028.html#301), we do not include an example illustrating these steps. Rather, we simply give the algorithm followed by a comprehensive example showing the results of applying the algorithm. The array *R* produced by the algorithm contains the indices of the keys chosen for the root at each step. For example, *R* \[1\] \[2\] is the index of the key in the root of an optimal tree containing the first two keys, and *R* \[2\] \[4\] is the index of the key in the root of an optimal tree containing the second, third, and fourth keys. After analyzing the algorithm, we will discuss how to build an optimal tree from *R.* Algorithm 3.9: Optimal Binary Search Tree****Problem: Determine an optimal binary search tree for a set of keys, each with a given probability of being the search key. Inputs: *n*, the number of keys, and an array of real numbers *p* indexed from 1 to *n*, where *p* \[*i*\] is the probability of searching for the *i*th key. Outputs: A variable *minavg*, whose value is the average search time for an optimal binary search tree; and a two-dimensional array *R* from which an optimal tree can be constructed. *R* has its rows indexed from 1 to *n* + 1 and its columns indexed from 0 to *n. R* \[*i*\] \[*j*\] is the index of the key in the root of an optimal tree containing the *i*th through the *j*th keys. ``` void optsearchtree (int n, const float p [], float& minavg, index R [] []) { index i, j, k, diagonal; float A [1 .. n + 1] [0 .. n]; ```  **** ****Analysis of Algorithm 3.9 Every-Case Time Complexity (Optimal Binary Search Tree)Basic operation: The instructions executed for each value of *k.* They include a comparison to test for the minimum. The value of  does not need to be computed from scratch each time. In the exercises you will find an efficient way to compute these sums. Input size: *n*, the number of keys. The control of this algorithm is almost identical to that in [Algorithm 3.6](LiB0028.html#301). The only difference is that, for given values of *diagonal* and *i*, the basic operation is done *diagonal* + 1 times. An analysis like the one of [Algorithm 3.6](LiB0028.html#301) establishes that  **** The following algorithm constructs a binary tree from the array *R.* Recall that *R* contains the indices of the keys chosen for the root at each step. Algorithm 3.10: Build Optimal Binary Search Tree****Problem: Build an optimal binary search tree. Inputs: *n*, the number of keys, an array *Key* containing the *n* keys in order, and the array *R* produced by [Algorithm 3.9](#ch03ex17). *R* \[*i*\] \[*j*\] is the index of the key in the root of an optimal tree containing the *i*th through the *j*th keys. Outputs: a pointer *tree* to an optimal binary search tree containing the *n* keys. ``` node_pointer tree (index i, j) { index k; node_pointer p; k = R[i] [j]; if (k == 0) return NULL; else{ p = new nodetype; p-> key = Key [k]; p-> left = tree (i, k - 1); p-> right = tree (k + 1, j); return p; } } ``` **** The instruction *p* = **new nodetype** gets a new node and puts its address in *p.* Following our convention for recursive algorithms, the parameters *n, Key*, and *R* are not inputs to function *tree.* If the algorithm were implemented by defining *n, Key*, and *R* globally, a pointer *root* to the root of an optimal binary search tree is obtained by calling *tree* as follows:  We did not illustrate the steps in [Algorithm 3.9](#ch03ex17) because it is similar to [Algorithm 3.6](LiB0028.html#301) (Minimum Multiplications). Likewise, we will not illustrate the steps in [Algorithm 3.10](#ch03ex18) because this algorithm is similar to [Algorithm 3.7](LiB0028.html#306) (Print Optimal Order). Rather, we provide one comprehensive example showing the results of applying both [Algorithm 3.9](#ch03ex17) and [Algorithm 3.10](#ch03ex18). Example 3.9****Supposed we have the following values of the array *Key*:  and  The arrays *A* and *R* produced by [Algorithm 3.9](#ch03ex17) are shown in [Figure 3.14](#ch03fig14), and the tree created by [Algorithm 3.10](#ch03ex18) is shown in [Figure 3.15](#ch03fig15). The minimal average search time is 7/4. [](fig3-14_0.jpg) Figure 3.14: The arrays *A* and *R*, produced when [Algorithm 3.9](#ch03ex17) is applied to the instance in [Example 3.9](#ch03ex19). [](fig3-15_0.jpg) Figure 3.15: The tree produced when [Algorithm 3.9](#ch03ex17) and [Algorithm 3.10](#ch03ex18) are applied to the instance in [Example 3.9](#ch03ex19). Notice that *R*\[1\] \[2\] could be 1 or 2. The reason is that either of these indices could be the index of the root in an optimal tree containing only the first two keys. Therefore, both of these indices give the minimum value of *A* \[1\] \[2\] in [Algorithm 3.9](#ch03ex17), which means that either could be chosen for *R* \[1\] \[2\]. **** The previous algorithm for determining an optimal binary search tree is from Gilbert and Moore (1959). A Θ (*n*2) algorithm can be obtained using the dynamic programming speed-up method in Yao (1982).