DSA - 搜索树应用 2

发表于 分类于 阅读次数： 本文字数： 705 阅读时长 ≈ 3 分钟

数据结构负我！期中差点没及格。
今天太不幸了，两个星期前有个作业莫名其妙消失了我以为是我不小心做过了，今天突然发现其实是换了个地方所以我荣幸的没写作业，而且还他妈没有补交窗口。

kd 树

多维 D 树的意思。递归地划分平面，将分出来的矩形区域组织为一棵二叉树。根节点对应整个平面，交替按照 x，y 坐标划分。约定每个矩形左闭右开，下闭上开

建树：每个节点对应一次划分，也对应一个点集，对应平面上一个区域。当前点集不超过 1 个点就不再递归，然后按照轮换依次每个维度进行切割。取当前点集中切割维度的中位点作为代表，把点集分为两部分挂到左右子树上。

image-20260425165055866

如果是 2d 树的话可以组织成一棵四分树。

image-20260425165137170

对 kd 树而言，层高显然 O (logn)。任何同一层的节点所确定的区域没有交集，父亲的区域是儿子的区域之和。同一层所有节点的区域之和是整个平面。

做矩形查询的解可以划分成有限个区域之和

矩形查询：

和树套树类似，如果当前区域和查找区域没有交集就跳过，包含就全部整体输出，如果有交集但是不包含就递归深入继续切分。

image-20260425165755198

复杂度分析：预处理时间 $T (n)=2T (n / 2)+O (n)=O (nlogn)$

空间按层分析，1 + 2+4+…+O (2logn)=O(n)

查找时间复杂度，时间成本决定于递归调用的总次数，也即查询区域和边框的相交次数。只考查北方的那条边，因为任何一条边引发的递归次数和总次数渐进相等。再将边放大到一条直线可以得到上界。

image-20260425170610497 image-20260425170844841

考查这条直线和一个爷爷相交，那么在四个孙子中有两个绝对不可能相交。在四个孙子中最多两个与直线相交。

$Q(n)=2Q(n/4)+O(1),Q(n)=O(\sqrt{n})$

image-20260425171154090

在这种最坏情况下，查询区域和每个点区域都相交了一遍，$\sqrt {n}*\sqrt {n}$ 的区域，最多四倍根号 n