CS136 : cs240tut10.pdf
Document Summary
Range trees: used for range searching multi-dimensional data, e. g. , nd all points (x, y) which satisfy. 1 dimensional range trees are balanced binary search trees where the points are stored in the leaves. To allow binary search to work, the non-leaves contain the value of the largest leaf contained in the left child"s subtree. Example: draw the perfectly balanced 1-dimensional range trees on the x and y coordinates of the points. Answer: (1, 8), (2, 6), (3, 4), (5, 7). Example: search for the range [2. 5, 6. 5] in both trees. Answer: bold nodes represent those on the search paths; underlined nodes represent those which are in range: In general, you want to output all the leaves which lie between the search paths, and possibly the two leaves which lie on the search paths; check if these points lie in range manually. (explain how pseudocode works. ) Example: draw the perfectly balanced 2-dimensional range tree using the previous points.
