kNN 算法的 kd 树实现（ C 源码）

[begeekmyfriend]

https://github.com/begeekmyfriend/kdtree

特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。

实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。

注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。

有兴趣欢迎探讨。

[y8y]

我是第一个赞的，楼主的 C 代码看起来很舒服。

[zgqq]

大佬

[franklinyu]

除了「 for(; ;)」和「 8 個空格縮進」屬於口味不同以外，樓主的代碼簡直是一股清流……

[congeec]

正规军

[wujunze]

👍