热线电话：13121318867

登录
首页精彩阅读KD树的删除​_数据分析师
KD树的删除​_数据分析师
2014-12-03
收藏

KD树的删除_数据分析师

 KD树的删除可以用递归程序来实现。我们假设希望从K-D树中删除结点（a,b）。如果（a,b）的两个子树都为空，则用空树来代替（a,b）。否则，在（a,b）的子树中寻找一个合适的结点来代替它，譬如(c,d)，则递归地从K-D树中删除（c,d）。一旦(c,d)已经被删除，则用（c,d）代替（a,b）。假设(a,b)是一个X识别器，那么，它得替代节点要么是（a,b）左子树中的X坐标最大值的结点，要么是（a,b）右子树中x坐标最小值的结点。
    也就是说，跟普通二叉树(包括如下图所示的红黑树)结点的删除是同样的思想：用被删除节点A的左子树的最右节点或者A的右子树的最左节点作为替代A的节点(比如，下图红黑树中，若要删除根结点26，第一步便是用23或28取代根结点26)。
   当(a,b)的右子树为空时，找到（a,b）左子树中具有x坐标最大的结点，譬如（c,d），将(a,b)的左子树放到(c,d)的右子树中，且在树中从它的上一层递归地应用删除过程（也就是（a,b）的左子树） 。
    下面来举一个实际的例子(来源：中国地质大学电子课件，原课件错误已经在下文中订正)，如下图所示，原始图像及对应的kd树，现在要删除图中的A结点，请看一系列删除步骤：
    要删除上图中结点A，选择结点A的右子树中X坐标值最小的结点，这里是C，C成为根，如下图：
     从C的右子树中找出一个结点代替先前C的位置，
    这里是D，并将D的左子树转为它的右子树，D代替先前C的位置，如下图：
    在D的新右子树中，找X坐标最小的结点，这里为H，H代替D的位置，
    在D的右子树中找到一个Y坐标最小的值，这里是I，将I代替原先H的位置，从而A结点从图中顺利删除，如下图所示：
    从一个K-D树中删除结点(a,b)的问题变成了在(a,b)的子树中寻找x坐标为最小的结点。不幸的是寻找最小x坐标值的结点比二叉检索树中解决类似的问题要复杂得多。特别是虽然最小x坐标值的结点一定在x识别器的左子树中，但它同样可在y识别器的两个子树中。因此关系到检索，且必须注意检索坐标，以使在每个奇数层仅检索2个子树中的一个。
    从K-D树中删除一个结点是代价很高的，很清楚删除子树的根受到子树中结点个数的限制。用TPL（T）表示树T总的路径长度。可看出树中子树大小的总和为TPL（T）+N。 以随机方式插入N个点形成树的TPL是O(N*log2N),这就意味着从一个随机形成的K-D树中删除一个随机选取的结点平均代价的上界是O(log2N) 。CDA数据分析师官网


CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想查询CDA考试成绩，点击>>> “CDA成绩” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

▷ 想获取CDA考试时间/费用/条件/大纲/通过率，点击 >>>“CDA考试官网” 了解CDA考试详情；

数据分析

数据分析咨询请扫描二维码

上一篇成为CDA会员俱乐部志愿者你将获得！
下一篇图论在大数据分析中的作用！
CDA考试动态
CDA报考指南
热门栏目
最新资讯
更多
Copyright © 2015-present 北京国富如荷网络科技有限公司 All Rights Reserved.
京ICP备11001960号-9   京公网安备 11010802034615号   经营许可证编号：京B2-20210330
客服在线
立即咨询