K-d tree - luân phiên chiều, bất biến và cân bằng

Giới thiệu

Bài này học k-d tree lưu điểm nhiều chiều. Cây này giúp tìm điểm gần nhất rất nhanh.

Kiến thức cần nhớ

Luân phiên chiều

• Mỗi mức chỉ chia theo một chiều duy nhất.
• Mặt phẳng: mức chẵn chia x, mức lẻ chia y.
• Lên k chiều: mức d dùng chiều d chia k lấy dư.
• Ví dụ đời thường: gấp giấy xen kẽ dọc rồi ngang.

Bất biến và cân bằng

• Nút chia x: trái có x nhỏ hơn, phải có x lớn hơn.
• Sai bất biến thì rẽ nhánh sai hết.
• Xây cân bằng: chọn trung vị làm nút chia, đệ quy 2 nửa.
• Ví dụ đời thường: xếp giữa lớp làm tổ trưởng rồi chia 2 nhóm đều.

# Rẽ nhánh k-d tree theo chiều của nút
def re_nhanh(diem, nut):
    chieu = nut.chieu  # 0 là x, 1 là y
    if diem[chieu] < nut.nguong:  # so đúng 1 tọa độ
        return nut.trai  # sang trái
    return nut.phai  # ngược lại sang phải

Tìm và chèn

• Tìm: từ gốc rẽ đúng một tọa độ mỗi mức tới lá.
• Chèn: đi như tìm tới chỗ trống rồi gắn vào.
• Cây cân bằng thì tốn $O(log n)$, cây lệch thành $O(n)$.
• Ví dụ đời thường: chèn theo thứ tự tăng dần làm cây nghiêng hẳn.

Ví dụ

• Input: cây 7 điểm xây bằng trung vị -> Output: cao 3, gốc chia x, con chia y.
• Câu này cho thấy cây cân bằng nhờ trung vị.
• Input: tìm điểm vừa chèn -> Output: thấy ngay không cần duyệt hết cây.
• Câu này cho thấy rẽ nhánh đúng thì tìm nhanh.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-045/. Điểm có K chiều, dùng std::array<double, K> với K là tham số template.

Bài 1: Xây k-d tree cân bằng

template <int K> struct KDNode { std::array<double, K> p; KDNode *left = nullptr, *right = nullptr; };
template <int K> class KDTree {
 public:
  explicit KDTree(std::vector<std::array<double, K>> pts);   // xây bằng trung vị, dùng std::nth_element
  void insert(const std::array<double, K> &p);
  bool contains(const std::array<double, K> &p) const;
  int  height() const;
  bool checkInvariant() const;    // mọi nút: cây trái < p[axis] <= cây phải
};

Trục chia ở độ sâu d là d % K.

7 điểm 2D: (2,3) (5,4) (9,6) (4,7) (8,1) (7,2) (6,5)
-> gốc chia x, height = 2 (tính gốc là 0), checkInvariant = true
contains((8,1)) -> true; contains((8,2)) -> false

Bài 2: Cân bằng và lệch

1. Xây cây từ $10^5$ điểm ngẫu nhiên bằng trung vị. In height.
2. Chèn lần lượt $10^5$ điểm có x và y tăng dần. In height.
3. Đo thời gian $10^5$ lần contains trên 2 cây.

Bài 3: Truy vấn vùng chữ nhật (nâng cao)

std::vector<Point> rangeQuery(const Box &b): trả mọi điểm nằm trong hộp [lo, hi]. Cắt nhánh khi hộp không giao phía bên kia mặt chia.

7 điểm trên, hộp x in [4,8], y in [1,5] -> (5,4), (8,1), (7,2), (6,5)

Đếm số nút đã thăm. So với quét cả $10^5$ điểm cho 1000 hộp ngẫu nhiên nhỏ.

✅ Tiêu chí hoàn thành

• Test mẫu pass, checkInvariant đúng sau mọi insert.
• Bảng chiều cao và thời gian Bài 2 có số thật.
• rangeQuery khớp quét tuyến tính trên 1000 truy vấn ngẫu nhiên.
• Code chạy được cho cả K = 2 và K = 3.

❓ Câu hỏi ôn tập

• k-d tree luân phiên chiều thế nào?
• Bất biến phân hoạch phát biểu sao?
• Vì sao phải chọn trung vị khi xây?
• Cây lệch gây hại gì cho truy vấn?

🌕 Bạn đã hoàn thành ngày 45. Làm hết bài tập phía trên rồi sang ngày tiếp theo.