树结构入门教程-平衡二叉树双旋转

我们在前面学习了平衡二叉树的左旋转和右旋转,在有些特殊的需求中,往往我们只通过左旋转或者是右旋转是无法完成对二叉排序树进行调整为一棵平衡二叉树的,就像下面这个数列一样时无法通过单一的旋转完成如:{10,11,7,6,8,9}

那么我们试一下将上述数列只通过单一旋转看是否能调整为一棵AVL树,如下图:

双旋转1.png

上图中左边是数列{10,11,7,6,8,9}对应的二叉排序树,我们发现 左子树高度大于右子树的,此时我们进行右旋转,那么上图中右边就是右旋转之后的结果,发现此时右子树高度-左子树高度是大于1的,按照我们之前的做法是需要进行左旋转的,在上述的场景中是不行的,我们先来分析下这个问题:

一开始我们就发现上述二叉排序树的左子树的高度是大于右子树高度的,于是我们立即对它进行右旋转,假如我们这样操作了:

• 当我们在右旋转的时候:
• 1.发现左子树的右子树高度大于左子树的左子树高度(如上图一样)
• 1.1.我们先对当前左子树的右子树进行左旋转(如下图所示:)

左子树的右子树进行左旋转.png

• 1.2.现在我们对上图右边的二叉排序树进行右旋转即可(如下图所示)

AVL树.png

经过我们左旋转和右旋转共同的操作,将上述二叉树排序树调整为一棵AVL树,接着我们通过代码来实现上述操作

代码实现

这里直接写核心代码

//节点的添加方法
//采用递归的方式来添加,需要满足二叉排序树的要求
public void add(Node node){
    if (node == null){
        return;
    }
    //判断当前传入节点的值和当前子树的根节点的值的关系
    if (node.value < this.value){
        //如果当前节点的左子节点为null,我们直接添加
        if (this.left == null){
            this.left = node;
        }else { //递归去添加
            this.left.add(node);
        }
    }else { //表示 node.value > this.value
        if (this.right ==null){
            this.right = node;
        }else {
            this.right.add(node);
        }
    }
    //当添加完一个节点后,如果(右子树的高度-左子树的高度) >1 ,我们需要左旋转
    if (getRightHeight() - getLeftHeight() >1){
            leftRotate();
        //如果当前节点的右子节点的左子节点高度 大于当前节点右子节点的右子节点高度
        if (right !=null && right.getLeftHeight() > right.getRightHeight()){
            //首先对当前节点的右子节点进行右旋转
            right.rightRotate();
            //接着我们对当前节点进行左旋转
            leftRotate();
        }else {
            leftRotate();
        }
        return;
    }
    //当添加完一个节点后,如果(左子树的高度-右子树的高度) >1 ,我们需要右旋转
    if (getLeftHeight() - getRightHeight() >1){
        //如果当前节点的左子节点的右子节点高度大于当前节点的左子节点的高度(假如: 根节点的左子树的右子节点的高度大于左子树的左子节点的高度)
        if (left !=null && left.getRightHeight() > left.getLeftHeight()){
            //首先对当前节点的左子节点进行左旋转
            left.leftRotate();
            //接着是对当前节点进行右旋转(根节点)
            rightRotate();
        }else {
            rightRotate();
        }
    }
}

双旋转核心的代码是#add方法的后面的两个if判断,注释很详细这里我们直接测试

   int [] arr = {10,11,7,6,8,9};
    AvlTree avlTree = new AvlTree();
    //创建二叉排序树
    for (int i = 0; i <arr.length ; i++) {
        Node node = new Node(arr[i]);
        avlTree.add(node);
    }
    //遍历
    System.out.println("中序遍历结果为:");
    avlTree.midOrder();
    //=======================================
    System.out.println("当前树的高度="+avlTree.getRoot().getHeight());
    System.out.println("左子树的高度="+avlTree.getRoot().getLeftHeight());
    System.out.println("右子树的高度="+avlTree.getRoot().getRightHeight());
    System.out.println("AVL树的根节点为="+avlTree.getRoot());
    System.out.println("AVL树的根节点的左子节点为="+avlTree.getRoot().left.left);
    System.out.println("AVL树的根节点的右子节点为="+avlTree.getRoot().right);
}

测试结果如下图所示:

双旋转测试结果图.png

那么关于AVL树的双旋转的学习就到这里了,完整代码已上传git