RussellABrown/kd-tree

**动态K-D树：** 动态K-D树由 Overmars 和 van Leeuwen 在论文 "Dynamic Multi-Dimensional Data Structures Based on Quad- and K-D Trees" (Acta Informatica 17:267-285, 1982) 中提出。其建树算法在以下在线文章中有所描述。 动态K-D树构建算法维护一个类似于AVL树或红黑树的平衡K-D树，当插入或删除一个K维元组导致树不平衡时，它会通过重建子树来进行自平衡。下文描述的多线程静态K-D树构建算法用于重建该子树。 动态K-D树实现了一个集合。还包括一个基于动态K-D树的键值对多值映射的实现。 动态K-D树被实现为 `KdTreeDynamic` 类，它派生自实现静态K-D树的 `KdTree` 类。因此，`KdTree` 类实现的搜索算法，如区域搜索和最近邻搜索，既可用于静态K-D树，也可用于动态K-D树。此外，可以先通过两种静态算法之一构建一个静态K-D树，之后再通过动态算法修改该树。 C++/kd-tree/test_kdtreedynamic.cpp 文件及其关联的 .h 文件（kdTreeDynamic.h, kdTree.h, kdTreeNode.h, KdTreeNlogn.h, kdTreeKnlogn.h, kdTreeHeapSort.h 和 KdTreeMergeSort.h）构建并测试一个动态K-D树。 C++/kd-tree/test_kdtreedynamic.stats.cpp 文件及其关联的 .h 文件（kdTreeDynamic.stats.h, kdTree.h, kdTreeNode.h, KdTreeNlogn.h, kdTreeKnlogn.h, kdTreeHeapSort.h 和 KdTreeMergeSort.h）构建并测试一个动态K-D树，并可选择性地收集各种性能统计数据，包括直方图。 C++/kd-map/raw-pointers/test_kdmapdynamic.cpp 和 C++/kd-map/smart-pointers/test_kdmapdynamic.cpp 文件及其关联的 .h 文件（kdMapDynamic.h, kdMap.h, kdMapNode.h, kdMapNlogn.h, kdMapKnlogn.h, kdMapHeapSort.h 和 kdMapMergeSort.h）构建并测试一个基于动态K-D树的键值对多值映射。这些文件有两个版本：一个使用原始指针，另一个使用智能指针。 请参阅 test_kdtreedynamic.cpp、test_kdtreedynamic.stats.cpp 和 test_kdmapdynamic.cpp 文件以获取编译说明、-D 编译定义的解释以及命令行选项的说明。 Java/KdTreeDynamic/TestKdTreeDynamic.java 文件及其关联的 .java 文件（KdTreeDynamic.java, KdTreeStatic.java, KdTreeNlogn.java, KdTreeKnlogn.java, KdNode.java, MergeSort.java, NearestNeighborHeap.java, Pair.java, Paire.java 和 Constants.java）构建并测试一个基于动态K-D树的键值对多值映射。关于 Constants.java 中配置常量的解释，请参阅 TestKdTreeDynamic.java 中的注释。 `KdTreeDynamic` 类扩展自 `KdTreeStatic` 类。 **静态K-D树：** 多线程静态K-D树构建算法在以下在线文章中有所描述。 《计算机图形技术杂志》(JCGT) 的文章详细描述了一个 O[knlog(n)] 的K-D树构建算法，并将该算法的性能与一个 O[nlog(n)] 算法的性能进行了比较。 除了JCGT文章提供的 O[knlog(n)] 算法描述外，两篇arXiv文章中的第一篇包含了一个附录，描述了在JCGT文章中发表这些算法之后实现的改进。 两篇arXiv文章中的第二篇是一篇综述，对比了 O[knlog(n)] 和 O[nlog(n)] 算法与Yu Cao等人在期刊文章"A New Method to Construct the KD Tree Based on Presorted Results" (Complexity Volume 2020, Article ID 8883945, https://doi.org/10.1155/2020/8883945) 中提出的算法。 上述两篇arXiv文章都包含了在JCGT文章中发表这些算法之后实现的改进的C++代码，并描述如下。这些相同的改进可在此Github网页上获得。 C++/kd-tree/test_kdtree.cpp 文件及其关联的 .h 文件（kdTree.h, kdTreeNode.h, kdTreeNlogn.h, kdTreeKnlogn.h, kdTreeYuCao.h, kdTreeHeapSort.h 和 kdTreeMergeSort.h）通过 O[knlog(n)]、O[nlog(n)] 或 O[knlog(n)] + O[nlog(n)] 算法构建并测试一个实现集合的静态K-D树。 C++/kd-map/raw-pointers/test_kdmap.cpp 和 C++/kd-map/smart-pointers/test_kdmap.cpp 文件及其关联的 .h 文件（kdMap.h, kdMapNode.h, kdMapNlogn.h, kdMapKnlogn.h, kdMapHeapSort.h 和 kdMapMergeSort.h）通过 O[knlog(n)] 或 O[nlog(n)] 算法构建并测试一个基于静态K-D树的键值对多值映射。 请参阅 test_kdtree.cpp 和 test_kdmap.cpp 文件以获取编译说明、-D 编译定义的解释以及命令行选项的说明。 TestKdTreeStatic.java 文件及其关联的 .java 文件（KdTreeStatic.java, KdTreeNlogn.java, KdTreeKnlogn.java, KdNode.java, MergeSort.java, NearestNeighborHeap.java, Pair.java, Paire.java 和 Constants.java）构建并测试一个基于静态K-D树的键值对多值映射。关于 Constants.java 中配置常量的解释，请参阅 TestKdTree.java 中的注释。 **对数K-D树：** 一组大小按连续的2的幂次递增的静态K-D树形成一个动态K-D树（也称为对数K-D树），如 Overmars 和 van Leeuwen 在 "Two General Methods for Dynamizing Decomposable Searching Problems" (Computing 26:155-166, 1981) 中所描述。 Java/KdTreeLogarithmic/TestKdTreeLogarithmic.java 文件及其关联的 .java 文件（KdTreeDynamic.java, KdTreeStatic.java, KdTreeNlogn.java, KdTreeKnlogn.java, KdNode.java, MergeSort.java, NearestNeighborHeap.java, Pair.java, Paire.java, AvlTree.java, AvlNode.java 和 Constants.java）构建并测试一个基于对数K-D树的键值对多值映射。关于 Constants.java 中配置常量的解释，请参阅 TestKdTreeLogarithmic.java 中的注释。 `KdTreeLogarithmic` 类扩展自 `KdTreeDynamic` 类。 请注意，Java/KdTreeLogarithmic 目录中的关联 .java 文件与 Java/KdTreeDynamic/KdTreeDynamic.java 文件及其关联的 .java 文件不同。Java/KdTreeDynamic 目录包含基于动态K-D树的键值对多值映射的基本实现，而 Java/KdTreeLogarithmic 目录包含支持基于对数K-D树的键值对多值映射所需的扩展实现。

标签：C++, JS文件枚举, k-d树, 动态数据结构, 区域搜索, 反向最近邻搜索, 多维索引, 平衡树, 搜索算法, 数据擦除, 数据结构, 最近邻搜索, 查询算法, 空间数据结构, 算法, 自平衡树, 键值映射, 集合