kd-tree是一种树数据结构， 用来存储多维数据。正如BST（二分搜索树）用值的大小关系来建树，左子节点的值 < 父节点 < 右子节点。 kd-tree也是用值的大小关系来建树，但是由于它处理的是多维数据， 以二维为例， 在根节点根据x值的大小关系来组织， 左子节点x值 < 父节点x值 < 右节点x值， 在下一层， 则换用y值的大小关系来组织， 左子节点y值 < 父节点y值 < 右节点y值，再下一层又换回x值，如此循环。
以二维为例， 从根节点开始， 如果x值比根节点大或等于，就在右子树查找， 如果x值比根结点小，就在左子树查找，如果x值和y值都相同，则查找到。
以二维为例， 在kd-tree中插入一个节点， 实际上就是查找一个可以插入的位置， 从根节点开始， 如果x值比根节点大，就插入在根的右子树，如果 x值比根节点小， 就插入在左子树。子树的插入方法相同， 直到找到一个null的位置。
首先， 使用和查找一样的方法， 确定删除点的位置， 使用以下步骤来删除：
- 如果删除点没有子树，直接删除。
- 如果删除点有右子树， 在右子树查找到当前维度的最小值， 和节点替换，然后重新删除那个点
- 如果删除点有左子树， 在左子树查找当前维度最小值，和节点替换，然后重新删除那个点， 最后把整个左子树移到右边
以x值为例， 如果当前节点的分割维度是x， 那么在左子树查找， 如果不是则两个子树都要查找。
假设查询点为Q， 一开始设定最近距离为infinity， 结果点为null. 从根节点开始， 计算根节点到Q的距离，将它记为最近距离，将节点本身记为结果点。 根据跟节点的分割维度x， 比较Q的x值和分割x的关系， 如果x < 分割x，则优先查找左子树， 否则优先查找右子树。 在优先子树中重复上述操作。计算Q到根节点的距离， 如果更小则更新结果。 在非优先子树中， 需要计算（在父节点）Q到分割轴的距离， 如果这个距离比当前最近距离还大， 那么剪掉这整棵子树，不用查找。
和最近邻查询一致， 但是对于途中计算到的所有最小距离和候选结果点， 以距离为权重，保存在最小堆中。最后返回最小堆中的前k个，即为结果。
如果预先已经知道数据点了， 可以建立一棵平衡的kd-tree使得，左右子树的高度差较小。 建立的方法就是， 选择分割值的时候，以中位数作为分割值， 最简单的方法就是对于所有值排列然后选择 中间的值。
使用排列然后再选择中值的方法，效率有点低，可以使用一些快速选择方法。
- 随机选择：
随机选择是快速排序的一种变体， 快速排序每次分割都会确定一个元素的位置。 随机选择则随机地选择一个元素， 然后确定它的位置， 之后查看这个元素是不是在中点， 如果不是，则查看它是在中点的左边还是右边，如果在中点的左边，则从元素 开始到结尾重新随机选择一个元素确定它的位置，在右边则反之，如此重复，直到确定中点元素的值。
- 中点选择：
随机选择虽然在实践上可以得到很好的结果， 但是在理论上的结果不够好。 中点选择， 和随机选择类似， 但是它不是随机的确认一个元素的位置， 而是使得确认的元素尽可能的接近中点。
它首先将元素每5个分成一组， 计算每组的中点， 然后将得到的中点，又每5个分成一组， 计算中点， 如此重复，直到得到一个中点元素， 这个值就是候选元素值，确定它的位置， 如果它是中点则结束，否则和随机选择类似，在一个小范围内重新确定。
从随机选择和中点选择中获得启发， 可以使用这种方法， 在数组内部原地的对元素进行重排， 使得整体的中点是根节点， 左边的中点是左子树根节点， 右边的中点是右子树根节点。以此类推。这种方法没有建立起层次结构。可以节约内存， 但是相应的操作需要改变。