2025 年 4 月 25 日更新. 最近有 UCR 做并行的同学来访问， 讲\(k\)d-tree, 写的十分好.
操作系统作业要写一下死锁检测 https://en.wikipedia.org/wiki/Banker's_algorithm
里面有一步大概是在所有进程的 required_resources 对应的向量里面找小于系统
available_resources 对应的向量， 更新 available_resources 再找，
重复这样的过程. 实际上就是在一些\(m\)维的点里面不断询问给定的一个 axis
parallel box 当中的点是哪些. 想用 kd-tree 让这个过程跑的更快一些，
于是开始找 c++ 的 kd-tree 实现.
理想的 implementation 应该是这样的: 点的类型是一个模板参数， kd-tree
只要求这个点的类型重载了<= 和[], 分别用来定义点的严格大小关系和取出第
k 维的值， 另外每个维度的值也应该重载<=, 应该真的支持 k 维的点，
期望复杂度能做到和理论一致 https://en.wikipedia.org/wiki/K-d_tree, 支持删除插入…
大概找了三个实现:
kdtree-cpp
这是个不错的实现， 作者写的代码比较简洁， 并且 knn
支持多种距离度量(继承DistanceMeasure类之后稍微修改就行了，
不过死锁检测也用不到 knn), 但是点的类型是
vector<vector<double>> 维度都需要运行时判断，
而且只有 knn 方面的函数， 另外还有std::nth_element的问题，
在 ikd-Tree 当中一起讨论. 不支持插入删除. 我觉得写的很好，
但是需要补充和调整很多东西才能用到别的地方去.
ikd-Tree
这个实现是在 arxiv 上一篇文章中用到的: https://arxiv.org/abs/2102.10808
看文章和测试的结果， 速度非常快， 支持插入删除，
而且直接提供了Box_Search这样的函数.
严重的问题是文章绝大部分和 github 的 README 当中都在说 kd-tree,
而且代码当中 PointType 也是一个模板参数， 但是只支持三维…
花了不少时间看文章和文档都没有发现…
更加严重的问题是std::nth_element, https://github.com/hku-mars/ikd-Tree/issues/25
在查询一个范围中的点时不能根据 kdtree
当中一个节点划分的维度对应的值来判断是应该向左子树还是右子树搜索. issue
当中已经给了一个例子.
nanoflann
我没仔细看， 根据 examples
他是支持任意维度的点插入删除的…看起来满足所有的要求.
在 ikd-Tree 的 issue 当中看到建树的时候直接用了
DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;