Quadtree điểm (point quadtree) là biến thể của cây nhị phân dùng để biểu diễn dữ liệu điểm 2 chiều. Nó chia sẻ đặc điểm của tất cả quadtree.
Nó thường rất hiệu quả khi so sánh dữ liệu điểm 2 chiều có thứ tự, thường thực thi trong O(log n) thời gian. Quadtree điểm đáng nhắc đến để hoàn thiện, nhưng k-d tree vượt trội hơn như công cụ tìm kiếm nhị phân tổng quát.
Quadtree điểm được xây dựng như sau:
Cho điểm tiếp theo cần chèn, ta tính ô chứa nó và thêm vào cây.
Điểm mới được thêm sao cho ô chứa nó bị chia thành tứ phần bởi đường thẳng đứng và ngang đi qua điểm đó. Do đó, các ô là hình chữ nhật nhưng không nhất thiết là vuông.
Trong các cây này, mỗi nút chứa một trong các điểm đầu vào.
Vì việc phân chia mặt phẳng được xác định bởi thứ tự chèn điểm, chiều cao của cây nhạy cảm và phụ thuộc vào thứ tự chèn. Chèn theo thứ tự sai có thể dẫn đến cây chiều cao tuyến tính theo số điểm đầu vào (lúc đó nó trở thành danh sách liên kết).
Nếu tập điểm là tĩnh, có thể tiền xử lý để xây dựng cây cân bằng chiều cao.
Cấu trúc nút cho quadtree điểm
Một nút của quadtree điểm tương tự nút cây nhị phân, khác chính là nó có bốn con trỏ (mỗi con trỏ cho một tứ phần) thay vì hai ("left" và "right") như cây nhị phân thông thường. Khóa thường được chia thành hai phần, tham chiếu tọa độ x và y.
Do đó, một nút chứa thông tin sau:
- bốn con trỏ: quad['NW'], quad['NE'], quad['SW'], quad['SE']
- NW - Tây Bắc, NE - Đông Bắc, SW - Tây Nam, SE - Đông Nam
- điểm (point); bao gồm:
- khóa (key); thường là tọa độ x, y
- giá trị (value); ví dụ: tên