When we need to search for an element of a given value v in such a tree, we do it recursively in the following manner. If the tree is empty, the search ends in failure. If the tree is notempty, we compare v with the tree’s root K(r). If they match, a desired elementis found and the search can be stopped; if they do not match, we continue with the search in the left subtree of the root if v < K(r) and in the right subtree ifv > K(r). Thus, on each iteration of the algorithm, the problem of searching in abinary search tree is reduced to searching in a smaller binary search tree. The mostsensible measure of the size of a search tree is its height; obviously, the decrease ina tree’s height normally changes from one iteration to another of the binary tree search—thus giving us an excellent example of a variable-size-decrease algorithm.
In the worst case of the binary tree search, the tree is severely skewed. This happens, in particular, if a tree is constructed by successive insertions of an increasing or decreasing sequence of keys (Figure 4.15).
Obviously, the search for an−1 in such a tree requires n comparisons, makingthe worst-case efficiency of the search operation fall into bigtheta(n). Fortunately, theaverage-case efficiency turns out to be in bigtheta(log n). More precisely, the number ofkey comparisons needed for a search in a binary search tree built from n randomkeys is about 2ln n ≈ 1.39 log2 n. Since insertion of a new key into a binary searchtree is almost identical to that of searching there, it also exemplifies the variablesize-decrease technique and has the same efficiency characteristics as the searchoperation.
