Khái niệm cơ bản
Cây tìm kiếm nhị phân đa chiều (viết tắt k-d tree) được định nghĩa là cấu trúc dữ liệu để lưu trữ bản ghi đa khóa (multikey records). Cấu trúc này đã được dùng để giải quyết nhiều bài toán "hình học" (geometric) trong thống kê và phân tích dữ liệu.
Cây k-d (viết tắt của k-dimensional tree) được định nghĩa là cấu trúc dữ liệu phân vùng không gian (space-partitioning) để tổ chức điểm trong không gian k chiều. Cấu trúc dữ liệu k-d tree được dùng cho nhiều ứng dụng, ví dụ: tìm kiếm liên quan đến khóa tìm kiếm đa chiều (ví dụ: tìm kiếm phạm vi - range searches và tìm kiếm láng giềng gần nhất - nearest neighbor searches). k-d tree là trường hợp đặc biệt của cây phân chia không gian nhị phân (binary space partitioning trees).
Mô tả không chính thức
Cây k-d là cây nhị phân mà mỗi nút lá được coi là một điểm k chiều. Mọi nút không phải lá có thể tưởng tượng là ngầm tạo ra một siêu phẳng chia (splitting hyperplane - dùng làm trung vị) chia không gian thành hai phần, gọi là nửa không gian (half-spaces). Điểm bên trái siêu phẳng này được xử lý bởi cây con trái của nút đó, điểm bên phải được xử lý bởi cây con 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 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 chiều đó. Ví dụ: nếu cho một lần chia cụ thể trục "x" được chọn, tất 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 trái và tất cả điểm giá trị "x" lớn hơn sẽ ở cây con phải. Trong trường hợp đó, siêu phẳng được đặt bởi giá trị x của điểm, và pháp tuyến đơn vị chỉ trục x. Thực hành phổ biến là sắp xếp số điểm ngẫu nhiên cố định, và dùng trung vị của những điểm đó làm mặt phẳng chia.
Cho danh sách n điểm, thuật toán sau dùng sắp xếp tìm trung vị để xây dựng k-d tree cân bằng chứa các điểm đó.
function KDtree(list of points PointList, int Depth) {
// Chọn trục dựa trên Depth để trục luân phiên qua tất cả giá trị hợp lệ
var int axis := Depth mod k;
// Sắp xếp danh sách điểm và chọn trung vị làm phần tử chốt (pivot)
choose median by axis from PointList;
// Tạo nút node1 và xây dựng cây con
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;
}