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

上节我们学习了AVL树的左旋转操作,当然有左旋转肯定会有右旋转操作,关于AVL树的其他就不多说了,本节我们就直蹦主题

案例分析

假设我有一组数列{10,12,8,9,7,6},同样我们需要创建出对应的AVL数,首先我们来看该数列对应的二叉排序树的样子,如下图所示:

二叉排序树.png

上述是我们利用二叉排序树特点创建的二叉排序树,我们可以发现上述这棵树左右子树的高度超过了1,不满足AVL树,所以我们需要对上述这棵二叉排序树进行调整,由于上述树的左子树整体高度是大于右子树,因此这里采用右旋转的方式来降低左子树的高度以此来达到左右子树的平衡,我们先来看下思路分析:

• 1.创建一个新节点,以当前根节点的值
• 2.把新节点的右子节点设置为当前节点的右子节点
• 3.把新节点的左子节点设置为当前节点左子节点的右子节点
• 4.把当前节点的值用左子节点的值来替换
• 5.把当前节点的左子节点设置为当前节点左子节点的左子节点
• 6.把当前节点的右子节点设置为新节点

同样也是6步,我们通过上述的步骤可以完成对上述二叉排序树的调整为对应的AVL树,如下图所示:

右旋转对应的AVL树.png

上图就是经过调整之后的符合平衡二叉树的AVL树,接着我们利用代码来实现此过程:

直接在Node类新增右旋转方法

//右旋转的方法
public void rightRotate(){
    //1.创建一个新节点,以当前根节点的值
    Node newNode = new Node(value);
    //2.把新节点的右子节点设置为当前节点的右子节点
    newNode.right = right;
    //3.把新节点的左子节点设置为当前节点左子节点的右子节点
    newNode.left = left.right;
    //4.把当前节点的值用左子节点的值来替换
    value = left.value;
    //5.把当前节点的左子节点设置为当前节点左子节点的左子节点
    left = left.left;
    //6.把当前节点的右子节点设置为新节点
    right = newNode;
}

接着在我们的Node类中的add方法里新增判断,代码如下:

//当添加完一个节点后,如果(左子树的高度-右子树的高度) >1 ,我们需要右旋转
    if (getLeftHeight() - getRightHeight() >1){
          rightRotate();
   }

我们每添加一个节点去判断左右子树的高度,接着我们来看看测试代码:

 int [] arr = {10,12,8,9,7,6};
    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);
}

测试结果如下图所示

AVL树有旋转测试结果图.png

通过我们的调整,将一棵不平衡的二叉排序树调整为AVL树,那么关于AVL树的右旋转调整学习就到这里了,完整代码前前往git地址查看.