RainAir
My OI Blog
RainAir
KD-Tree 学习笔记

K-D Tree,全名k-dimensional Tree,是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。K-D Tree是二进制空间分割树的特殊的情况,以下是一棵二维空间上的 k-d tree:
https://blog.aor.sd.cn/wp-content/uploads/2019/01/QQ截图20190131154516.png

建树

K-D Tree 的建树过程类似于平衡树:对于已知点集,求出其在某一维度上排序后的中间点,作为这个空间的分割点,然后把空间一分为二,再对每个部分递归建树,返回子部分分割点的编号,作为当前部分分割点的左右儿子。关于每次按照哪个维度排序,最好的方案是按照方差大小,但是为了简便我们就遍历每一维来建立。

其中 pushup 函数维护了 max 和 min 两个数组,用来存储每一个分割空间的极值。
https://blog.aor.sd.cn/wp-content/uploads/2019/01/QQ截图20190131154843.png

插入

插入的时候就是从根开始,判断这个点在分割点的那边,如果有的话就递归插入子节点,否则直接创建新的子节点(也和平衡树很像)
删除和插入差不多……

查询

查询时对于每一个被分割的点集,先利用到分割点的距离更新答案,然后判断边界是否能用于更新答案,如果能的话,就递归进入这个子区域更新答案。为了提高效率,我们贪心的选择答案更优的地方优先递归查询。

例题:BZOJ2648 SJY摆棋子
这个题目就是kdtree裸题呀。

结语

其实 K-D Tree 更像是一种优化暴力的方法,他常数比较大,有时候为了防止被出题人构造数据卡,需要使用类似于替罪羊树的思想来不断调整树的平衡。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/445
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/7f5c232e160bb21b4c009adb298fdcfa?s=80&d=mm&r=g

    Orz RainAir 一天学一个数据结构

    11月前回复
    • https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=80&d=mm&r=g
      RainAir博主

      @Siyuan: 您一天就学会了大部分省选数论内容 Orz
      详情可以看他的博客:D

      11月前回复
  • https://secure.gravatar.com/avatar/1a0f35ddca9473e8d761a8582c32ab70?s=80&d=mm&r=g

    wyh太强辣

    11月前回复
  • https://secure.gravatar.com/avatar/7f3e3b17f311325509d0e6c020040577?s=80&d=mm&r=g
    题出的好!难度适中,覆盖知识点广,题目又着切合实际的背景,解法比较自然。给出题人点赞 !

    orz 神wyh

    9月前回复

RainAir

KD-Tree 学习笔记
K-D Tree,全名k-dimensional Tree,是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。K-D Tree是二进制空间分割树的特殊的情况,以下…
扫描二维码继续阅读
2019-01-31
标签
近期评论