多维二叉搜索树

基本概念

多维二进制搜索树（缩写为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;
}