Now, we are ready to propose an algorithm for processing one-dimensional range queries. Absorbed in general, the search paths for the end points x and x prime of the query interval first go together, and then at some node, split. For an internal node v of T, let lc of v and rc of v denote its left and right child respectively. Moreover, let xv denote the splitting value stored at the node v. The first thing to do is to find the split node. The respective procedure takes as input a binary balanced search path T and two values, x and x prime. Thereby, we assume that x is less than or equal to x prime. The output of this procedure is the node at which the search paths for x and x prime split or both search paths end. As a first step, we'll let a node v be the root of T. Subsequently, while v is not a leaf, we check whether x prime is less than or equal to xv or x is greater than xv, and proceed to the left and right subtree of the node v in the former and latter case respectively. If [inaudible] holes, the loop terminates. After completion of the cycle, the node v represents the node we have been looking for. Now, let us describe the entire query algorithm. First, we find the split node for the search paths to the end points x and x prime of the query interval. Further, we follow the source paths for x from the split node until the leaf node. Whenever we proceed from the current node v to its left child, we report all the points from P stored in the right subtree of v. In the example, you now see on the left is soon and we are moving from the node v to its left child and c of v, we will report all the points stored in the subtree rooted at the [inaudible] node. Namely, the two points stored at the dog reliefs. Similarly, when following the search path for x prime, each time we proceed from the current node v to it's right child, we report all the points stored in the subtree rooted at the left child of v. We emphasize once again, before the leaves u and u prime, we should check explicitly whether their respective points fall in the query interval and if so, we report them. Suppose that you have at hand a procedure ReportSubtree that takes as a parameter in order v of T and reports all the points stored in the subtree rooted at v. Now, that is outlined a procedure that takes as input a binary balanced stored tree T and a query interval, x, x prime, and report all the points stored in T that fallen side x, x prime. We start by finding the split node for the search paths to x and x prime in the treaty. If there's not turns out to be a leaf, we check whether the point stored at it must be reported and if so, output it. Otherwise, we continue along the search path for x. Thus, we let node v be the left child of v split. Further, while v is not a leaf, we check whether x is less than or equal to xv. If so, report all the points stored at the right subtree of v and continue to its left child. Otherwise, we move to the right child of v. When we reach a leaf, we check whether the point stored at it falls inside the query interval and if so, report it. The search path from the node v split to x prime is processed analogously. Now, let us estimate the time complexity of the purported algorithm. As we showed earlier, in binary balanced source tree or a set of n values uses linear memory and can be built in algorithm and time. When tremors in the search path to x or x prime, we spend constant time at each visited node, not counting the time spent in goals to the procedure report subtree. Recall that the height of the routine is asymptotic logarithm n. Consequently, the term requirements of the method except for the time needed to report the points is asymptotically also an logarithm n. The overall time spent by this procedure reports subtree is linear in the total number of leaves in the traverse subtrees. We conclude that it is linear in the number of the reported points. Thus, the running time of our algorithm is big O of logarithm n plus k, where k is the number of the reported points. The proposed method is output sensitive. In the worst case, the time complexity will be linear in n, since potentially all the points from our state may need to be reported. To summarize, our algorithm can process one-dimensional range queries in time logarithm n plus k using linear memory and he'll spend n logarithm and time at the proposing stage.