这一节的核心是如何把 BST 的“一维二分”思想扩展到“二维平面”。Page 16-172D 正交范围搜索的定义问题定义标准的符号表BST处理的是一维键一个数字。现在我们要处理二维键平面上的点(x, y)。插入/删除一个二维键。范围搜索Range Search给定一个轴对齐矩形找出所有落在该矩形内的点。范围计数Range Count统计落在该矩形内的点的数量。应用场景电路设计检查版图上某个矩形区域内有没有违规过孔、数据库查询某块地理区域内的兴趣点、网络查找 IP 地址段内的设备。Page 18-21网格实现的尝试与失败PPT 先提了一个“暴力空间划分法”网格Grid。物理动作把整个平面划分成M × M的小方格。每个点根据它的坐标被存到对应方格的链表里。查找时只看矩形覆盖到的那些方格。问题Page 20-21如果数据点分布不均匀Clustering网格就会失效。如果方格太大一个格子里挤了几百个点比如美国地图上的城市查找时依然要遍历大量数据退化为线性查找。如果方格太小格子数量爆炸浪费大量内存。PPT 的结论网格只对均匀分布的数据有效。真实数据如地图、网表往往是聚集的。因此需要一个能适应数据密度的结构。Page 22-23空间划分树kd-tree 的定位为了解决网格的“固定分辨率”问题PPT 引入了空间划分树Space-partitioning trees2d 树2d tree递归地把平面切成两半交替横切/竖切。四叉树Quadtree递归地把平面切成四块。BSP 树任意角度切分游戏中常用。这页的物理含义你现在要学的kd-tree2d 树是它的 2 维特例就是通过递归二分来适应数据分布。如果某个区域点很多树会在这里切得更密如果区域空旷树就不会在那里浪费节点。应用PPT 列出了一大堆——光线追踪、碰撞检测、飞行模拟器、N体模拟甚至《毁灭战士》Doom的渲染加速。它在图形学和处理高维空间数据时非常实用。Page 24-252d 树的构造物理规则这是最核心的物理实现部分。数据结构依然是Node含left、right指针但比较规则变了根节点使用x坐标比较。小的放左边大的放右边等价于在垂直方向切一刀。下一层子节点使用y坐标比较。小的放左边大的放右边等价于在水平方向切一刀。再下一层孙节点回到x坐标。规律按层级交替切换维度x - y - x - y ...。物理映射你在 BST 里做的compareTo(key)在这里变成了javaif (depth % 2 0) cmp x.compareTo(p.x); // 偶数层比 x else cmp y.compareTo(p.y); // 奇数层比 y内存布局依然是你熟悉的两指针节点。Page 26-282d 树的范围查找物理动作递归剪枝检查当前节点x是否在查询矩形内。如果是输出。剪枝判断如果当前节点是按x划分的且查询矩形的左边界大于节点x那么左子树的所有点都在左侧不可能在矩形内直接剪掉不递归。同理如果查询矩形完全在节点左侧右子树也剪掉。上面两个操作体现在几何上就是line与矩形相交。一旦某个节点的line与矩形相交则该节点下所有节点都要接受检查why递归搜索剩下的子树。时间复杂度Page 28平均情况R log N和 1D 范围查找类似但注意这里对比 1D 的log N是基于维度平衡的假设。最坏情况R √N。当树严重不平衡或者查询矩形极大且跨过中心导致剪枝失效时比如矩形覆盖半个平面必须遍历接近√N个节点。一、网格法缺陷-为什么要kd treesQPPT 的结论网格只对均匀分布的数据有效。真实数据如地图、网表往往是聚集的。因此需要一个能适应数据密度的结构。这里的意思是说如果我使用网格法想要在一个二维空间进行范围搜索或者范围计数会出现网格法下的问题是吗那么按照这些内容网格法下的问题应该指的是我不知道该把网格分的大还是把网格分的小如果把网格分的太大可能精度不够把网格分的太小就会导致计算复杂度变高这其实不太直观因为我们做二维的范围搜索和范围技术大底是什么呢或许我们可以先看做要找一个矩形内落的点这好像也是PPT上写的东西但是网格法很显然就无法正好适应那个矩形。或许PPT的意思是这样我们先用网格法分隔然后分出来的网格必须要把那个矩形给覆盖再在这些网格内找到矩形里面的点。那这么说好像就比较直观了。如果是在地图上也就是点出现的密集的数据集中做网格法再进行搜索可能依旧它的计算量是很大的因为一个小格内的点本来就非常多。那么另外一个问题是如果我们要搜索的范围不是一个很规整的图形就要涉及到网格的尺寸所以又回到尺寸问题。 是这样吗A理解完全正确网格法失败的两个物理核心数据的密度分布和查询形状的任意性。1. 关于“数据密集区”的理解你完全正确在地图上城市集中在东部西部是大片的空地。网格大了纽约那一格可能塞了几百个点。当你查一个小小的曼哈顿矩形时网格法会把整个纽约那一格几百个点全部倒出来然后你还要一个一个去判断它们是否在你那个小矩形里。你为了找 10 个点不得不去遍历几百个点这就是网格退化为线性扫描的原因。网格小了纽约那一格只有 1 个点但为了覆盖西部那些稀疏的点你要生成密密麻麻几十万个空网格占用了巨大的内存而命中率极低。结论网格法的缺陷是“分辨率”固定。它不管你是密集区还是稀疏区通通切成一样大的块所以无法适应数据本身的聚散。2. 关于“搜索形状任意”的理解你的补充非常深刻你说“如果搜索范围不是很规整就要牵扯到网格尺寸”——这个直觉太准了。即使所有数据是均匀分布的网格法也有这个问题它无法让网格边界刚好贴合查询矩形。假设你有一个矩形恰好跨在 4 个网格中间。网格法会把整个 4 个网格里所有的点都捞出来哪怕很多点在这个网格的远端根本不在你的查询矩形内然后你必须在外部再做一次精准的“点是否落在矩形内”的判断。如果这个查询矩形刚好横跨了 100 个网格的边缘你就要扫描这 100 个网格里的所有多余点。虽然它们可能只是“边界误差”但如果网格分得大这个误差带来的额外扫描量是很大的。3. 终极结论关于网格法PPT 展示网格法就是为了告诉你一个铁律“如果数据是分布不均匀的且查询范围是任意的固定分辨率的暴力划分网格在时间和空间上必然有一个会爆炸。”因为为了查得快粒度细空间爆炸内存满。为了省空间粒度粗时间爆炸扫描了太多无关点。所以你才需要后面那个kd-tree。它不固定分辨率只在有点的地方切没点的地方它就一个节点直接跳过了。它通过树递归地适应数据的疏密从而同时解决你刚才说的“密度分布”和“任意形状”带来的边界扫描问题。二、kd tree的数据结构Q节点2下把被1分出的1/2再分成两半。下一次切分的两条线挂在节点上面把2切出的空间再分成两半。下一次切分按y排序y小在左y大在右。节点1下的节点2、3按x轴排序节点2下的78按x轴排序。这个对不对A不对这一句有误。错误点“节点1下的节点2、3按x轴排序。”物理事实是节点2和节点3本身以及它们各自内部的左/右子树都是按Y 轴排序的因为下一层已经切换了维度。正确的表述应该是“节点2左子空间和节点3右子空间内部的数据在插入时按照Y 轴比较大小来决定挂在它们的左还是右。”而节点2和节点3自身的位置是由根节点节点1在深度 0 时比较 X 坐标决定的。一旦落入节点2左子空间后续的查找和插入就只看 Y 坐标了直到深度 2 再切回 X。修正后的完整逻辑链你需要记住的根深度0切 X → 分出“左半平面X小”和“右半平面X大”。深度1在左半平面和右半平面内部切 Y→ 分出“下Y小”和“上Y大”。深度2在每一个被 Y 切出的四分空间里切 X→ 所以节点2下的子节点7、8重新按 X 排序。以此类推X → Y → X → Y交替进行。我来把树的递归建树过程按 X → Y → X → Y 交替走一遍你就清楚它是如何对应到那些红色/蓝色分割线的根深度0切 X根节点是1 (35, 50)。按 X 坐标 35 切分左子树X 35包含点 3、4、5、6你树里的左分支。右子树X 35包含点 2、7、8、9、10你树里的右分支。深度1切 Y节点 3 (25, 42)左子树根按 Y 42 切分。左子树Y 42包含点 632,30右子树Y 42包含点 418,85、510,50。节点 2 (58, 60)右子树根按 Y 60 切分。左子树Y 60包含点 742,68——注意42,68的 Y 是 68 60按 Y 比较应该是在右子树我检查一下splits里的{axis:y, pos:61}大概是在这里用的我把坐标代入再看一遍。点7的坐标是 (42,68)Y68大于节点2的Y60所以按Y轴划分点7应该在右子树。嗯应该仔细计算一下点2是 (58,60)点7是 (42,68)点8是 (88,18)。按Y60切分Y60的包括点8 (88,18)Y60的包括点7 (42,68)、点10 (50,82)、点9 (78,29) 的Y是2960所以点9在左子树Y60。但是点7的Y6860所以点7在右子树Y60。实际上我重新仔细走一遍节点2是 (58,60)按Y60切分。左子树Y60包含点8 (88,18) 和点9 (78,29)因为2960。右子树Y60包含点7 (42,68) 和点10 (50,82)。但点7的X42点10的X50这会在下一层继续分。深度2切 X在节点 4 的左子树18,85下按 X 继续分节点 5 (10,50) 的 X 小于 18被分到左边。在节点 8 (88,18) 下按 X 继续分节点 9 (78,29) 的 X 小于 88被分到左边。在节点 7 (42,68) 下按 X 继续分节点 10 (50,82) 的 X 大于 42被分到右边。Q原来如此我好像明白了。这里的交替比较指的是我先用x把它们分成两半然后再在这两半下比较它们各自的y而不是不管第一层的x直接比较y是吗A是的。物理上它遵循的规则是“维度切换只在当前子树所管辖的‘子空间’内部生效。”我用你那个结构里的根节点1和它的左子树来拆开看根节点1按X划分。决策是X ≤ 35 的点进入左子空间X 35 的点进入右子空间。当程序进入左子空间以节点 3 为根时它不再在乎全局的 X 坐标。在这个被切出来的左半平面X 在 0~35 之间内部它开始按Y划分把 Y ≤ 42 的点放到节点 3 的左边Y 42 的放到右边。如果你“不管第一层的 x 直接比较 y”会怎样那就是把整个平面当成一个整体按 Y 坐标排序完全忽略根节点切出的左/右边界。这会导致左半平面原本存在的那些点比如点 4 的 Y85 和点 5 的 Y50在没有 X 约束的情况下跑到其他区域去比较破坏了原本由根节点 1 建立的平面分割。你问的“而不是不管第一层的 x 直接比较 y”——正是 kd-tree 和“全局交替排序”的本质区别。kd-tree 的比较是递归空间上的比较不是全局列表上的比较。正因为每一层的切分都严格限定在当前子矩形内kd-tree 才能保证查询时只要当前节点的边界线与查询矩形不相交就能安全地剪掉整棵子树。Q那我觉得我刚刚那个说法好像也没有问题孤立的看层与层之间不要看多层而是看两层的话确实它是我刚刚说的那种说法划分的。也就是如果这一层是被按照x划分那么下一层就是被按照y来划分。我认为体现在节点2下就是把被1分出的1/2再分成两半而下一次切分的线78按y排序y小在左y大在右。等等我之前说节点1下的节点2、3按x轴排序节点2下的78按x轴排序这是错的。7在线2下面8在线2上面。我知道了因为它们正好也符合7的x小于8对于别的线也是如此所以我误解了。这里的本质其实是当线把空间切成两半以后左半的空间和右半的空间被隔开那么左半后续的切分线只属于左半右半后续的切分线只属于右半。对于上下也是如此。A这句话就是 kd-tree 物理机制中最核心、也最容易被误解为“排序”的边界条件。你说对了。之前的误解“节点1下的节点2、3按 X 轴排序”根源于一个视觉巧合在你的数据里节点7的 X 坐标42恰好小于节点8的 X 坐标88。所以在图上看起来它们好像依然在遵循 X 轴的左右顺序。但物理事实是节点7和8之所以分别挂在节点2的左/右是因为在那一层深度1比较的是 Y 坐标而不是 X 坐标。你提炼出的这句话“左半的空间和右半的空间被隔开那么左半后续的切分线只属于左半右半后续的切分线只属于右半。”这个判断在物理上完全正确而且它正是 kd-tree 与普通 BST 最底层的分水岭。普通 BST左子树和右子树是“数值范围”的集合。根节点是 35左子树的值都小于 35右子树的值都大于 35。但是左子树内部的节点比如 18 和 25之间并没有“物理上的边界线”——它们只是值的大小不同。kd-tree根节点沿 X35 切了一刀后左子树实际上被物理地限制在了x ∈ [0, 35]这个矩形区域内。节点3和4在这个区域内无论怎么切它们画出的横线Y或竖线X绝对不能越过 X35 这条边界。它们只在自己的半区里活动。同理节点7和8在右半区x ∈ [35, 100]里活动它们的切割线也不会越过边界到左半区去。这种“物理互不侵犯”的性质正是 kd-tree 能够在范围查找时直接剪掉整棵子树而不需要遍历它的根本原因——因为如果查询矩形完全落在x 35的区域右半区的整棵树就可以直接忽略不需要检查里面的任何节点。你提炼出的这个“隔离性”就是 kd-tree 剪枝效率的物理基础。Q那么我明白了一旦被分开那么后面的子树节点它都是进行了一个范围限定的所以这才叫做不断的在把矩形给切分开。例如如果第二层的节点2也就是深度为一的层数中的节点2它是y数a的话则它左子树的所有点的y轴坐标都会小于a右子树的所有点y轴坐标都会大于a。A正确。针对你举的例子深度为 1 的节点 2按y a切分它左子树深度 2 及以下里的所有点其y坐标都小于a。它右子树里的所有点其y坐标都大于a。关键物理补充“范围限定”的完整含义你提到的“范围限定”不止是“小于a”或“大于a”它继承了它前面所有祖先的限制。例如节点 2 是根节点 1 的右子树比如根节点 1 按x 35切分节点 2 在右半区。那么节点 2 的左子树里的点它们必须同时满足x 35继承自根节点且y a节点 2 自己的限制。所以kd-tree 的每一次“切分”都是在当前矩形内部画一条线把矩形一分为二。后代节点的范围永远被限定在那个小矩形里。你理解的“不断的在把矩形给切分开”就是 kd-tree 最底层的物理动作。三、2d树代表的空间划分物理动作递归剪枝检查当前节点x是否在查询矩形内。如果是输出。剪枝判断如果当前节点是按x划分的且查询矩形的左边界大于节点x那么左子树的所有点都在左侧不可能在矩形内直接剪掉不递归。同理如果查询矩形完全在节点左侧右子树也剪掉。上面两个操作体现在几何上就是line与矩形相交。一旦某个节点的line与矩形相交则该节点下所有节点都要接受检查why递归搜索剩下的子树。Q我对这个问题的描述还不精确2d tree本质上就是在1d tree上做了一种变式或者说将它的每一层的含义视作一个2d上的含义。具体来说它的应用场景是这样的我们现在在二维平面上有一些点当我使用一个方框把它们框出我需要知道这些点的个数或者是每个点都是什么。那么一个非常直观能想到的方法就是方格法使用方格法我们就把这块画布上也就是这块二维空间上的面积都方格化而后选出能够覆盖这个矩形的方格再在方格内部逐一进行搜索。然而这种方格法具有致命的缺点那就是方格的大小不容易选定以及方格内部的点分布可能不均匀。如果方格选小了那么运行时间将会更长。而如果方格选大了运行内存就要更大。方格中的点不均匀造成的后果大约是如果你选中了一个内部具有很多点的方格则或许大部分的遍历都是无用的。那么针对这个就使用binary search trees来解决二维空间上的搜索问题。具体的方法是这这些点所分布的空间中我使用一条穿过这个点的线对空间进行切分。第一条线把空间切分成两半。接下来的两条线又把上一条线切分出来的空间各自分成两半。这个时候就会有四半。而2叉树这里的分叉所指的就是坐标的大小第一层纵切的话空间就被分成左半和右半那么这一层下面的左子树就全部都是左半空间的内容右子树全部都是右半空间的内容他们天然就符合x轴小于和大于切分处的关系。接下来的切分就将是横切又再次把后续内容切成y轴大小关系的不同分支。而一个叶子节点则继承了前面所有祖先节点的限制条件。当我们根据空间内的点完成这些切分则可以开始搜索矩形框选注的内容其搜索的方式是这样从树的根中进入查看这个坐标是否落在矩形中。如果矩形的坐标比根的坐标小我们就进入左子树右子树将不会被访问在几何上就是右边的一半被砍掉不需要再进行搜索。直到我们在某个节点它的坐标落在了矩形的范围内则对这个节点下的所有子节点进行遍历看他们是否被矩形所包括。这样每次进入一个节点这个节点没有落在矩形的范围内就是对我们的搜索范围切一刀缩小范围。我想这种方法的优势应该是不需要进行全部的遍历每次进入一个根节点以后它的后续数据搜索量都是进入之前的大约1/2以节点都在来算的话。这样不但数据搜索量的减少是快速的并且不会出现分布不均匀的情况。而后我看到这样的说法关于搜索算法你对“落入矩形则遍历所有子节点”的表述可以再精确一点。在kd-tree搜索中更准确的说法是如果当前节点所代表的整个子空间与矩形区域有重叠就需要进入该子树搜索如果没有重叠就直接剪枝而不是单纯看“节点坐标是否在矩形内”。为什么说节点代表了整个子空间似乎确实如此但这种节点所代表的子空间好像并不是直接由当下这个节点所代表的。不如说是这样例如在深度为零的第一层我们分了一个x小于35跟x大于35而如果进入到x小于35中的左节点在y的层面我们触碰到了那个矩形所代表的就是x小于35的这个子空间是我们所要搜索的空间并且我们已经无法再进行更多的修剪了。我所说的进入到某个节点以后触碰到那个矩形指的是例如节点三是在y轴的大小上进行切分的而如果节点三所在的y轴与矩形所在的y范围相交我们就必须遍历节点三下的每一个子节点。关于这一点普林斯顿算法课口述的是当节点三所在的这条线与矩形相交那么我们就必须要遍历节点三下的所有子节点它使用的不是子空间这个概念。但是我认为子空间这个概念应该是更准确的。所以我因此认为节点三所代表的子空间并不是由节点三所切分出来的而是由节点一所切分出来的小于x35的部分。也就是说该节点所代表的子空间其含义并不由那一层所赋予而是由上一层赋予。A“这条线与矩形相交”确实是一个用来快速判断的视觉捷径。但“子空间”概念才是 kd-tree 在物理上真正执行检查的精确单位。我们来确认你最后那个结论的物理正确性“节点三所代表的子空间其含义并不由那一层节点三自身所赋予而是由上一层节点一赋予。”物理上完全正确。节点 3 自身那条y 42的线它的作用不是用来定义“节点 3 本身占据了哪块区域”而是用来把节点 3 继承到的这块区域由节点 1 切出来的左半平面再切分给它的两个孩子节点 4 和节点 6。节点 3 的“子空间”边界框就是它从根节点 1 继承来的那块矩形——x ∈ [0, 35], y ∈ [0, 100]。它自己那条y 42的线只是把这块矩形内部划开并不改变这块矩形本身的边界。当你检查节点 3 时你需要检查的是它继承来的整块矩形[0,35]×[0,100]是否与查询矩形相交。如果相交你才进入节点 3然后才看它那条y42的线决定下一步去左子树还是右子树。也就是说“子空间”继承来的矩形由所有祖先共同决定。“节点的线”在这个矩形内部的划分线用来决定子树的走向。Q但是这种切分使我感到疑惑因为我们仅仅只是切掉了其中不知道是不是一半的点也就是右子树而后节点三下的点与矩形相交的也并不多我们依旧做了大量无用的遍历。 并且这种方式对我来说也很新奇它的作用是把点映射成了某种切分空间的线而这种点就同时具有了切分和代表一个子空间的含义。可是这种切分又如何来确定其顺序呢它的代码又是怎样的呢A1. 关于“大量无用的遍历”——你的直觉是对的但这是物理代价的硬性下限你感觉“节点三下的点与矩形相交的并不多我们依旧做了大量无用的遍历”——这在物理上完全正确也是 kd-tree 范围搜索Range Search不可避免的代价。我直接给你看它的复杂度公式你就知道为什么“虽然有无用遍历但它依然是革命性的”暴力遍历检查N个点。kd-tree 2D 范围搜索在最坏情况下检查√N R个节点其中R是落在矩形内的点数。举个例子如果N 1,000,000暴力检查你需要碰 1,000,000 个点。kd-tree你最多需要碰√1,000,000 1,000个节点再加上实际命中的点数。为什么你感觉“大量无用”因为你拿到的节点三下面可能只有 1 个命中的点但你为了找到它可能先碰了 100 个无关的节点因为它所在的那个大方框与矩形相交了你不得不进去查看。但是如果你用暴力遍历那 100 个无关的节点就变成了 1,000,000 个无关的节点。kd-tree 把“无用遍历”从“全体”压缩到了“边界附近”的一小部分。这种“无用遍历”的量是由树在边界处的深度决定的。你看到的“节点三下的点与矩形相交的并不多”就是R很小但√N依然存在的物理体现。2. 关于“点同时是切分线和子空间”——你的观察极其精准你注意到“这种点就同时具有了切分和代表一个子空间的含义。”这正是 kd-tree 与普通 BST 最底层的物理分水岭普通 BST 的节点仅仅代表一个“值”。左子树是“小于值”右子树是“大于值”。节点本身没有“占有”一块二维区域。kd-tree 的节点代表一条穿越点且无限延伸的线。这条线一旦画出就定义了它后代所在的“半平面”。当你深入树时后代节点的所有坐标都被这条线限制了范围。你捕捉到的“双重含义”作为“分割者”它的坐标决定了左/右子树或上/下子树的阈值。作为“子空间”的代表它自身所在的那个小矩形是由它所有祖先的线共同“围出来”的。这个矩形内部的所有点构成了它的子树。3. 关于“顺序和代码”——直接给你看物理比较规则你问“这种切分又如何来确定其顺序呢它的代码又是怎样的呢”它的代码比你想象的还要简单——就是普通的 BST 插入只是比较的字段compareTo会按层次切换。我直接写出来你就明白它和普通 BST 的区别只有这一行javapublic void insert(Node parent, Point p, int depth) { if (parent null) return new Node(p); // 关键区别就在这里按层次决定比 X 还是比 Y if (depth % 2 0) { // 偶数层比 X cmp p.x - parent.point.x; } else { // 奇数层比 Y cmp p.y - parent.point.y; } if (cmp 0) parent.left insert(parent.left, p, depth 1); else parent.right insert(parent.right, p, depth 1); }顺序插入规则深度 0根比x。x小的去左子树大的去右子树。深度 1第一代孩子比y。y小的去左子树大的去右子树。深度 2第二代孙子回到比x。以此类推x - y - x - y...Q但我真正的疑惑是例如之前我给你看的点是有九个还是十个对不对那么我插入的顺序不一样就会导致最终搜索的时间复杂度不一样这个插入顺序是怎么决定的呀A在标准的、教科书级别的 kd-tree 实现中插入顺序不是“由你决定的”而是“由点的坐标分布决定的”。你根本不需要手动决定插入顺序因为这类树通常不是通过“逐个插入”来构建的而是通过“递归中位数切分”来静态构建的。1. 如果我像普通 BST 那样逐个插入会发生什么你担心的场景如果你真的拿到一个空树然后insert(point1)、insert(point2)……这样逐个插入就像普通 BST 一样那么插入顺序确实决定了树的形状。如果你按x坐标从小到大插入树会退化成一条右向链表高度变成N搜索变成O(N)。这就是你担心的“插入顺序导致时间复杂度不同”的情况。在线插入Online Insertion的 kd-tree 确实有这个致命缺陷。但是工业界和教材里使用的 kd-tree几乎从不这样构建。2. 标准 kd-tree 是怎么构建的静态中位数切分在实际应用中点集通常是预先全部已知的。因此构建 kd-tree 的标准算法是“静态构建”或“离线构建”。步骤如下取当前子空间的所有点初始是整个根矩形。按当前维度X 或 Y对所有点进行排序。选择排序后的中位数点作为当前子树的根节点。左侧的点全部进入左子树右侧的点全部进入右子树因为它们分别小于和大于中位数的坐标。递归对左子树和右子树分别执行上述操作并在下一层切换到另一个维度Y 或 X。这个构建顺序完全由点的坐标值决定完全不受你输入列表的原始顺序影响。3. 套用你那张图10 个点在你那张图里如果你用“静态中位数构建”第一步深度 0按 X会对所有 10 个点的x坐标排序选出中位数比如点 3 或点 6取决于具体坐标。根节点不会是点 1而是中位数点。第二步深度 1按 Y在左半平面x 根.x和右半平面x 根.x内部分别按y坐标排序各自选出中位数作为子树的根。所以这棵树的根节点、第二层节点都是由“坐标的几何位置”决定的而不是由“你最先输入哪个点”决定的。4. 那“插入顺序”还有意义吗只在一种情况下有意义如果你要维护一个动态变化的点集不断有新的点加入。在这种情况下你无法预先知道所有点所以只能在线插入。但为了不让树退化工程上通常不会用纯粹的 kd-tree 在线插入而是用scapegoat树替罪羊树或定期重建的策略插入新点后检查树是否失衡比如高度超过2 * log N。如果失衡就把整棵子树或整棵树拉平重新用“静态中位数切分”重建。但是普林斯顿这一节几何搜索讲的是静态应用比如给定一堆点建立索引后只做查询不频繁插入新点。因此PPT 默认使用的是“静态中位数构建”所以插入顺序这个变量在教材的讨论里根本不存在。你脑海里的“插入顺序影响树形状”是普通 BST 的思维模型。对于 kd-tree在应用层面它通常被绕过用中位数构建来保证严格平衡。你不需要为“顺序”操心只需明白“递归排序后选中位数”这个物理机制。这和你之前学的归并排序在“建树”上的逻辑类似——先把数据一次性排好再切分。四、kd tree的时间复杂度最坏情况R √N。当树严重不平衡或者查询矩形极大且跨过中心导致剪枝失效时比如矩形覆盖半个平面必须遍历接近√N个节点。Q最坏情况为什么是接近根号n个而不是n个毕竟一旦矩形跨过中心那么中心下的所有子节点都要被遍历一遍不是吗A不是的。关键在于“跨过中心的矩形”并不覆盖“中心下的所有子节点”。这个 N^(1/2)​ 的根源不是“碰到的节点多”而是“碰到的边界线多”。1. 为什么一个横跨中心的矩形不会导致遍历N个节点你的推理“横跨中心→遍历所有子节点”隐含了一个假设一旦进入某个子树就必须扫描该子树里的所有节点。但物理上剪枝检查发生在每一层而不是只在根节点。举个例子根节点按x切分矩形横跨了左半和右半所以你确实要进入左子树和右子树。在左子树深度 1按y切分里即使矩形整体横跨了中心x方向它的y范围可能只在中间一条带比如y从 40 到 60。此时左子树的根节点按y切会检查它的左右子树如果y切分线在 50且矩形的y范围是[40, 60]那么它的左子树y 50和右子树y 50都会与矩形相交都要进入。但在深度 2按x切时矩形可能完全覆盖某些子空间也可能完全不覆盖某些子空间。那些完全不覆盖的子空间依然会被立即剪掉。结论横跨中心的矩形不会让你遍历整棵树。它只能让你在每一层都多走几条路径但那些路径上的节点依然会在遇到与矩形完全不重叠的子空间时被剪掉。你最后遍历到的节点是所有与矩形边界相交的节点而不是矩形内部的节点。2.√N的物理来源边界节点数量在 2D 平面上一个平衡的 kd-tree 会把空间划分成大约N个叶子单元格。如果一个查询矩形与这个平面相交被剪枝过程“触及”的节点其数量不是与面积成正比而是与矩形边界穿过的单元格数量成正比。在一个√N × √N的网格中一条直线或一个矩形边界穿过的格子数量是O(√N)。kd-tree 的搜索行为等价于遍历所有与查询矩形边界相交的节点。内部命中点只贡献R完全不重叠的被剪掉。最坏情况就是你构造一个查询矩形它像一条细长的“对角线”带横跨整个区域恰好避开了所有内部点R0但与很多分割线相交。此时你要遍历的边界节点数量正是O(√N)量级。3. 什么时候会退化为N当查询矩形是整棵树的包围盒即覆盖整个空间时剪枝完全失效你必须遍历所有N个节点才能输出R N个点。但在 PPT 里这种退化被划入R的范畴因为R √N中的R占了主导变成了N √N复杂度依然是O(N)由输出规模决定。所以√N描述的是“当R远小于N时你不得不额外检查的冗余节点数量”。这不是算法设计上的缺陷而是 2D 平面几何的硬性规律——任何基于空间划分的搜索算法在查询边界上都会遇到这个由“周长”而非“面积”决定的额外开销。你会感觉它不合理是因为你心里想的是“面积覆盖”而 kd-tree 的剪枝查的是“边界相交”。根源混淆了“进入这个节点”和“遍历这个节点的所有子节点”所谓“直线跟矩形相交 → 该节点下的所有子节点全部遍历。”物理事实直线跟矩形相交 →你只是“获得许可”进入这个节点。进入之后你必须继续检查这个节点的左右子节点所代表的子空间并根据检查结果决定是剪掉还是继续深入。“进入”和“遍历全部”是两件完全不同的事。