Kd tree: dữ liệu được lưu trữ chỉ trong lá vs được lưu trữ trong lá và các nút

Question

Tôi đang cố gắng triển khai cây Kd để thực hiện hàng xóm gần nhất và gần đúng tìm kiếm lân cận gần nhất trong C++. Cho đến nay tôi đã bắt gặp 2 phiên bản của cây Kd cơ bản nhất.

1. Một, nơi dữ liệu được lưu trữ trong các nút và trong lá, chẳng hạn như here
2. Một, nơi dữ liệu được lưu trữ chỉ trong lá, chẳng hạn như here

Họ dường như là căn bản giống nhau, có cùng tính chất tiệm cận.

Câu hỏi của tôi là: có một số lý do tại sao chọn cái khác?

I figured hai lý do cho đến nay:

1. Cây mà lưu trữ dữ liệu trong các nút quá là nông bởi 1 mức.
2. Cây mà các cửa hàng dữ liệu chỉ trong lá có dễ dàng hơn để thực hiện delete data chức năng

Có một số lý do khác tôi nên xem xét trước khi quyết định cái nào để thực hiện?

Answer 1

Bạn chỉ có thể các nút đánh dấu là đã xóa và trì hoãn bất kỳ thay đổi cấu trúc nào đối với việc xây dựng lại cây tiếp theo. k-d-cây phân hủy theo thời gian, vì vậy bạn sẽ cần phải thực hiện xây dựng lại cây thường xuyên. k-d-cây là tuyệt vời cho các tập dữ liệu chiều thấp không thay đổi, hoặc nơi bạn có thể dễ dàng đủ khả năng để xây dựng lại một cây tối ưu (xấp xỉ).

Để triển khai cây, tôi khuyên bạn nên sử dụng cấu trúc tối giản. Tôi thường làm các nút sử dụng không phải. Tôi sử dụng một mảng tham chiếu đối tượng dữ liệu. Trục được xác định bởi độ sâu tìm kiếm hiện tại, không cần lưu trữ nó ở bất kỳ đâu. Hàng xóm bên trái và bên phải được đưa ra bởi cây tìm kiếm nhị phân của mảng. (Nếu không, chỉ cần thêm một mảng của byte, một nửa kích thước của tập dữ liệu của bạn, để lưu trữ các trục bạn đã sử dụng). Tải cây được thực hiện bởi một QuickSort chuyên biệt. Về mặt lý thuyết nó là O(n^2) trường hợp xấu nhất, nhưng với một heuristic tốt như trung bình-of-5 bạn có thể nhận được O(n log n) khá đáng tin cậy và với chi phí liên tục tối thiểu.

Mặc dù không giữ được nhiều cho C/C++, bằng nhiều ngôn ngữ khác, bạn sẽ trả một mức giá khá lớn để quản lý nhiều đối tượng. A type*[] là cấu trúc dữ liệu rẻ nhất bạn sẽ tìm thấy, và đặc biệt nó không đòi hỏi nhiều nỗ lực quản lý. Để đánh dấu một phần tử là đã xóa, bạn có thể null nó và tìm kiếm cả hai bên khi bạn gặp phải một số null. Đối với chèn, tôi đầu tiên thu thập chúng trong một bộ đệm. Và khi bộ đếm sửa đổi đạt đến ngưỡng, hãy xây dựng lại.

Và đó là toàn bộ quan điểm của nó: nếu cây của bạn thực sự rẻ để xây dựng lại (rẻ như sử dụng một mảng gần như sắp xếp trước!) Thì không hại đến việc thường xuyên xây dựng lại cây. Quét tuyến tính qua danh sách chèn "ngắn" rất thân thiện với bộ nhớ cache CPU. Bỏ qua null s cũng rất rẻ.

Nếu bạn muốn có cấu trúc động hơn, tôi khuyên bạn nên xem xét R * -trees.Họ đang thực sự desinged để cân bằng trên chèn và xóa, và tổ chức các dữ liệu trong một cấu trúc khối theo định hướng đĩa. Nhưng ngay cả đối với R-cây, đã có báo cáo rằng việc giữ một bộ đệm chèn vv để trì hoãn thay đổi cấu trúc cải thiện hiệu suất. Và tải hàng loạt trong nhiều tình huống cũng giúp ích rất nhiều!