这是一个创建于 3247 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://github.com/begeekmyfriend/kdtree
特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。
实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。
注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。
有兴趣欢迎探讨。
特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。
实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。
注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。
有兴趣欢迎探讨。
 |
1
y8y 2017 年 2 月 22 日
我是第一个赞的，楼主的 C 代码看起来很舒服。
|
 |
2
zgqq 2017 年 2 月 22 日 via Android
大佬
|
 |
3
franklinyu 2017 年 2 月 23 日
除了「 for(; ;)」和「 8 個空格縮進」屬於口味不同以外，樓主的代碼簡直是一股清流……
|
 |
4
congeec 2017 年 2 月 23 日 via iPhone
正规军
|
 |
5
wujunze 2017 年 4 月 20 日
👍
|
Select Language