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

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

使用java实现平衡二叉树(avl tree)的插入与自旋

上一章(图解平衡二叉树)已经理解了平衡二叉树的旋转规则,那么如何使用Java编写一个平衡二叉树呢?这章就来手写一个java版本平衡二叉树

Node.java

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(){
    }
}

这儿的Node类设计为双向链表的模式,每个子节点包含自己的父节点引用地址

计算节点高度

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

计算平衡因子

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

右旋

    /**
     * 右旋
     *                 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;
    }

右旋的原理很简单,左节点变父节点,父节点变右节点。然后将位置变动的2个节点中的parent,left,right节点的引用改变即可

左旋

    /**
     * 左旋
     *                  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 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);
        }
    }

插入

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;
    }

插入的过程,其实就是一直往下查找合适的位置插入。这儿使用while(true)循环的方式。当root==null,则说明已经循环到最后一层。同时判断应该插入到左树还是右树。以上代码的注释已经都写的很明白了~

写在最后

代码可能看得有点头晕,建议使用可视化工具动态查看节点的变换过程,然后结合代码理解

上一章(玩转红黑树 (第二部分)平衡二叉树)

下一章(玩转红黑树 (第四部分)java实现平衡二叉树(查找,删除))

评论

Your browser is out-of-date!

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

×