Khái niệm cơ bản
Cây tìm kiếm nhị phân đa chiều (viết tắt là k-d tree) được định nghĩa là một cấu trúc dữ liệu để lưu trữ các bản ghi nhiều khóa. Cấu trúc này đã được thực hiện để giải quyết một số vấn đề "hình học" trong thống kê và phân tích dữ liệu.
Cây k-d (viết tắt của cây k chiều) được định nghĩa là cấu trúc dữ liệu phân vùng theo không gian để tổ chức các điểm trong không gian k chiều. Cấu trúc dữ liệu cây k-d được triển khai cho một số ứng dụng, ví dụ, các tìm kiếm liên quan đến khóa tìm kiếm đa chiều (ví dụ:tìm kiếm theo phạm vi và tìm kiếm lân cận gần nhất). cây k-d được coi là một trường hợp đặc biệt của cây phân vùng không gian nhị phân.
Mô tả không chính thức
Cây k-d là một cây nhị phân trong đó mọi nút lá được coi như một điểm k-chiều. Mọi nút không phải nút đều có thể được hình dung như việc tạo ra một siêu phẳng chia tách (được sử dụng làm trung vị) ngầm chia không gian thành hai phần, được gọi là nửa không gian. Các điểm ở bên trái của siêu phẳng này được xử lý bởi cây con bên trái của nút đó và các điểm ở bên phải của siêu phẳng được xử lý bởi cây con bên phải. Chúng ta có thể chọn hướng siêu phẳng theo cách sau:mọi nút trong cây được liên kết với một trong k chiều, cùng với siêu phẳng vuông góc với trục của chiều đó. Vì vậy, ví dụ:nếu đối với một phép chia cụ thể mà trục "x" được chọn, tất cả các điểm trong cây con có giá trị "x" nhỏ hơn nút sẽ xuất hiện trong cây con bên trái và tất cả các điểm có giá trị "x" cao hơn sẽ được trong cây con bên phải. Trong trường hợp như vậy, siêu phẳng sẽ được đặt bởi giá trị x của điểm và bình thường của nó chỉ ra trục x đơn vị. Một phương pháp phổ biến là sắp xếp một số cố định các điểm được chọn ngẫu nhiên và triển khai giá trị trung bình của các điểm đó để làm mặt phẳng phân tách.
Cho một danh sách gồm n điểm, Thuật toán sau sử dụng cách sắp xếp tìm điểm trung bình để xây dựng cây k-d cân bằng chứa các điểm đó.
function KDtree (list of points PointList, int Depth) {
// Choose axis based on Depth so that axis cycles through all valid values
var int axis := Depth mod k;
// Sort point list and select median as pivot element
choose median by axis from PointList;
// Node is created as node1 and construct subtree
node1.location := median;
node1.leftChild := KDtree(points in PointList before median, Depth+1);
node1.rightChild := KDtree(points in PointList after median, Depth+1);
return node1;
}