K-D树
前言
kd-tree（k-dimensional树的简称），是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）
好像跟没说一样
K-D树其实是每个结点为K维数值点的二叉树
每个结点将某一维划分成两部分
一部分为左子树
一部分为右子树
所以说，当\(k=1\)时，kd树每个点都只划分这一维，其实是二叉搜索树
在我们算法竞赛中，通常\(k=2\)
下面这棵树就是\(k=2\)的
它的结点交替地分了一维和二维 就像这样
红线是按照根结点\((7,2)\)的x维分的
蓝线是结点\((7,2)\)的左右子结点\((5,4)\) \((9,6)\)的y维分的
下次再按子节点的x维分
......
这就是K-D树的一种建树方法：每一维交替建树
那么我们就开始说如何建树
操作
建树
K-D树建树的一般过程为：
- 选择某个维度
- 取数据在该维度的中位数（可以使左右子树的大小相等）作为分割的线
- 将小于中位数的数据点放到左子树
- 将大于等于中位数的数据点放到右子树
这就引出了两个问题
- 如何选择维度
- 如何计算中位数
划分维度的选择
有三种方法
- k维交替建树(离线)
就是按顺序 每一维依次划分
上面的例子就是这种方法 按照x和y依次划分的
操作的时候可以用取余运算
第 \(i\) 层按照 \(i\) \(mod\) \(k\) 维划分
- 最大方差法(离线)
第一种方法并不是最优的
对于一组数据 方差越大 数据越分散（初中数学）
所以从方差大的维度分 可以更优
不过 谁(sei)还这么做啊
梅姐又附体
3.动态插入法(在线)
把每一个点依次插入 不平衡就拍扁重建 插入操作在后面
为了方便，在算法竞赛中，最常用的是第一种方法
计算中位数
有个stl就可以计算(狂喜)
nth_element(ps+1,ps+mid,ps+r,cmp);
表示对\(ps\)数组中下表为\([l,r)\)的元素按cmp的规则重新布置(没排序)，使得\(ps[mid]\)存放着中位数，小于等于中位数的放在\([l,mid]\)中(没排序)，大于中位数的放在\([mid+1,r]\)中(没排序)
之后我们就可以建树了
代码长介样
跟线段树好像
int build(int l,int r,int wd)
{
if(l>r)return 0;
int mid=(l+r)>>1,k=newnode();
WD=wd;//每次按照当前维度排序
nth_element(p+l,p+mid,p+r+1,cmp);
t[k].pt=p[mid];
t[k].lc=build(l,mid-1,wd^1);
t[k].rc=build(mid+1,r,wd^1);
update(k);
return k;
}
插入
类似于BST的插入
到每一维判断该是左右哪个子树就好
void ins(int &k,point tmp,int wd)
{
if(!k)//新建节点
{
k=newnode();
t[k].lc=t[k].rc=0;
t[k].pt=tmp;
update(k);
return ;
}
if(tmp.x[wd]<=t[k].pt.x[wd])ins(t[k].lc,tmp,wd^1);
else ins(t[k].rc,tmp,wd^1); //判断应该插入进左子树还是右子树中
update(k);
}
但是插入多了就会不平衡
所以可以像替罪羊树一样设一个平衡因子
对于看不惯的不平衡的直接拍扁重建
不得不提某人的逆天发言
不写替罪羊 当点多了的时候直接把整棵树重建
还有查找k远点 最近点等操作 跟具体题有关了
大概就写完了
撒花撒花
附例题
引用来源
K-D Tree - OI Wiki (oi-wiki.org)
还有书
标签：结点,wd,int,mid,博客,中位数,维度 From： https://www.cnblogs.com/zysssss/p/18083252