# 快乐树0x01：AVL树的java实现

***

> 写几个码量比较大的数据结构试试看，不知道过几天还记不记的得

## 1. AVL树

* 树的高度：根节点到叶子节点的最长距离
* AVL树是一种平衡二叉树，其任何一个节点的两个子树的高度最大差为1

## 2. 节点

### 节点定义

```java
public class AVLTree<T extends Comparable<T>>{
//用java自带的泛型，实现Comparable接口做比较
    
    Node<T> root;//跟节点
    
    class Node<T extends Comparable<T>>{
        T value;
        Node<T> left;
        Node<T> right;
        int height; //节点的高度
        
        public Node(T key, Node<T> left, Node<T> right){
            this.value = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }
}
```

相比普通的二叉树，会记录多一个节点的高度。

### 取height函数

```java
int height(Node<T> node){
    //获取树的高度
    if(node!=null)
        return node.height;
    return 0;
}
```

## 3. 旋转

旋转操作是AVL树平衡的核心。旋转操作其实就是一种改变根节点，从而使得树平衡的方法。

如果在AVL树中进行插入或删除操作，可能会导致平衡被打破。

可以分为4种情况：LL、LR、RL和RR。

四种情况分别对应如图：

![img](https://images0.cnblogs.com/i/497634/201403/281624280475098.jpg)

### LL的旋转

LL情况下，可进行一次单旋转：

![img](https://images0.cnblogs.com/i/497634/201403/281626153129361.jpg)

LL对应的旋转是左单旋转，把k1作为根节点，k2作为k1的又子树，同时将k1的右子树作为k2的左子树。

当然，旋转后要重新计算节点的高度。由于高度是自下而上的，只用取自己的子树最高高度+1即可。

代码中，以k1为最左节点，参数为最高节点（因为不能向上查，只能向下）

```java
private Node<T> LLRotation(Node<T> k2){
        //执行左单旋转，返回新的（子树）根节点。注意k1永远是原左节点。
        Node<T> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = Math.max(height(k2.left),height(k2.right))+1;
        //注意这里k1的高度是新树，所以用k2.height就可以了，不用重复求
        k1.height = Math.max(height(k1.left),k2.height)+1;
        //重新计算节点的高度
        return k1;
    }
```

### RR的旋转

RR对应的是右单旋转，与LL的左单旋转对称。

![img](https://images0.cnblogs.com/i/497634/201403/281626410316969.jpg)

```java
private Node<T> RRRotation(Node<T> k1){
    //执行右单旋转，返回新的（子树）根节点。注意k1永远是原左节点。
    Node<T> k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;

    k1.height = Math.max(height(k1.left),height(k1.right))+1;
    k2.height = Math.max(height(k2.left),k1.height)+1;

    return k2;
}
```

要注意的是k1永远指原左边的节点，k2是右边的节点。

### LR的旋转

LR的情况通过一次旋转不能完全解决，需要两次单旋转才能恢复平衡。

![img](https://images0.cnblogs.com/i/497634/201403/281627088127150.jpg)

对LR的双旋转其实就是 **围绕k1**进行一次右单旋转和 **围绕k3**进行一次左单旋转。

```java
private Node<T> LRRotation(Node<T> k3){
    k3.left = RRRotation(k3.left); //围绕k1RR旋转
    return LLRotation(k3); //围绕k3LL旋转
}
```

### RL的旋转

RL的情况和LR是对称的。

![img](https://images0.cnblogs.com/i/497634/201403/281628118447060.jpg)

```java
private Node<T> RLRotation(Node<T> k1){
    k1.right = LLRotation(k1.right); //k3在第二层
    return RRRotation(k1); //k1在最上层
}
```

## 4. 插入

根据二叉查找树性质插入节点。递归，边界条件是到达叶子的子树（当前节点==null）

由于插入操作是不稳定的，可能改变平衡状态，需要在每层递归（但根据AVL的性质，不会超过2层不平衡）检测平衡状态，如果不平衡则进行相应的旋转。

因为进行了旋转和插入，所以递归需要在返回时重新统计高度。

```java
private Node<T> insert(Node<T> tree,T value){
    //tree：插入的位置 value：插入的值
    if(tree == null){ //递归，边界条件，一定要写
        tree = new Node<T>(value,null,null);
    }else{
        int cmp = value.compareTo(root.value);
        if(cmp<0){ //<，应该在左子树插入
            tree.left = insert(tree.left,value);
            //插入后可能导致不平衡，需要判断状态并旋转恢复
            if(height(tree.left)-height(tree.right)==2){
                //因为是在左子树插入的，就有LL和RL两种非平衡情况
                if(value.compareTo(tree.left.value)<0) //LL
                    tree = LLRotation(tree);
                else  //LR
                    tree = LRRotation(tree);
            }
        }else if(cmp>0){ //>，在右子树插入
            tree.right = insert(tree.right,value);
            if(height(tree.right)-height(tree.left)==2){
                if(value.compareTo(tree.right.value)>0)
                    tree = RRRotation(tree);
                else
                    tree = RLRotation(tree);
            }
        }else{ //cmp == 0
            System.out.println("不允许插入相同的节点！");
        }
    }
    //经过了旋转，要重新计算节点的高度
    tree.height = Math.max(height(tree.left),height(tree.right))+1;
    return tree;
}
```

## 5. 删除

删除相比插入更麻烦，因为删除要考虑其左右子树。简单的做法是另写两个函数（比较好写，就不写出来了）分别查找子树的最大和最小值，在左树高度更大时将左树最大值与要被删的节点互换，然后再删；在右树高度更大时将右树最小值与要被删的节点互换，直到要被删除节点的位置没有任何子树，然后再删除。这样可以保住左右子树的数据仍然符合规则的同时方便地删除节点。

```java
private Node<T> remove(Node<T> tree, Node<T> target){
    // tree: 当前节点 target：待删除节点
    if(tree==null||target==null) return null;
    //递归，边界条件一定要写
    int cmp = target.value.compareTo(tree.value);
    // 沿树查找，老套路
    if(cmp<0){
        tree.left = remove(tree.left, target);
        if(height(tree.right)-height(tree.left)==2){
            Node<T> l =tree.left;
            if(height(l.right)>height(l.left))
                tree = LRRotation(tree);
            else
                tree = LLRotation(tree);
        }
    }else if(cmp>0) {
        tree.right = remove(tree.right, target);
        if(height(tree.left)-height(tree.right)==2){
            Node<T> l = tree.left;
            if(height(l.right)>height(l.left))
                tree = LRRotation(tree);
            else
                tree = LLRotation(tree);
        }
    }else{ //tree就是要删除的节点
        if(tree.left!=null && tree.right!=null){
            //要删除的节点左右都非空
            if(height(tree.left)>height(tree.right)){
                //左子树比右子树高
                Node<T> max = findMax(tree.left);
                //这个findMax函数用来找出子树中的最大节点
                tree.value = max.value;
                tree.left = remove(tree.left,max);
                //这里的做法是把要被删的节点的左子树中的最大节点和要被删节点交换
                //然后在那个位置再删掉要被删节点，那个位置肯定没有子树，直接删掉
                //这样删除很方便，也不影响左子树都比右子树小的性质
            }else{
                //左子树不比右子树高
                Node<T> min = findMin(tree.right);
                //这个findMin函数用来找子树的最小节点
                tree.value = min.value;
                tree.right = remove(tree.right,min);
                //找出右子树的最小节点和被删节点互换再删除，和上面一样
            }
        }else{ //被删节点已经没有左右子树了，直接删
            Node<T> tmp = tree;
            tree = (tree.left!=null)?tree.left:tree.right;
            tmp = null;
        }
    }
    return tree;
}
```

完整的AVL树要能维护一组数据，肯定还要提供相应的遍历/查找等等操作，但这些都比较好写，不单独列出。

> 这玩意是真的难写，这个未完全版本都要150行，考场要写出来真不容易，也许有其他替代方案？