k-d树

✍ dations ◷ 2025-04-04 20:23:19 #数据结构,树结构

在计算机科学里,-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树的最邻近搜索才可以很好的发挥其作用。不然的话,大部分的点都会被查询,最终算法效率也不会比全体查询一遍要好到哪里去。另外,如果只是需要一个足够快,且不必最优的结果,那么可以考虑使用近似邻近查询的方法。

相关

  • 贾汉吉尔贾汉吉尔 (英语 : Jahangir)(1569年8月31日-1627年10月28日),是统治印度次大陆的莫卧儿帝国的第四任皇帝,生于1569年,死于1627年。他被认为是莫卧儿帝国最伟大的皇帝之一。他在其
  • 艾力克·斯托克斯艾力克·斯托克斯(Alec Stokes,1919年6月27日-2003年2月5日)是1940年代到1950年代间,伦敦国王学院的DNA研究团队成员之一。他曾与罗莎琳·富兰克林、雷蒙·葛斯林、莫里斯·威尔
  • 伊塔洛·斯韦沃笔名伊塔洛·斯韦沃(Italo Svevo),意大利犹太商人兼小说家。埃托雷·施米茨(Ettore Schmitz,1861年12月9日─1928年9月13日)为他的本名,大器晚成,60岁后才写出成为名之作《季诺的意
  • 拉安戈斯图拉镇拉安戈斯图拉镇是阿根廷的城镇,位于该国西部讷韦尔瓦皮国家公园,由内乌肯省负责管辖,面积79平方公里,海拔高度780米,2001年人口7,526。
  • 尤里卡尤里卡县(英语:Eureka County),美国内华达州中部的一个县,面积10,826平方公里。根据2010年人口普查,本县共有人口1,987人。本县县治为尤里卡(Eureka)。本县于1873年3月1日成立,县名是
  • 洪知秀洪知秀(朝鲜语:홍지수 Hong Ji Soo,英语:Joshua Jisoo Hong,1995年12月30日-),以艺名Joshua(朝鲜语:조슈아 Jo Syu A,日语:ジョシュア Jo Shu A)为人熟识,是一名在韩国发展的韩裔美籍男
  • 荷兰国徽荷兰国徽于1815年8月24日开始使用。中心图案为一盾徽,蓝底,饰以黄色长方形小块。中间为一只头戴金冠、呈忿怒状的金色、红舌红爪,手持剑和代表七个省份的箭枝的狮子。上有王冠
  • 佩特里·福塞尔佩特里·福塞尔(芬兰语:Petteri Forsell;1990年10月16日-)是一位芬兰足球运动员。在场上的位置是攻击型中场。他现在效力于芬兰足球超级联赛球队玛丽港。他也代表芬兰国家足球队
  • 圣雅各教堂 (吕贝克)坐标:53°52.2564′N 10°41.3376′E / 53.8709400°N 10.6889600°E / 53.8709400; 10.6889600圣雅各教堂(德语:)是德国路德会在吕贝克旧城区的五座主要教堂之一。 它成立于133
  • 土耳其宗教土耳其宗教(2016)伊斯兰教是土耳其的主要宗教,根据国家的规定,99.8%的人口自动被国家登记为穆斯林,如果父母任何一方都没有任何其他官方认可的宗教信仰。由于这种方法,穆斯林的官方