Structure

Each node holds N-M entries (MBRs). Similar to B-tree but with rectangles.

Advertisement

Insert with split

Descend to best-fitting MBR. If leaf overflows, split via linear/quadratic/R* heuristics. Propagate MBRs upward.

Advertisement

Search

void search(Node n, Rect query, List result) {
  for (Entry e : n.entries) {
    if (e.mbr.intersects(query)) {
      if (n.isLeaf) result.add(e.object);
      else search(e.child, query, result);
    }
  }
}


R* tree improvement


Reinsertion during overflow + better split choice. Produces more compact + query-efficient trees.




        
    






  
Advertisement

  
  






    ← Back to Algorithms & DP





    Disclaimer
     · 
    Privacy
     · 
    Contact