Please explain algorithm in words, give pseudocode, and discuss correctness and running time.
Recall that the elements stored in a binary search tree T whose keys are in the range [k1, k2] can be found and reported in O(h+s) time, where h is the height of T and s is the number of elements in the range. Suppose instead that we need only to find the number of elements in T whose keys are in the range [k1, k2]. Assuming that each node v of T is augmented with the number nv of internal nodes in the subtree rooted at v (as in P. 104), design an algorithm that solves the above counting problem in O(h) time.
Page 104 is included.
104 Chapter 3. Binary Search Trees 3.3 Index-Based Searching We began this chapter by discussing how to search in a sorted array, A, which allows us to quickly identify the ith smallest item in the array simply by indexing the cell Ali. As we mentioned, a weakness of this array representation is that it doesn't support efficient updates, whereas a binary search tree allows for efficient insertions and deletions. But when we switched to a binary search tree, we lost the ability to quickly find the ith smallest item in our set. In this section, we show how to regain that ability with a binary search tree. Suppose, then, that we wish to support the following operation on a binary search tree, T, storing n key-value pains: select(i): Return the item with ith smallest key, for 1 S isn. For example, if i-1, then we would return the minimum item, if i = n, then we would return the maximum, and if i =n/21, then we would return the median (assuming n is odd). The main idea for a simple way to support this method is to augment each node, v, in T so as to add a new field, ny, to that node, where m,, is the number of items stored in the subtree of T rooted at v. For instance, see Figure 3.13. 14 5 23 63 17 4 51 3 74 20 48 2 58 71 46 72 Figure 3.13: A binary search tree augmented so that each node, v, stores a count, ny, of the number of items stored in the subtree rooted at v. We show the key for each node inside that node and the ny value of each node next to the node, except for external nodes, which each have an ny count of 0. 104 Chapter 3. Binary Search Trees 3.3 Index-Based Searching We began this chapter by discussing how to search in a sorted array, A, which allows us to quickly identify the ith smallest item in the array simply by indexing the cell Ali. As we mentioned, a weakness of this array representation is that it doesn't support efficient updates, whereas a binary search tree allows for efficient insertions and deletions. But when we switched to a binary search tree, we lost the ability to quickly find the ith smallest item in our set. In this section, we show how to regain that ability with a binary search tree. Suppose, then, that we wish to support the following operation on a binary search tree, T, storing n key-value pains: select(i): Return the item with ith smallest key, for 1 S isn. For example, if i-1, then we would return the minimum item, if i = n, then we would return the maximum, and if i =n/21, then we would return the median (assuming n is odd). The main idea for a simple way to support this method is to augment each node, v, in T so as to add a new field, ny, to that node, where m,, is the number of items stored in the subtree of T rooted at v. For instance, see Figure 3.13. 14 5 23 63 17 4 51 3 74 20 48 2 58 71 46 72 Figure 3.13: A binary search tree augmented so that each node, v, stores a count, ny, of the number of items stored in the subtree rooted at v. We show the key for each node inside that node and the ny value of each node next to the node, except for external nodes, which each have an ny count of 0
