多维二叉搜索树
基本概念
多维二进制搜索树（缩写为kd树）定义为用于存储多键记录的数据结构。已经实现该结构以解决统计和数据分析中的许多“几何”问题。
kd树（k维树的缩写）被定义为一种空间划分数据结构，用于组织k维空间中的点。数据结构kd树是为几种应用程序实现的，例如，涉及多维搜索关键字的搜索（例如范围搜索和最近邻居搜索）。kd树被视为二进制空间分区树的特例。
非正式描述
kd树是二叉树，其中每个叶节点都被视为k维点。可以想象每个非叶节点都隐式生成一个分裂超平面（用作中值），该超平面将空间分为两部分，称为半空间。指向该超平面左侧的点由该节点的左侧子树处理，指向该超平面右侧的点由右侧的子树处理。我们可以通过以下方式选择超平面方向：树中的每个节点都与k个维度之一相关联，并且与垂直于该维度轴的超平面相关。因此，例如，如果为特定拆分选择了“x”轴，则子树中“x”值小于节点值的所有点将出现在左侧子树中，而所有“x”值较高的点值将在右侧的子树中。在这种情况下，超平面将由该点的x值设置，其法线指示单位x轴。一种流行的做法是对固定数量的随机选择的点进行排序，并实现这些点的中位数作为分割平面。
给定n个点的列表，以下算法使用中位数查找排序来构建包含这些点的平衡kd树。
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;
}