K-D树、K-D-B树、B-K-D树

K-D树在维基百科上定义是将K维空间中的点进行分割的数据结构，D是dimensional(维度)的缩写，K-D树是BSP(Binary Space Partitioning)的一种。

维基百科的解释很正式(看的迷迷糊糊)。简单的说，K-D树就是二分查找树在K维空间的泛化(更迷糊了:joy:)。

1、K维空间的二分查找树

之前的一篇文章中有讲过二分查找树(BST)这样基础的数据结构，它是基于二分查找的思想实现的插入和查找速度。

如果把BST中的所有元素看成一维线段上的所有点，从树的根节点开始每个节点都会把线段分成两段。

BST

所以BST本质上就是一维K-D树(或者叫做1-D树)

现在将树中的元素推广到二维平面上的点，树的每一层按照维度轮流划分。比如，奇数层按x轴划分，偶数层按y轴划分，这样就得到一棵二维K-D树(2-d树)

KD-Tree

同样我们可以将元素推广到三维空间中的点，那样我们可以得到一棵3d-tree。

3d-tree

理论上k-d树可以继续到4维，5维… 作为一个三维空间里的生物，就没法用图来展示这样的元素了:sweat_smile:

这里有一个二维K-D树的模拟程序能帮助我们更好的理解K-D树：

任何事物都有好坏的地方，K-D树也是如此。

K-D树的优点：

很明显，K-D树和BST一样不仅可以精确查找，也更适合做范围查询，但K-D树比BST更强，它能对多个维度进行范围查询。

比如：

Person1(age:18,hight:176)，Person2(age:19,height:181) … Person10(age:23,height:171)

想要查找年龄在20岁以上并且身高在170到180之间的所有人，用K-D树就能很好的解决。

k-d-tree range search

由于K-D树的结构要求，上面的例子中要求每个人的年龄和身高各项数据必须齐全，如果某个人只有年龄或只有身高，就无法使用K-D树索引了。所以实际上K-D树更常见的应用是经纬度定位，或者三维空间定位(某个维度数据缺失，其他维度数据也就没有意义了)

缺点：

和二分查找树一样，K-D树也有平衡性问题，这个问题下面会进行详细讨论。

高纬度数据查找效率并不一定好，有时候可能不如最原始的暴力查找。通常，如果维度为k，则k-d树中的点数N应远远大于(即)。否则查找时，节点中大多数节点都会被遍历到，效率上还不如原始的遍历。

2、K-D树的平衡问题

既然K-D树是BST在k维空间的推广，那K-D树自然也有BST存在的平衡性问题——二叉树退化成链表。

平衡性问题

但是由于K-D树按多个维度划分子树，相邻的层级之间不在同一个维度，因此AVL、RB-Tree等平衡二叉搜索树的旋转技术对于K-D树并不适用。

有一种做法是重建K-D树：将已知的所有点作为输入，每一层按照该层维度排序，并找到中位数的那个点作为子树的根节点。这个过程用伪代码表示如下：

function kdtree (list of points pointList, int depth)
{
    // 该层的维度，2-d树的第1层就是x
    var int axis := depth mod k;
        
    // 按照该层维度选取中位数(这个过程中可能需要排序)
    select median by axis from pointList;
    
    node.location := median; // 构造节点
    // 构造左右子树
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}