K-D Tree

先分析一下这个算法的名称：K 是维数，然后D是“Dimension”，维度

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

显然是一个数据结构

这个数据结构是处理在多维空间内关于“点”的问题

例如“平面内最远点对”，“k”远点对

无论是在几维空间里，都是有坐标轴的

在使用的时候有一种“坐标轴分治”的感觉

维护的信息：

split ：分裂坐标轴

ls、rs：左右儿子

node：该节点存储的真实点

 

然后是三个操作：建树，查询，插入

 

建树：

递归建树。类似平衡树

选择当前区域的点的各个维度的方差最大的维度（传说如果方差大，数据分散，复杂度或者精度有所保证？？），把这个维度当做split

这个节点的真实点就是c[mid]

然后，把这个维度[s]小于c[mid][s]的放在左边，大于的放在右边。

（实现时，用一个nth_element，再重载小于号，可以O(n)实现把中间的放在mid位置上，并且这个维度[s]小于c[mid][s]的放在左边，大于的放在右边。）

然后递归建树即可。

 

[学习笔记]K-D tree 随笔

x，y是split

 

这样，整个K-D Tree就把一些点分成了若干个块。

我们一块一块处理会比较容易剪枝。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄