KD-Tree（也称为K维树）是一种二叉搜索树，其中每个节点中的数据是空间中的K维点。 简而言之，它是用于组织K维空间中的点的空间划分的数据结构。KD-Tree中的非叶节点将空间分为两部分，称为半空间。该空间左侧的点由该节点的左侧子树表示，空间右侧的点由右侧子树表示。 根将具有x对齐的平面，根的子代都将具有y对齐的平面，根的孙子都将具有x对齐的平面，而根的曾孙将具有y对齐的平面，依此类推。
概括：
让我们将平面编号为0、1、2…（K – 1）。 很明显，深度D处的点（节点）具有A对齐的平面，其中A的计算公式为：
A = D mod K
如何确定一个点将位于左侧子树还是右侧子树中？
如果根节点在平面A中对齐，则左子树将包含其平面中的坐标小于根节点坐标的所有点。 同样，右子树将包含其平面上的坐标等于根节点坐标的所有点。
2D-Tree创建的示例：
有以下2维坐标点：(3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)
插入（3，6）：由于树为空，因此使其成为根节点。插入（17，15）：将其与根节点点进行比较。由于根节点是X对齐的，因此将比较X坐标值以确定它是在右子树中还是在右子树中。该点将与Y对齐。插入（13，15）：此点的X值大于根节点中点的X值。因此，这将位于（3，6）的右侧子树中。再次将该点的Y值与点（17，15）的Y值进行比较。因为它们相等，所以这一点将位于（17，15）的右子树中。该点将X对齐。插入（6，12）：此点的X值大于根节点中点的X值。因此，这将位于（3，6）的右侧子树中。再次将该点的Y值与点（17，15）的Y值进行比较。由于12 <15，此点将位于（17，15）的左子树中。该点将X对齐。插入（9，1）：类似地，此点位于（6，12）的右侧。插入（2，7）：类似地，该点位于（3，6）的左侧。插入（10，19）：同样，此点位于（13，15）的左侧。空间如何划分？
上面所有7个点将在X-Y平面中绘制如下：
1. 点（3，6）将会把整个空间分成两部分：绘制X = 3分割线。
2. 点（2，7）将X = 3线左侧的空间水平分成两部分。在线X = 3的左侧绘制线Y = 7。
3. 点（17，15）将X = 3线右边的空间水平分成两部分。在X = 3线的右边绘制Y = 15线。
4. 点（6，12）将Y = 15线下方和X = 3线右侧的空间分成两部分。在X = 3线的右侧和Y = 15线下方绘制X = 6线。
5. 点（13，15）将Y = 15线下方和X = 6线右侧的空间分成两部分。在X = 6线的右侧和Y = 15线下方绘制X = 13线。
6. 点（9，1）将X = 3，X = 6和Y = 15的线分成两部分。在X = 3和X = 6之间绘制Y = 1线。
7. 点（10，19）将X = 3线右侧和Y = 15线上方的空间分为两部分。在X = 3线的右侧和Y = 15线的上方绘制Y = 19线。
