3

I read several slides, like this one's last page, where the describe the search algorithm. However, I have a basic question. The data lie in a 2D space.

I first build a Binary Search Tree based on the x value of the points. Every inner node holds a BST based on the y value of the points that lie in the subtree of that inner node.

Then I think I should search for the points that lie in the range query [x1, x2] and then check if for that points the requested [y1, y2] range query is satisfied. However, the algorithm suggests that you should search in the y-based BST of an inner node, if the range of the inner node is inside [x1, x2], but I don't get that.

If we do that, then in an example I have, we will search (without a reason) the y-based BST of the root. Check the example:

                      ------ 0 ---------------------
                      |                            |
                ---- -3 ----                  ---- 4 ------ 
                |          |                  |           |
          ---- -4 -    -2              --- 3 ---          5
          |       |    / \             |       |         / \
         -5   (-3,4) (-2,2)(0,7)       2    (4,-4)   (5,3)(6,-1)
         / \                          / \
    (-5,6) (-4,0)                  (2,1) (3,6)

And the range query I wish to perform is (-oo, 1) x (0, 5)*.

If I look at the root, it has value 0, thus it's enclosed in (-oo, 1), so if I follow the algorithm I am going to search the whole y-based tree of the root?

That should be a tree that contains all the points, so there is no point in continuing searching in x-based tree. Moreover, that will result in more visited nodes than the necessary.

I am implementing that in , if that matters.

*Performing a range query for x's in the range [-inf, 1] and y's in the range [0, 5].

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • Is `(-inf, 1)` an `(x, y)` coordinate or `(x_lo, x_hi)`? I'm guessing it's the latter. – James Adkison May 14 '16 at 01:30
  • @JamesAdkison the latter, should I edit my question? How should I do that, if so? – gsamaras May 14 '16 at 01:31
  • It would have been clear to me if there were statements similar to: Performing a range query for x's in the range [-inf, 1] and y's in the range [0, 5] (or anything similar to that). – James Adkison May 14 '16 at 01:35

1 Answers1

2

The algorithm you are proposing is not quite right - you should compare the range you are querying with the range of the node you are looking at, not the value of the node.

E.g., initially you should compare (-inf, 1) with (-5, 6), which is the data range of the tree (you can also use (-inf, inf) as the data range of the tree or any interval that encloses (-5, 6), for that matter), instead of the value 0. Recursively you should compare the query range with the range of the subtree rooted at the node you are querying at.

Also, the range update can be done while searching - when splitting at a node, the upper/lower bound of the left/right recursive call interval is the node value.

zw324
  • 26,764
  • 16
  • 85
  • 118
  • Yeah I know that I was missing something, but I didn't know what. However, I am trying to run the example I have in my question, but I am not sure how to proceed with it. I mean how can the root actually check for `(-5, 6)`? Does it store it? – gsamaras May 14 '16 at 02:04
  • You can store it (I think it could provide some speedup in the extreme case, for example when the whole tree is in the query range), but you can actually use (-inf, inf) and update the interval while querying - my last update was to address this point :-) – zw324 May 14 '16 at 02:07
  • Thanks Mr. Wei, I have asked a new, relative, [question](https://stackoverflow.com/questions/37222215/priority-search-tree-confusion). If you have time, take a look! – gsamaras May 14 '16 at 03:35