KD-Tree 的一些理解--

本文主要是介绍KD-Tree 的一些理解--，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

阅读文档：Wikipedia 上的 KD Tree 。
https://en.wikipedia.org/wiki/K-d_tree

引言

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. K-dimensional is that which concerns exactly k orthogonal axes or a space of any number of dimensions.[1]
K-D Tree即是K-Dimensional (维度)Tree 的缩写。K-D Tree主要用于空间划分，K-D也就是说在k维空间中对于一些点的划分。
关于这里的K-D(dimensional)，文档专门为此做出了解释，k维，指的是严格意义上的k个正交轴或任何数量维度的空间。(在这里，我觉得正交轴更好理解，主要是理解代数上的正交的意思即可。)
k-d trees are a useful data structure for several applications, such as：Searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches) & Creating point clouds. k-d trees are a special case of binary space partitioning trees.
K-D树对于一些应用，是一种非常有用的数据结构。

概述

The k-d tree is a binary tree in which every node is a k-dimensional point.[2]
☆这一句说明了重点。
k-d 树是一个二叉树，并且对于树上的每一个节点都是k维的点。
Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces.
每一个非叶子节点，都可以认为是可以划分生成一个划分超平面。这个超平面可以将这个空间分为两个部分。

主要是理解hyperplane：
hyperplane指的是一个维度比整个空间少1的超平面。
在二维平面上,hyperplane就是一条直线。
在三维空间中,hyperplane就是一个平面。
在n维空间中,hyperplane是一个n-1维的超平面。

Points to the left of this hyperplane are represented by the left subtree of that node and points to the right of the hyperplane are represented by the right subtree.
位于超平面左侧的点都由该节点的左子树所表示。而位于超平面右侧的点都由该节点的右子树所表示。

The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k dimensions, with the hyperplane perpendicular to that dimension's axis.
这段话介绍了超平面方向选取的方法。
这棵树上的每一个节点都是与k维度的一个维度相关联，
在该节点上,构建的超平面是垂直于该维度对应的坐标轴的。

So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with a larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x value of the point, and its normal would be the unit x-axis.[3]
对于上面的一个举例：
基于x的值构建一个超平面：对于一个特定的划分，特定的一个x被选取，对于所有的点，如果它们的x值小于“x”，则位这个节点的左子树，反之，则右子树。
在这个例子中,超平面的设置是由点的x坐标值来决定的,而它的法向量就是单位x轴。

K-D 树的构造方法

Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct k-d trees. The canonical method of k-d tree construction has the following constraints:[4]
因为存在许多选择轴对齐分割平面的方式,因此可以以许多不同的方式构建 k-d 树。k-d 树构建的标准方法有以下约束条件:

As one moves down the tree, one cycles through the axes used to select the splitting planes.
当沿着树向下移动时,用于选择分割平面的轴会循环使用。
(For example, in a 3-dimensional tree, the root would have an x-aligned plane, the root's children would both have y-aligned planes, the root's grandchildren would all have z-aligned planes, the root's great-grandchildren would all have x-aligned planes, the root's great-great-grandchildren would all have y-aligned planes, and so on.)
☆例如，在一个三维树中：
根节点的分割平面是沿着 x 轴对齐的。
根节点的子节点的分割平面都是沿着 y 轴对齐的。
根节点的孙节点的分割平面都是沿着 z 轴对齐的。
根节点的曾孙节点的分割平面都是沿着 x 轴对齐的。
根节点的曾曾孙节点的分割平面都是沿着 y 轴对齐的。
这种交替的平面分割方式一直延续下去。
Points are inserted by selecting the median of the points being put into the subtree, with respect to their coordinates in the axis being used to create the splitting plane. (Note the assumption that we feed the entire set of n points into the algorithm up-front.)
这段话描述了，在k维空间中如何插入一组点。
Note:我们假设我们一开始对于这个树就有n个点。
接着我们往这棵子树上插入一些点，会根据该子树所使用的分割轴(x、y或z轴)的坐标，选择这组点的中位数作为新的分割点插入到该子树中。

(也就是说，当我们需要将一组新的点插入到当前的kd树子树中时,我们不是直接将整个点集插入进去。而是先计算这组新点在当前分割轴上的中位数,然后将这个中位数作为一个新的分割点,插入到当前子树的适当位置。
也就是说,我们是将这组新点的中位数作为一个新的分割点插入进去,而不是直接将整个点集插入。这样可以保持kd树的平衡性。)

这样说有点绕，我们的借助Claude3.5来进一步理解。

This method leads to a balanced k-d tree, in which each leaf node is approximately the same distance from the root. However, balanced trees are not necessarily optimal for all applications.

这种方法可以生成一个平衡的 kd 树,其中每个叶子节点离根节点的距离大致相同。然而,平衡的树并不一定对所有应用场景都是最优的。
Note that it is not required to select the median point. In the case where median points are not selected, there is no guarantee that the tree will be balanced. To avoid coding a complex O(n) median-finding algorithm[5][6] or using an O(nlogn) sort such as heapsort or mergesort to sort all n points, a popular practice is to sort a fixed number of randomly selected points, and use the median of those points to serve as the splitting plane. In practice, this technique often results in nicely balanced trees.
注意到，我们没有必要选择中位数。当我们不选择中位数的情况下，我们无法保证树的平衡好。
为了避免编写复杂的 O(n) 中位数查找算法或使用 O(nlogn) 的排序算法(如堆排序或归并排序)来对所有 n 个点进行排序,一种常见的做法是：
☆对一个固定数量的随机选择的点进行排序,然后使用这些点的中位数作为分割平面。
在实际应用中,这种技术通常可以生成非常平衡的 kd 树。

Given a list of n points, the following algorithm uses a median-finding sort to construct a balanced k-d tree containing those points.
给定一个包含 n 个点的列表,下面的算法使用中位数查找排序来构建一棵包含这些点的平衡 k-d 树。

It is common that points "after" the median include only the ones that are strictly greater than the median in the current dimension. For points that lie on the median in the current dimension, it is possible to define a function that compares them in all dimensions. In some cases, it is acceptable to let points equal to the median lie on one side of the median, for example, by splitting the points into a "lesser than" subset and a "greater than or equal to" subset.
这段话主要是说明了如何处理在某一坐标轴上严格上等于中位数的点的方法。
以下是对于中位数之后的点的定义以及处理在当前维度上等于中位数的点两种方法。

通常情况下,中位数"之后"的点仅包括当前维度中严格大于中位数的点。对于在当前维度上与中位数相等的点,可以定义一个函数来比较它们在所有维度上的大小。在某些情况下,将等于中位数的点划分到中位数的一侧是可以接受的,例如将点划分为"小于"子集和"大于或等于"子集。

This algorithm creates the invariant that for any node, all the nodes in the left subtree are on one side of a splitting plane, and all the nodes in the right subtree are on the other side. Points that lie on the splitting plane may appear on either side. The splitting plane of a node goes through the point associated with that node (referred to in the code as node.location).
这段话，是对于k-d树的一个评价。

这个算法创造了一个不变性,即对于任何节点,左子树中的所有节点都在一个分割平面的一侧,而右子树中的所有节点都在另一侧。位于分割平面上的点可以出现在任何一侧。节点的分割平面通过与该节点相关联的点(在代码中称为node.location)。

Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. Then, they maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. Two such algorithms build a balanced k-d tree to sort triangles in order to improve the execution time of ray tracing for three-dimensional computer graphics. These algorithms presort n triangles prior to building the k-d tree, then build the tree in O(nlogn) time in the best case.[7][8] An algorithm that builds a balanced k-d tree to sort points has a worst-case complexity of O(knlogn).[9][10] This algorithm presorts n points in each of k dimensions using an O(nlogn) sort such as Heapsort or Mergesort prior to building the tree. It then maintains the order of these k presorts during tree construction and thereby avoids finding the median at each level of subdivision.

这段话，说明了如何理解提高k-d树的效率的方法比较。
有一些构建平衡 k-d 树的替代算法会先对数据进行预排序,然后在构建树的过程中保持这个预排序的顺序,从而避免了在每个分割层级上寻找中位数的代价。
这类算法主要包括两种：

用于排序三维计算机图形中三角形的算法。这些算法会先对 n 个三角形进行预排序,然后在最佳情况下以 O(n log n) 的时间复杂度构建 k-d 树,以提高光线追踪的执行时间。
用于排序点的算法。这种算法的最坏情况时间复杂度为 O(k n log n),其中 k 是维度的数量。算法首先使用 O(n log n) 复杂度的排序算法(如堆排序或归并排序)对 n 个点在 k 个维度上进行预排序,然后在构建树的过程中保持这些预排序的顺序,从而避免了在每个分割层级上寻找中位数。

总之,这些算法通过预排序和在构建过程中保持排序顺序,避免了在每个分割层级上寻找中位数的开销,从而提高了构建平衡 k-d 树的效率。

我们借助Claude3.5 来举例理解一下k-d树为什么有时效率是低下的。