https://github.com/begeekmyfriend/kdtree
特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。
实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。
注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。
有兴趣欢迎探讨。
特点：绝对平衡，搜索极快，代价是动态性差，每次增删后需要重建。
实现是对增删进行缓存，直到重建才映射到实际数据结构中去。重建会对每个维度分量进行快速排序，以确保每个树节点都是取中值，实现了绝对平衡，也即最小高度，最大限度降低搜索比较次数，杜绝最差情况发生。
注意，排序只是对数据样本的索引进行移动，数据本身插入时只拷贝一次，数据样本集中缓存有利于 cache 命中。
有兴趣欢迎探讨。
Select Language