2d-tree

Bài toán 1: 2D-Tree

​

2D-Tree: cây 2 chiều với nhiều ứng dụng như: -Tìm điểm gần nhất : +Ứng dụng trong ggMap, định vị địa điểm gần bạn nhất -Tìm các điểm trong 1 phạm vi +Khoanh vùng phạm vi : lấy tất cả sản phẩm, phân tích phạm vi nào có nhiều người dùng để tập trung shipper vào khu vực đó ​

Quy tắc khi xây cây 2d-tree: -2 con của node dọc là ngang và ngược lại -Khi chèn 1 node vào cây, khi đi qua node : +Level lẻ: so sánh hoành độ, nhỏ hơn => trái , lớn hơn hoặc bằng => phải +Level chẵn so sánh tung độ, nhỏ hơn => trái ( dưới khi vẽ trên lưới ) , lớn hơn hoặc bằng=> phải (trên khi vẽ trên lưới ) +Sửa bounding rect của node vừa thêm dựa vào bounding rect của cha :

Insert node

-Recursive : 
class Node {
    Point2D point 
    Node left 
    Node right
    boolean isVertical
    Rect bounding
}
function Node insert(cur : node, point : point2D, bounding :Rect, isVertical){
    if(cur == null){ return new Node (point, bounding)} 
    if(cur.isVertical){
        if(cur.point().x() > point.x()){
            Rect newBounding = { ...bounding, maxX: cur.point().x()}
            cur.setLeft(cur.left, point, newBounding, !cur.isVertical)
        }
        else{
         Rect newBounding = { ...bounding, minX: cur.point().x()}
           cur.setRight(cur.right, point, newBounding, !cur.isVertical)
        }
    }
    else{
          if(cur.point().y() > point.y()){
            Rect newBounding = { ...bounding, maxY: cur.point().y()}
            cur.setLeft(cur.left, point, newBounding, !cur.isVertical)
        }
        else{
         Rect newBounding = { ...bounding, minY: cur.point().y()}
           cur.setRight(cur.right, point, newBounding, !cur.isVertical)
        }
    }
    return cur
}

**Ví dụ: xây cây 2d-trêe và vẽ trên lưới ** =>Cây 2d-tree : =>Lưới : =>Hộp bao :

   *Bounding rect của 1 điểm sẽ là hcn phạm vi của node đó thường được kế thừa từ cha và chỉnh sửa tại phần x / y mà thằng con nằm bên trái / phải so với cha . 
   Ví dụ : A(2,3) có bounding rect [-&, &] x [-& , &] 
               => B(3,5) nằm bên phải A => bounding rect : [2, +&] x [-& , +&]
               & : vô cùng

Tư tưởng thuật toán tìm kiếm theo vùng rect:

 -Đi từ gốc, tại mỗi điểm check bounding rect của điểm đó có intersect với target rect hay không : 
   + Nếu CÓ check node đó có thuộc rect hay không và đi sang cả 2 bên trái và phải của phần đó.
   + Nếu KO tỉa nhánh đó đi (bỏ luôn vì phạm vi của cha đã ko thuộc rồi thì cần gì mất công check phạm vi của node con ~ chắc chắc cũng là không thuộc ~)
-Code : 
function f(root, targetRect ) //BFS 
   -res:List
   -tracks:Queue
   -tracks.add(root)
   while(!tracks.isEmpty () ){
   cur = tracks.pool()
   if(cur == null) continue;
   if(!intersect (targetRect , cur.boundingRect)){
       continue;
   }
   if(targetRect.contains(cur)){
       res.add(cur)
   }
     tracks.add(cur.left)
   tracks.add(cur.right)
   }
   return res;

function recursion (cur, targetRect, res) //DFS 
  if(cur == null) continue;
   if(!intersect (targetRect , cur.boundingRect)){
       continue;
   }
   if(targetRect.contains(cur)){
       res.add(cur)
   }
     tracks.add(cur.left,...)
   tracks.add(cur.right,...)
   }

Độ phức tạp

    -Worst: đi hết cây: N 
    -Average: logN 

​ Với hình chữ nhật được cho dưới đây, hãy đánh số các nút (không rỗng) theo thứ tự mà chúng được truy cập bởi một truy vấn theo vùng (range query). Những cây con nào bị tỉa (pruned)? (Lưu ý: Một số cây con rỗng có thể bị tỉa, và một số thì không.) ​

Bounding rect của các điểm

-Thứ tự nút được truy cập theo DFS 
+1: A intersect: tracks gọi   B, E 
+2: B : intersect : gọi B.left (null) và C  
+3:C : intersect : gọi left(D) và F 
+ 4:D : intersect : gọi left (null) và right(null)
+5 :F : not intersect => prune (tỉa luôn ~ return) 
+6:E : intersect : gọi G 
+7:G intersect . 

Bài toán 2: Nearest Neighbour Search

Input: You had a set of 2d points which present the location of stores Output: Let's build a effective data structure to store this set to satisfy search requirement that determines the nearest store to any client's location (x,y) -Use above approach that we installed to build 2dTree Strategy: ```js -Check bestPoint.distanceSquaredTo(queryPoint) < cur.bounding.distanceSquaredTo(queryPoint) => prune : return because -Compare the distance bestPoint and queryPoint to the distance cur.point and queryPoint at every turn call recursive +Cur.isVertical : compare cur.x() to queryPoint.x() +Else : compare cur.y() to queryPoint.y() =>Navigate to one side : left / right -However,need to compare h(queryPoint, cur.point()) to bestPoint.distance : (~vertical : h = abs( cur.point().x() - queryPoint.x()) ~else : h = ...y )

       _ h < bestPoint.distanceSquaredTo(queryPoint) => navigate rest branch because it may contain nearer point 
 -Code 
 function Point nearnest (cur :Node, queryPoint : Point2D, bestPoint: Point2D) {
 if(cur == null) return bestPoint;
 if(
 
 }
Node first , second 
 -if(cur.isVertical()){
             
 }
-if(cur.point().distanceSquaredTo(queryPoint)) < bestPoint.distanceSquaredTo(queryPoint)) => bestPoint = cur.point() 

if(cur.isVertial
```