java数据结构和算法——平衡二叉树之双旋转

一、平衡二叉树的单旋转（即左旋转或者右旋转）问题分析

• 某些情况下，单旋转不能完成平衡二叉树的转换。比如数列 { 10, 11, 7, 6, 8, 9 }，图解如下：

二、解决单旋转不能形成AVL树的思路分析（通过双旋转实现AVL树的思路分析图解）

1）、当符号右旋转的条件时 2）、如果它的左子树的右子树高度大于它的左子树的高度，如下图： 3）、 先对当前这个结点的左节点进行左旋转（即下图中的值为7的节点进行左旋转），如下图： 4）、基于第3）步骤的基础上，再对当前结点进行右旋转的操作即可，如下图：

三、平衡二叉树双旋转的代码示例

1、创建一个节点类 Node

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 创建一个节点类 Node
 * @author: xiaozhi
 * @create: 2020-10-13 22:04
 */
public class Node {
    public int value;//节点的值
    public Node left;//左节点
    public Node right;//右节点

    //构造方法
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    /** 
    * @Description:  返回以当前节点为根节点的树的高度
    * @Author: xz
    * @Date: 2020/10/13 22:07
    */
    public int height(){
        return  Math.max(left ==null ? 0 : left.height(),right == null ? 0 : right.height())+1;
    }
    /** 
    * @Description: 返回左子树的高度
    * @Author: xz
    * @Date: 2020/10/13 22:10
    */
    public int leftHeight(){
        if(left == null){
            return 0;
        }
        return  left.height();
    }
    /**
    * @Description: 返回右子树的高度
    * @Author: xz
    * @Date: 2020/10/13 22:11
    */
    public int rightHeight(){
        if(right ==null){
            return 0;
        }
        return right.height();
    }
    /**
    * @Description:  左旋转方法
    * @Author: xz
    * @Date: 2020/10/13 23:44
    */
    public void leftRotate() {
        //创建新的结点，以当前根结点的值
        Node newNode = new Node(value);
        //把新的结点的左子树设置成当前结点的左子树
        newNode.left = left;
        //把新的结点的右子树设置成当前结点的右子树的左子树
        newNode.right = right.left;
        //把当前结点的值替换成右子结点的值
        value = right.value;
        //把当前结点的右子树设置成当前结点右子树的右子树
        right = right.right;
        //把当前结点的左子树(左子结点)设置成新的结点
        left = newNode;
    }
    /**
    * @Description:  右旋转方法
    * @Author: xz
    * @Date: 2020/10/14 22:43
    */
    private void rightRotate() {
        //创建新的结点，以当前根结点的值
        Node newNode = new Node(value);
        //把新的结点的右子树设置成当前结点的右子树
        newNode.right = right;
        //把新的结点的左子树设置成当前结点的左子树的右子树
        newNode.left = left.right;
        //把当前结点的值替换成左子结点的值
        value = left.value;
        //把当前结点的左子树设置成当前结点左子树的左子树
        left = left.left;
        //把当前结点的右子树(右子结点)设置成新的结点
        right = newNode;
    }
    /**
     * @Description: 一、递归的形式添加结点，注意需要满足二叉排序树的要求
     * @Param:  node 传入的几点
     * @Author: xz
     * @Date: 2020/9/27 21:58
     */
    public void addNode(Node node){
        if(node == null){
            return;
        }
        if(node.value  当前结点的值
            if(this.right == null){ //如果当前结点右子结点为null
                this.right = node;
            }else{//递归的向右子树添加
                this.right.addNode(node);
            }
        }
  
        //当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
        if(rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if(right != null && right.leftHeight() > right.rightHeight()) {
                //先对右子结点进行右旋转
                right.rightRotate();
                //然后在对当前结点进行左旋转
                leftRotate(); //左旋转..
            } else {
                //直接进行左旋转即可
                leftRotate();
            }
            return ; //必须要!!!
        }

        //当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
        if(leftHeight() - rightHeight() > 1) {
            //如果它的左子树的右子树高度大于它的左子树的高度
            if(left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前结点的左结点(左子树)->左旋转
                left.leftRotate();
                //再对当前结点进行右旋转
                rightRotate();
            } else {
                //直接进行右旋转即可
                rightRotate();
            }
        }
    }

    /**
     * @Description: 二、中序遍历二叉排序树
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/9/27 22:09
     */
    public void infixOrder(){
        //左子节点不为null，向左子节点中序遍历
        if(this.left != null){
            this.left.infixOrder();
        }

        //输出当前节点
        System.out.println(this);

        //右子节点不为null，向右子节点中序遍历
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

}

2、创建平衡二叉树类（即AVL树）

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 创建平衡二叉树（即AVL树）
 * @author: xiaozhi
 * @create: 2020-10-13 22:13
 */
public class AVLTree {
    public Node root;

    public Node getRoot() {
        return root;
    }

    /**
     * @Description:  一、添加二叉排序树节点方法
     * @Param:  node 传入的节点
     * @Author: xz
     * @Date: 2020/9/27 22:18
     */
    public void addBstNode(Node node){
        if(root == null){//如果root为空则直接让root指向node
            root = node;
        }else{
            root.addNode(node);
        }
    }
    /**
     * @Description:  二、中序遍历二叉排序树方法
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/9/27 22:25
     */
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空，不能遍历");
        }
    }

}

3、定义一个平衡二叉树测试类

package com.rf.springboot01.dataStructure.avlTree;

/**
 * @description: 平衡二叉树测试类
 * @author: xiaozhi
 * @create: 2020-10-13 22:15
 */
public class AVLTreeTest {
    public static void main(String[] args) {
        //定义一个数组，测试双旋转数组
        int[] arr={10,11,7,6,8,9};
        //创建一个AVL树对象
        AVLTree avlTree = new AVLTree();
        //添加节点
        for(int i=0;i