k-d树

✍ dations ◷ 2025-04-02 20:41:47 #数据结构,树结构

在计算机科学里,-d树( k-维树的缩写)是在维欧几里德空间组织点的数据结构。-d树可以使用在多种应用场合,如多维键值搜索(例:范围搜寻及最邻近搜索)。-d树是空间二分树(Binary space partitioning)的一种特殊情况。

-d树是每个叶子节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点,节点右边的子树代表在超平面右边的点。选择超平面的方法如下:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法线为x轴的单位向量。

有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种创建-d树的方法。最典型的方法如下:

这个方法产生一个平衡的-d树。每个叶节点的高度都十分接近。然而,平衡的树不一定对每个应用都是最佳的。

function kdtree ( pointList,  depth){        var  axis := depth mod k;                select median by axis from pointList;                var  node;    node.location := median;    node.leftChild := kdtree(points in pointList before median, depth+1);    node.rightChild := kdtree(points in pointList after median, depth+1);    return node;}

插入元素

移除元素

平衡

在动态插入删除点且不允许预处理插入操作的情况下,一种平衡的方法是使用类似替罪羊树的方法重构整棵树。

最邻近搜索用来找出在树中与输入点最接近的点。

k-d树最邻近搜索的过程如下:


维数灾难让大部分的搜索算法在高纬情况下都显得花哨且不实用。 同样的,在高维空间中,k-d树也不能做很高效的最邻近搜索。一般的准则是:在k维情况下,数据点数目N应当远远大于 2 k {\displaystyle 2^{k}} 时,k-d树的最邻近搜索才可以很好的发挥其作用。不然的话,大部分的点都会被查询,最终算法效率也不会比全体查询一遍要好到哪里去。另外,如果只是需要一个足够快,且不必最优的结果,那么可以考虑使用近似邻近查询的方法。

相关

  • 伯里克利伯里克利(古希腊语:.mw-parser-output .Polytonic{font-family:"SBL BibLit","SBL Greek","EB Garamond","EB Garamond 12","Foulis Greek",Cardo,"Gentium Plus",Gentium,"Th
  • 和平伙伴关系计划和平伙伴关系计划(英语:Partnership for Peace,缩写PfP)是北大西洋公约组织旗下的一个项目,旨在于北约成员国、前苏联和前南斯拉夫加盟国以及其它欧洲国家之间建立双边合作与互信
  • 科威特城科威特城(阿拉伯语:مدينة الكويت)位于科威特东部波斯湾畔,是科威特的首都和首都省的首府。http://www.hko.gov.hk/wxinfo/climat/world/chi/asia/westasia/kuwait_c.
  • 德国新浪潮德国新浪潮(德语:Neuer Deutscher Film,也称为Junger Deutscher Film)又称德国新电影,是影评人对于1960年代末至1980年代的一些德国导演与他们的电影作品所给予的称呼,他们主要受
  • 性联遗传伴性遗传即遗传基因位于性染色体上的遗传现象。男性个体的X染色体一定是来源他的母亲,而他本人又一定是将其传给女儿,不会传给他的儿子;然而,女性个体的两条X染色体分别来源于她
  • 己巳己巳为干支之一,顺序为第6个。前一位是戊辰,后一位是庚午。论阴阳五行,天干之己属阴之土,地支之巳属阴之火,是火生土相生。中国传统纪年农历的干支纪年中一个循环的第6年称“己巳
  • 佩索亚费尔南多·佩索阿(葡萄牙语:Fernando Pessoa,1888年6月13日-1935年11月30日),生于里斯本,是葡萄牙诗人与作家。 他生前以诗集《使命》而闻名于世。 他被认为是继路易·德贾梅士之后
  • 贝蒂·怀特贝蒂·玛丽咏·怀特(英语:Betty Marion White,1922年1月17日-),是一位美国演员,曾四次提名金球奖最佳音乐及喜剧类女主角,她亦是出演电视剧职业生涯最久的喜剧演员。除了身为电视剧
  • 高浪浦第1师第1师第6师高浪浦战役,是朝鲜战争开始后,朝鲜人民军越过38线全面南侵而发起的战役,结果是韩国高浪浦里(朝鲜语:장남면)落入朝军手中。
  • 玛格丽特·汉密尔顿玛格丽特·希菲尔德·汉密尔顿(英语:Margaret Heafield Hamilton,1936年8月17日-),美国计算机科学家,系统工程师和企业家,曾担任MIT仪器实验室(英语:Charles Stark Draper Laboratory)