unity 删除子节点_递归之阿拉丁神手写红黑树删除篇

作者：花生_TL007 | 2024-03-29 01:44:28

踩

unity 删除grid所有子节点

红黑树删除节点相对新增插入节点要复杂一些；在删除红黑树的某一个节点前，红黑树原本是平衡的；当要删除掉一个节点红黑树的结构和平衡性都有可能会被打破，需要删除掉节点之后从新进行平衡；删除一个节点红黑树会出现哪些情况呢；

可以从是否影响平衡或是否为叶子节点两个角度区分：

1，删除不影响平衡的情况，和影响平衡的情况；

2，删除的是叶子节点，或不是叶子节点，不是叶子节点时有几个子节点的情况；

下面优先考虑是否为叶子节点，再判断是否影响平衡，来分析删除节点的具体场景；

A:删除可以先简单地分为三种情况来考虑替换问题：没有子节点，有一个子节点，有两个子节点。

没有：那直接删掉

有一个：如果这个左子节点，就要找到比被删除节点值小的最大的值；如果这个节点是右子节点，就要找到比被删除节点值大的最小的值。然后将找到的当前节点当作被删除节点，进入A过程的循环递归。

有两个：可以选择找比被删除节点值小的最大的值，也可以找比被删除节点值大的最小的值。反正选择一种固定的方案，然后将找到的当前节点当作被删除节点，进入A过程的循环递归。

A过程的作用就是找到最终被正在删除的节点，然后从这里开始平衡工作。

因为A是递归的，经过A过程处理后最终找到的节点一定是叶子节点，然后就可以在最小范围内开始平衡处理。

经过以上递归过程之后，发现要删除的节点不管是不是叶子节点，经过转换之后最终要删除的都是叶子节点；这样以来就可以忽略维度2的考虑了，而对于维度1就变得很简单：如果叶子节点为红色那么删除之后不影响平衡，而如果是黑色则会影响平衡；尽管叶子节点是黑色被删除影响平衡，但当删除的节点是叶子节点是处理平衡的问题有变得更简单了；因为删除的是叶子节点，所以当要处理平衡问题时，此时的平衡处理范围是最小，可以像新增时一样，在当前范围内无法平衡时抛给“阿拉丁神”处理；

所以A过程就是要找到这个最终要被真正删除的节点，并在此过程中完成替换；

A过程代码：

删除方法入口；

/**     * 删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！     * 删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末。     *

* 删除值等于k的节点 * 1，找到节点dt * 2，dt没有子节点，直接删除 * 3，dt存在单个子节点，找替换节点(为子节点)(相当于被删除的节点)，从走234，最终都可以转换为2 * 4，dt存在两个子节点，找替换节点(统一用后继节点)(相当于被删除的节点)，从走234，最终都可以转换为2 * 5，重新平衡 * * @param k * @param root * @return */


    public TNode deletek(int k, TNode root) {
   
        // 找到要被删除的目标节点
        TNode dt = getkNode(k, root);
        // 找到最终被替换的叶子节点，在过程中完成节点的替换
        TNode deleteTarget = deleteTarget(dt, root);
        // 平衡
//        balanceDeleteTarget(deleteTarget, root);
//        System.out.println("=======================================");
        balanceDeleteTargetInLoop(deleteTarget, root);
        // 删除最终的替换节点
        deleteLinkToParent(deleteTarget);
        return getRoot(root);
    }
/**
     * 找到k所在的节点
     *
     * @param k
     * @param root
     * @return 空 表示没有找到
     */
    public TNode getkNode(int k, TNode root) {

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/332940