AVL树的Java实现

AVL树

   平衡二叉树这个是建立在排序二叉树的基础上的，加了一个条件就是每个结点的左右子树结点的高度不能超过2（即要小于等于1）

其余的代码实现情况和排序树一样

但add方法里面在添加完结点后需要平衡

add方法首先分四种情况，LL，RR，LR，RL

第一个L/R是指：加在根节点的左边/右边

第二个L/R是指：导致不平衡的叶子节点的父节点是左节点/右节点（例如：3是左，6是右）

LL： RR：

LR： RL：

LR/RL需要通过先对左子树/右子树进行左/右旋转转成LL/RR的情况，再对LL/RR进行右旋转/左旋转

代码实现：

左旋转：

    总共分为6步：1）先创建一个和根节点相同的新节点

                  2）再将新节点的左节点设为左子树

                  3）将新节点的右节点设为右子树的左节点

                  4）将根节点的值设为右子树的值

                  5）将根节点的右节点设为右子树的右子树

                  6）将根节点的左子树设为新的节点

右旋转：

    情况和左旋转类似：

            也分为6步：

注意：在旋转前要先判断是LL还是LR（RR还是RL），

通过其根节点左右子树的高度来判断，如果是L，其根节点的左子树的左子树的高度大于根节点的左子树的右子树的高度，就是LL，小于就是LR

代码如下：

public class AVLTreeDemo {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int [] arr={10,11,7,6,8,9};
        for (int i = 0; i node.value){
            if (this.left==null){//如果左节点为空，就直接加上就行
                this.left=node;
            }else{//如果左结点不为空，递归
                this.left.add(node);
            }
        }else {
            if (this.right==null){
                this.right=node;
            }else {
                this.right.add(node);
            }
        }
        //在添加完之后，可以判断是否添加的不平衡，是否需要旋转
        if (rightheight()-leftheight()>1){
            //当添加的结点的根结点的右边
            //则需要判断是RL还是RR
            //通过根结点右子树的左右子树的高度来判断
            if (right!=null&&right.leftheight()>right.rightheight()){//RL
                //先对右结点进行右旋转，将其变成RR的情况
                right.rightRotate();
                //再对根节点进行左旋转
            }
            leftRotate();
//            return;//!!!这个一定要写
        }
        if (leftheight()-rightheight()>1){
            //当添加的结点在根节点的左边
            //则需要判断是LR还是LL
            //通过左子树的左右两边的高度来判断
            if (left != null && left.rightheight() > left.leftheight()){//LR
                //先对左子树进行左旋转将其变成LL的情况,再右旋转
                left.leftRotate();
            }
            //LL情况就只要对其进行右旋转就行
            rightRotate();
        }

    }
    //中序遍历
    public void infixOrder(){
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    //查找结点
    public Node search(int value){
        if (this.value==value){
            return this;
        }else if (this.left!=null&&this.value>value){
            return this.left.search(value);
        }else if (this.right!=null&&this.value= this.value && this.right != null) {
                return this.right.searchParent(value); //向右子树递归查找
            } else {
                return null; // 没有找到父结点
            }
        }
    }
    //查找节点的高度
    public int height(){
        return Math.max(left == null ? 0 : left.height(),
                        right == null ? 0 : right.height())+1;
    }
    //查找左子树结点的高度
    public int leftheight(){
        if (left==null){
            return 0;
        }
        return left.height();
    }
    //查找右子树结点的高度
    public int rightheight(){
        if (right==null){
            return 0;
        }
        return right.height();
    }
    //左旋转
    public void leftRotate(){
        //1）首先创建新的根结点
        Node node = new Node(value);
        //2）将新结点的左结点设为左子树
        node.left=left;
        //3）将新结点的右结点设为右子树的左子树
        node.right=right.left;
        //4）将结点的值改为右结点的值
        value=right.value;
        //5) 将右子树设为右子树的右子树
        right=right.right;
        //6) 将新结点设为左子树
        left=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;
    }

}