玩转红黑树 (第四部分)使用java实现平衡二叉树(avl tree)(删除,查找)

玩转红黑树 (第四部分)使用java实现平衡二叉树(avl tree)(删除,查找)

java实现平衡二叉树(avl tree)(删除,查找)

查找

    /**
     * 根据val查找节点
     */
    public Node find(int val){
        Node n;
        Node child = this;

        //循环往下遍历树
        while (child != null){
            //左节点 or 右节点?
            n = child;
            child = (val >= n.val) ? n.right : n.left;

            if(n.val == val){
                return child;
            }
        }
        return null;
    }

查找很简单,循环往下一层一层查找即可

删除

看了网上很多朋友写的平衡二叉树的删除操作,感觉有点太复杂化了。举个例子,就相当于自己去把勾股定理(a2 + b2 = c2)给证明了一遍,看得让人头晕脑大~ 当我们找到规律后,会发现其实原理很简单。正如知道a和b,就能根据公式很容易求出c一样!

看图找规律

  • 入门(底层节点) 删除140节点

如上图所示,140位于最底层节点,没有属于自己的子树,这种删除操作最简单,获取到它自己的父节点(130),然后删除130的右节点。以下是代码示例

private void remove1(Node node){
        if(node.left == null && node.right == null){
            if(node.parent.left == node){
                //如果节点处于左树上,删除父节点下的左节点
                node.parent.left = null;
            }else{
                //如果处于右树上,删除父节点下的右节点
                node.parent.right = null;
            }
        }
    }
  • 进阶(存在一个子树节点) 删除110节点

如上图所示,如果被删除节点只存在一个子节点(右或者左),直接将子节点的val值赋值给当前节点,然后删除子节点。比如上图所示,将110的值变成108,然后删除原有的子节点(108)

    private void remove2(Node node){
        if(node.left!=null){
            //如果左子树存在节点,则优先使用左子节点替代被删除节点
            Node child = node.left;
            //将子节点的val赋值给当前节点,然后删除子节点
            node.val = child.val;
            remove(child);
        }else{
            //这是右树
            Node child = node.right;
            //同上
            node.val = child.val;
            remove(child);
        }
    }
  • 高级(存在2个子树节点) 删除120

查找到110节点时,获取左子节点,如果后面还存在多级,那么一直往下遍历右节点,直到最底层节点。那么,将此节点替代110即可。以下是代码示例。

    private void remove2(Node node){
        if(node.left!=null){
            //获取左子节点
            Node child = node.left;
            while (child.right!=null) {
                //如果左子节点存在右节点,循环往下获取,直到child.right=null结束 也就是最底层节点
                child = child.right;
            }
            //将子节点的val赋值给当前节点,然后删除子节点
            node.val = child.val;
            remove(child);
        }else{
            //这是右树
            Node child = node.right;
            //原理如上
            while (child.left!=null) {
                child = child.left;
            }
            //同上
            node.val = child.val;
            remove(child);
        }
    }

这就是删除节点时,存在的几种情况。多使用可视化工具模拟查看转换过程。规律自然明了于心中,寻找到规律后,在使用代码实现

完整代码如下

import com.alibaba.fastjson.JSON;

public class TreeNode {

    public static void main(String[] args) {
        Node root = new Node();

        root.insert(100);
        root.insert(90);
        root.insert(110);
        //插入此节点会发生旋转
        root.insert(130);
        root.insert(80);
        root.insert(140);
        root.insert(105);

        root.remove(130);

        System.out.println(JSON.toJSONString(root));
    }
}

class Node{

    /**
     * 值
     */
    private Integer val;
    /**
     * 平衡因子
     */
    private int balance;
    /**
     * 高度
     */
    private int height;
    /**
     * 左节点
     */
    private Node left;
    /**
     * 右节点
     */
    private Node right;
    /**
     * 父节点
     */
    private Node parent;

    public Node(int val,Node p) {
        this.val = val;
        this.parent = p;
        this.height = 1;
    }

    public Node(){
    }

    /**
     * 删除节点
     */
    public boolean remove(int val){
        //根据val查找到对应的Node节点
        Node targetNode = find(val);
        if(targetNode == null){
            //未寻找到节点
            return false;
        }
        remove(targetNode);
        return true;
    }

    private void remove(Node node){
        if(node.left == null && node.right == null){
            //如果此节点已经是最后一个
            if(node.parent == null){
                //并且本身就是根节点,则直接删除即可
                clearNode(node);
            }else{
                //处于叶子节点上
                if(node.parent.left == node){
                    //如果节点处于左树上,删除左节点
                    node.parent.left = null;
                }else{
                    //如果处于右树上,删除右节点
                    node.parent.right = null;
                }
                reloadBalance(node);
            }
        }else{
            if(node.left!=null){
                Node child = node.left;
                while (child.right!=null) {
                    child = child.right;
                }
                node.val = child.val;
                remove(child);
            }else{
                Node child = node.right;
                while (child.left!=null) {
                    child = child.left;
                }
                node.val = child.val;
                remove(child);
            }
        }
    }

    /**
     * 针对根节点的清理操作
     */
    private void clearNode(Node n){
        n.right = null;
        n.left = null;
        n.parent = null;
        n.height = 0;
        n.balance = 0;
    }


    /**
     * 根据val查找节点
     */
    public Node find(int val){
        Node n;
        Node child = this;

        //循环往下遍历树
        while (child != null){
            //左节点 or 右节点?
            n = child;
            child = (val >= n.val) ? n.right : n.left;

            if(n.val == val){
                return n;
            }
        }
        return null;
    }

    public boolean insert(Integer value){
        if(this.val == null){
            //说明这是第一次插入
            this.val = value;
            this.height = 1;
            return true;
        }

        //向下循环遍历,寻找合适的位置插入
        Node root = this;
        //用来指向每次遍历时的节点引用
        Node parent;

        while (true){
            //默认不存储已经存在的值
            if(value.equals(root.val)){
                return false;
            }

            parent = root;

            //判断是应该存在在左边还是右边
            boolean leftGo = value < root.val;
            //根据值的大小 选取节点
            root = leftGo ? root.left : root.right;

            if(root == null){
                //说明已经遍历到最后一层,可以插入数据
                if(leftGo){
                    //插入到左边
                    parent.left = new Node(value,parent);
                }else{
                    //否则插入到右边
                    parent.right = new Node(value,parent);
                }
                //重新计算负载因子,并且如果出现不平衡,则自旋保证平衡
                reloadBalance(parent);
                break;
            }
        }
        return true;
    }

    /**
     * 重新计算平衡因子 并且判断是否发生不平衡
     */
    private void reloadBalance(Node n) {
        //计算平衡因子
        reCalculateBalance(n);

        //是否失衡,如果存在失衡,进行旋转操作
        if(n.balance == -2){
            //平衡因子等于-2 说明已经倾斜 并且左倾斜 (这儿平衡因子计算方式是通过右节点高度 - 左节点高度) 为负数,说明左树高度 > 右树高度
            if(height(n.left.left) >= height(n.left.right)){
                //说明这是一颗LL型失衡树,只需要一次右旋即可恢复平衡
                rightRotate(n);
            }else{
                //说明这是一颗LR型失衡树,需要先左旋,后右旋即可恢复平衡
                n.left = leftRotate(n);      //左旋
                n = rightRotate(n);          //右旋
            }
        }else if(n.balance == 2){
            //平衡因子等于2 说明已经倾斜 并且右倾斜
            if(height(n.right.right) >= height(n.right.left)){
                //说明这是一颗RR型失衡树,只需要一次左旋即可恢复平衡
                leftRotate(n);
            }else{
                //说明这是一颗RL型失衡树,需要先右旋,后左旋
                n.right = rightRotate(n.right);      //右旋
                n = leftRotate(n);                   //左旋
            }
        }

        if(n.parent != null){
            //自下往上遍历,直到顶层节点
            reloadBalance(n.parent);
        }
    }

    /**
     * 右旋
     *                 A
     *               B   C                       A
     *             D           -------->       D   C
     *           E                           E   B
     *  失衡点为B节点
     *  return 新的父节点
     */
    private Node rightRotate(Node bNode){

        //如上图所示,B节点右旋.左变父,父变右
        Node dNode = bNode.left;
        //D节点取代B的位置,同理,D的父亲也变成B的父亲(A)
        dNode.parent = bNode.parent;
        //如果D右树存在节点,当B右旋至D的右树时,将会发生碰撞,所以,需要将D的右节点存放在B的左节点上
        bNode.left = dNode.right;
        if(bNode.left != null){
            //旋转后,此节点的父亲应该是B,所以需要改变父节点引用
            dNode.left.parent = bNode;
        }
        //继续改变节点间的引用关系,D的右节点已经变成B
        dNode.right = bNode;
        //B节点的父亲已经成为D
        bNode.parent = dNode;

        if(dNode.parent != null){
            //旋转后,D成为A的子节点,但是此时A的子节点依然为B,所以需要更新
            if(dNode.parent.left == bNode){
                //说明B节点原来的位置是在左树上,所以,将新的父节点D设置在A节点的左树上
                dNode.parent.left = dNode;
            }else{
                //将D节点设置到A树的右节点上
                dNode.parent.right = dNode;
            }
        }

        //旋转完毕后,重新计算高度和平衡因子
        reCalculateBalance(bNode,dNode);
        return dNode;
    }

    /**
     * 左旋
     *                  A
     *                B   C       ------>      A
     *                      D                B    D
     *                        E                 C    E
     *  失衡点为C节点
     *  return 新的父节点
     */
    private Node leftRotate(Node cNode){
        Node dNode = cNode.right;
        //D节点取代C的位置,同理,D的父亲也变成C的父亲(A)
        dNode.parent = cNode.parent;
        //C节点进行左旋时,位于D的左节点,如果D的左节点已经存在值了,则发生了碰撞,将当前节点放在C节点的右树
        cNode.right = dNode.left;

        if(cNode.right != null){
            //如果D的左节点存在,此时发生了旋转后,父亲已经变成了C节点,所以需要改变
            cNode.right.parent = cNode;
        }

        //继续改变节点之间的引用关系,D的右节点已经变成C
        dNode.left = cNode;
        //C节点的父节点变成D
        cNode.parent = dNode;

        //已经将当前被旋转点的各个引用关系都重新刷新完毕。
        //但是,如果原始树上的C节点不是根节点,如上图. 原始树A节点的右节点时C,旋转手A节点的右节点变成D. 所以,还需要刷新父节点的引用关系
        if(dNode.parent != null){
            if(dNode.parent.right == cNode){
                //说明原始树C节点在右树上,更新A节点右树为D
                dNode.parent.right = dNode;
            }else{
                //这说明在左树上
                dNode.parent.left = dNode;
            }
        }

        //重新计算平衡因子
        reCalculateBalance(cNode,dNode);
        return dNode;
    }

    /**
     * 计算负载因子  公式:右树高度 - 左树高度
     */
    private void reCalculateBalance(Node ... ns) {
        for (Node n : ns) {
            //计算前,重新计算节点高度
            reHeight(n);
            //右树高度减去左树高度
            n.balance = height(n.right) - height(n.left);
        }
    }

    /**
     * null节点高度默认为0,否则返回自身高度
     */
    private int height(Node n){
        return n == null ? 0 : n.height;
    }
    /**
     * 插入完毕后,重新计算节点高度  1 + 当前最高高度(左树高度和右树高度对比)
     */
    private void reHeight(Node n){
        n.height = 1 + Math.max(height(n.right),height(n.left));
    }
}

上一章(玩转红黑树 (第三部分)使用java实现平衡二叉树(插入,旋转))

下一章(玩转红黑树 (第五部分)红黑树的概念与插入

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×