Cây tứ phân điểm là sự thích nghi của cây nhị phân được thực hiện để biểu diễn dữ liệu điểm 2 chiều. Các tính năng của tất cả các quadtrees được chia sẻ bởi quadtree điểm.
Nó thường rất hiệu quả trong việc so sánh các điểm dữ liệu 2 chiều, có thứ tự, thường thực hiện trong thời gian O (log n). Các cây phần tư điểm có giá trị được đề cập đến vì tính đầy đủ, nhưng cây k-d vượt qua chúng như là công cụ để tìm kiếm nhị phân tổng quát.
Các phần tư điểm được xây dựng như sau.
Đưa ra điểm tiếp theo để chèn, chúng tôi tính toán ô chứa nó và thêm nó vào cây.
Điểm mới được thêm vào sao cho ô chứa nó được chia thành các góc phần tư bởi các đường dọc và ngang chạy qua điểm. Do đó, các ô có hình chữ nhật nhưng không nhất thiết phải là hình vuông.
Trong các cây này, mỗi nút bao gồm một trong các điểm đầu vào.
Vì sự phân chia của 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. Việc chèn không đúng thứ tự có thể dẫn đến cây có chiều cao tuyến tính với số lượng điểm đầu vào (lúc này nó trở thành danh sách liên kết).
Nếu tập hợp điểm là tĩnh, quá trình xử lý trước có thể được thực hiện để xây dựng một cây có chiều cao cân bằng.
Cấu trúc nút cho một phần tư điểm
Một nút của cây phần tư điểm giống với nút của cây nhị phân, với sự khác biệt chính là nó được liên kết với bốn con trỏ (mỗi con trỏ được sử dụng cho mỗi góc phần tư) thay vì hai ("trái" và "phải") như trong một cây nhị phân thông thường. Ngoài ra, một khóa thường được chia thành hai phần, tham chiếu đến tọa độ x và y.
Do đó, một nút bao gồm các thông tin sau
- bốn con trỏ:Đây là quad [‘NW’], quad [‘NE’], quad [‘SW’] và quad [‘SE’]
- NW-Tây Bắc, NE-Đông Bắc, SW-Tây Nam, Đông Nam Đông Nam
- điểm; đến lượt nó bao gồm khóa
- ; thường được ký hiệu là tọa độ x, y
- giá trị; chẳng hạn như một cái tên