『OPEN3D』1.5.3 动手实现点云KD树最近邻

本专栏地址：

https://blog.csdn.net/qq_41366026/category_12186023.html?spm=1001.2014.3001.5482

        当我们在一个排序后的容器中进行查找时，使用二分查找可以显著减少查找时间。基于这个思路，我们可以引入一种类似于二分查找的数据结构，它被称为二叉搜索树（Binary Search Tree，BST）。而对于高维空间中的数据，可以使用K-d树（K-dimensional tree）这样的数据结构。

二叉搜索树是一种有序的二叉树，其中每个节点都包含一个键值，且满足以下性质：

• 左子树中的所有节点的键值都小于根节点的键值。
• 右子树中的所有节点的键值都大于根节点的键值。
• 左右子树也分别是二叉搜索树。

通过这种有序性，我们可以利用二分查找的思想在二叉搜索树中高效地进行查找、插入和删除操作。

        一个二叉树可以认为是一个已经排过序的数组时，使用二分查找可以比线性查找拥有更高的效率。二分查找的时间复杂度为O(log2 N)&#x