title: Priority Search Tree confusion
body: <p>The only reasonable slide set I found is <a href="https://www.cs.umd.edu/class/fall2011/cmsc725/downloads/rt-anim.pdf" rel="nofollow">this</a>, which in page 15 says, for building:</p>
  
  <blockquote>
    <ul>
    <li>Sort all points by their x coordinate value and store them in the
    leaf nodes of a balanced binary tree (i.e., a range tree)</li>
    <li>Starting at the root, each node contains the point in its subtree    with the maximum value for its y coordinate that has not been stored<br>
    at a shallower depth in the tree; if no such node exists, then node<br>
    is empty</li>
    </ul>
  </blockquote>
  
  <p>I implemented a Range Tree <a href="https://stackoverflow.com/questions/37221232/how-to-search-in-a-range-tree">just before</a>, so based on the example I used there, I now have (for a <strong>Priority Search Tree</strong>):</p>
  
  <pre><code>                             7
                        ------ 0 ---------------------
                        |                            |
                        6                            6
                  ---- -3 ----                  ---- 4 ------ 
                  |          |                  |           |
                  4          2                  1           3
            ---- -4 -       -2              --- 3 ---       5
            |       |       / \             |       |      / \
            0    (-3,4) (-2,2)(0,7)        NIL   (4,-4) (5,3)(6,-1)
           -5                               2    
           / \                             / \
      (-5,6) (-4,0)                    (2,1) (3,6)
  </code></pre>
  
  <p>Here, every inner node is of the form:</p>
  
  <pre><code>mid_x
  max y
  </code></pre>
  
  <p>and the range query I am posing is (-inf, 1) x (-0.5, 5), i.e. (x_low, x_high) x (y_low, y_high).</p>
  
  <ol>
  <li>So, let's start from the root, I check if x (=0) is in (-inf, 1) and
  if 7 > (-0.5, 5). It is, thus I proceed in both children, but for
  simplicity, let me follow the left one (in all cases from now).</li>
  <li>I check if -3 is the x range and if 6 is more or equal than the
  upper bound of the y range of the query (i.e. 5). It is, so I
  continue.</li>
  <li>Same for the next level, thus we go to the next level and now please
  focus on this inner node. It has as max y a 0, which indicates that
  the max y of the subtree is 0, which is incorrect (left child is
  (-5, 6))<sup>*</sup>.</li>
  </ol>
  
  <p>What am I missing in building/searching process?</p>
  
  <hr>
  
  <p>In other words:</p>
  
  <p>Check the leftmost branch of the tree; it has as <code>max_y</code> values (2nd bullet in the quote), 7, 6, 4, 0.</p>
  
  <p><strong>But isn't that value the one that indicated the maximum y value stored in the subtree under the inner node?</strong> If so, this does not hold for <code>0</code> and point <code>(-5, 6)</code> (6 is not used, since its used in the 2nd level). </p>
  
  <hr>
  
  <p>*<sub>The particular query I am posing might not be damaged by that, but another one can.</sub></p>