AVL树的思想及实现

定义

AVL树是高度平衡的二叉搜索树，按照二叉搜索树（Binary Search Tree）的性质，AVL首先要满足：

若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

AVL树的性质：

1. 左子树和右子树的高度之差的绝对值不超过1
2. 树中的每个左子树和右子树都是AVL树
3. 每个节点都有一个平衡因子(balance factor–bf),任一节点的平衡因子是-1,0,1之一，(每个节点的平衡因子bf 等于右子树的高度减去左子树的高度 )

下图就是一棵AVL Tree：

如下图，这棵树是非AVL树，因为其平衡因子是不满足要求的。

初始化AVL Tree

AVL树是高度平衡的二分搜索树，所以其初始化的时候和二分搜索树是一样的，只不过因为要计算平衡因子，所以需要记录每个节点的高度。

public class AVLTree<K extends Comparable<K>, V> {

    /**
     * 节点私有类初始化
     */
    private class Node{
        public K key;
        public V value;
        public int height;

        public Node leftNode;
        public Node rightNode;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            height = 1;
            leftNode = null;
            rightNode = null;
        }
    }

    private int size;    //树空间
    private Node root;   //根节点

    /**
     * 构造函数
     */
    public AVLTree(){
        root = null;
        size = 0;
    }

计算高度和平衡因子

节点在初始化的时候的高度为1，然后树的初始化过程中会维护树的高度，所以获取节点的高度的话直接返回该节点的高度值就可以了。

平衡因子其实就是左子树的高度减去右子树的高度。

具体的实现如下：

/**
    * 获取某一个节点的高度值
    * @param node
    * @return
    */
   public int getHeight(Node node){
       if (node == null){
           return 0;
       }
       return node.height;
   }

   /**
    * 获取某个节点的平衡因子
    * 平衡因子其实就是左孩子的高度减去右孩子的高度,有正负
    * @param node
    * @return
    */
   public int balanceFactor(Node node){
       if (node == null){
           return 0;
       }
       return getHeight(node.leftNode) - getHeight(node.rightNode);
   }

验证二分搜索树的性质和平衡性

AVL树是一颗高度平衡的二分搜索树，所以要满足二分搜索树的性质，也要满足平衡性。

验证是否是二分搜索树的话，二分搜索树的中序遍历之后的元素是满足顺序从大到小的顺序性的，所以可以用该性质来测试是否是二分搜索树。

平衡性就是判断平衡因子的绝对值是否大于0就可以了。

具体如下：

/**
     * 中序遍历
     * @param node 以node为根的子树
     * @param keys  keys
     */
    private void inOrder(Node node, ArrayList<K> keys){
        if (node == null){
            return;
        }
        inOrder(node.leftNode, keys);         //执行到node.leftNode == null的时候就跳出这一次的inOrder,执行下面的语句
        keys.add(node.key);
        inOrder(node.rightNode,keys);
    }

    /**
     * 是否是一颗平衡树
     * @return
     */
    public boolean isBalanced(){
        return isBalanced(root);
    }

    /**
     * 判断以node为根节点的树是否平衡
     * 其实就是看树中每个节点的平衡因子的绝对值是否大于1
     * @param node node
     * @return
     */
    private boolean isBalanced(Node node){
        if (node == null){
            return true;
        }
        if (balanceFactor(node) > 1 || balanceFactor(node) < -1){
            return false;
        }
        return isBalanced(node.leftNode) && isBalanced(node.rightNode);
    }

维护平衡

有的时候给树中添加或者删除元素的时候可能会破坏树的平衡，那怎么去维护书的平衡呢？

右旋转

当插入的元素位于不平衡节点的左侧的左侧的时候：

这个时候需要对8这个节点进行右旋转。

右旋转的具体的实现完成如下：

其实过程很简单就是将y的做节点换成x的有节点，然后x的右孩子指向y.

具体的过程如下：

/**
     * 对以node为根节点的树进行右旋转
     // 对节点y进行向右旋转操作，返回旋转后新的根节点x
     //        y                              x
     //       / \                           /   \
     //      x   T4     向右旋转 (y)        z     y
     //     / \       - - - - - - - ->    / \   / \
     //    z   T3                       T1  T2 T3 T4
     //   / \
     // T1   T2
     * @param node node
     * @return 旋转后新的子树的根节点
     */
    public Node rightRoate(Node node){
        Node x = node.leftNode;
        Node T3 = x.rightNode;
        x.rightNode = node;
        node.leftNode = T3;

        //旋转完成之后更新树的高度,其实只有x和y的高度发生变化
        x.height = Math.max(getHeight(x.leftNode), getHeight(x.rightNode)) + 1;
        node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;

        return x;
    }

左旋转

当插入的元素位于不平衡节点的右侧的右侧的时候，需要进行左旋转，其实和右旋转是一个对称的过程，不在赘述，具体如下：

/**
     * 对以node为根节点的树进行左旋转
     // 对节点y进行向左旋转操作，返回旋转后新的根节点x
     //    y                             x
     //  /  \                          /   \
     // T1   x      向左旋转 (y)       y     z
     //     / \   - - - - - - - ->   / \   / \
     //   T2  z                     T1 T2 T3 T4
     //      / \
     //     T3 T4
     * @param node node
     * @return 返回旋转后新的子树的根
     */
    public Node leftRoate(Node node){
        Node x = node.rightNode;
        Node T2 = x.leftNode;
        x.leftNode = node;
        node.rightNode = T2;
        //旋转完成之后更新树的高度，其实只有x和y的高度发生变化
        x.height = Math.max(getHeight(x.leftNode), getHeight(x.rightNode)) + 1;
        node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;

        return x;
    }

先左旋转后右旋转

当插入的元素位于不平衡元素的左侧的右侧的时候需要先左旋转然后进行右旋转，为什么是这样的？

如下图的情况：

对X进行了左旋转之后变成了上面介绍的需要进行右旋转的情况，这时候只需要在进行右旋转就可以维持平衡了。

先右旋转后左旋转

当插入的元素位于不平衡元素的右侧的左侧的时候需要先左旋转然后进行右旋转，为什么是这样的？

如下图的情况：

对X进行了右旋转之后变成了上面介绍的需要进行左旋转的情况，这时候只需要在进行左旋转就可以维持平衡了。

插入元素

其实插入元素的过程是和二分搜索树是一样的，只不过AVL树多了一些操作，插入元素之后需要更新节点的高度，需要判断是否平衡，不平衡的话属于那种不平衡的情况需要进行什么操作来维护平衡？其实就是逻辑上的判断。

具体的实现如下

/**
     * 插入元素
     * @param key
     * @param value
     */
    public void add(K key, V value){
        root = add(root, key, value);
    }

    /**
     * 向以node为根节点的树上插入
     * @param node node
     * @param key key
     * @param value value
     * @return
     */
    private Node add(Node node, K key, V value){
        if (node == null){
            node = new Node(key,value);
            size ++;
            return node;
        }

        if (node.key.compareTo(key) > 0){
            node.leftNode = add(node.leftNode, key, value);
        }else if (node.key.compareTo(key) < 0){
            node.rightNode = add(node.rightNode, key, value);
        }else{
            node.value = value;
        }

        //更新树的高度
        node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;

        //LL
        if (balanceFactor(node) >  1 && (balanceFactor(node.leftNode) > 0)){
            node = rightRoate(node);
        }
        //RR
        if (balanceFactor(node) < -1 && (balanceFactor(node.rightNode ) > 0)){
            node = leftRoate(node);
        }

        //LR
        //        y      -                 y                                x
        //       / \                     /  \                             /   \
        //      x   T4    向左旋转(x)    z    T4        向右旋转 (y)        z     y
        //     / \        - - - - - >  / \           - - - - - - - ->    / \   / \
        //    z   T3                  x  T3                             T1  T2 T3 T4
        //       / \                 /  \
        //     T1   T2              T1  T2
        if (balanceFactor(node) > 1 && (balanceFactor(node.leftNode) < 0)){
            node.leftNode = leftRoate(node.leftNode);
            node = rightRoate(node);
        }

        //RL
        //      y      -                 y                                    z
        //     / \                      /  \                                /   \
        //    T1  x         向右旋转(x)  T1  z             向左旋转 (y)       y    x
        //       / \        - - - - - >    / \           - - - - - - - ->  / \   / \
        //      z   T4                    T2  x                           T1  T2 T3 T4
        //     / \                          /  \
        //   T2   T3                       T3  T4
        if (balanceFactor(node) < -1 && (balanceFactor(node.rightNode) > 0)){
            node.rightNode = rightRoate(node.rightNode);
            node = leftRoate(node);
        }

        return node;
    }

删除元素

其实删除元素的过程是和二分搜索树是一样的，删除叶子节点的话直接删除皆可以了，然后删除节点话需要找到该叶子节点的右子树中的最小值来重新成为该树的根节点，还有AVL树还多了一些操作，删除元素之后需要更新节点的高度，需要判断是否平衡，不平衡的话属于那种不平衡的情况需要进行什么操作来维护平衡？其实也还是逻辑上的判断。

具体实现如下：

/**
     * 删除某个节点对应的元素
     * @param key
     * @return
     */
    public V remove(K key){
        Node node = getNode(root,key);
        if (node == null){
            throw  new IllegalArgumentException("Error");
        }
        root = remove(root, key);
        return node.value;
    }

    /**
     * 返回树中最小的元素的节点
     * @param node
     * @return
     */
    public Node minimum(Node node){
        if (node == null){
            return null;
        }
        if (node.leftNode == null){
            return node;
        }
        return minimum(node.leftNode);
    }

    /**
     * 删除node为节点的树中key的元素
     * @param node
     * @param key
     * @return
     */
    private Node remove(Node node, K key){

        if (node == null){
            return null;
        }
        Node retNode;

        if (node.key.compareTo(key) > 0){
            node.leftNode = remove(node.leftNode, key);
            retNode = node;
        }else if (node.key.compareTo(key) < 0){
            node.rightNode = remove(node.rightNode, key);
            retNode = node;
        }else {

            //左子树为空
            if (node.leftNode == null){
                Node right = node.rightNode;
                node.rightNode = null;
                retNode = right;
                size--;
            }
            //右子树为空
            else if (node.rightNode == null){
                Node left = node.leftNode;
                node.leftNode = null;
                retNode = left;
                size --;
            }
            //左右子树均不为空的时候
            else {
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node successor = minimum(node.rightNode);
                successor.rightNode = remove(node.rightNode, successor.key);
                successor.leftNode = node.leftNode;

                node.leftNode = node.rightNode = null;
                 retNode = successor;
            }

            if (retNode == null){
                return null;
            }
            retNode.height = Math.max(getHeight(retNode.rightNode), getHeight(retNode.leftNode));

            //LL
            if (balanceFactor(retNode) >  1 && (balanceFactor(retNode.leftNode) > 0)){
                retNode = rightRoate(retNode);
            }
            //RR
            if (balanceFactor(retNode) < -1 && (balanceFactor(retNode.rightNode ) > 0)){
                retNode = leftRoate(retNode);
            }
            //LR
            if (balanceFactor(retNode) > 1 && (balanceFactor(retNode.leftNode) < 0)){
                retNode.leftNode = leftRoate(retNode.leftNode);
                retNode = rightRoate(retNode);
            }
            //RL
            if (balanceFactor(node) < -1 && (balanceFactor(node.rightNode) > 0)){
                retNode.rightNode = rightRoate(retNode.rightNode);
                retNode = leftRoate(retNode);
            }
        }
        return retNode;
    }

完整代码

package AVLTree;

import java.util.ArrayList;

/**
 * @author WilsonSong
 * @date 2018/6/20
 */
public class AVLTree<K extends Comparable<K>, V> {

    /**
     * 节点私有类初始化
     */
    private class Node{
        public K key;
        public V value;
        public int height;

        public Node leftNode;
        public Node rightNode;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            height = 1;
            leftNode = null;
            rightNode = null;
        }
    }

    private int size;    //树空间
    private Node root;   //根节点

    /**
     * 构造函数
     */
    public AVLTree(){
        root = null;
        size = 0;
    }

    /**
     * size
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 树是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 是否是二分搜索树
     * 其实就是根据二分搜索树的性质中序遍历后是从小到大顺序排序，不满足该条件即不是二分搜索树
     * @return
     */
    public boolean isBST(){
        ArrayList<K> keys = new ArrayList();
        inOrder(root, keys);
        for ( int i = 1; i < keys.size(); i++ ){
            if (keys.get(i-1).compareTo(keys.get(i)) > 0){
                return false;
            }
        }
        return true;
    }

    /**
     * 中序遍历
     * @param node 以node为根的子树
     * @param keys  keys
     */
    private void inOrder(Node node, ArrayList<K> keys){
        if (node == null){
            return;
        }
        inOrder(node.leftNode, keys);         //执行到node.leftNode == null的时候就跳出这一次的inOrder,执行下面的语句
        keys.add(node.key);
        inOrder(node.rightNode,keys);
    }

    /**
     * 是否是一颗平衡树
     * @return
     */
    public boolean isBalanced(){
        return isBalanced(root);
    }

    /**
     * 判断以node为根节点的树是否平衡
     * 其实就是看树中每个节点的平衡因子的绝对值是否大于1
     * @param node node
     * @return
     */
    private boolean isBalanced(Node node){
        if (node == null){
            return true;
        }
        if (balanceFactor(node) > 1 || balanceFactor(node) < -1){
            return false;
        }
        return isBalanced(node.leftNode) && isBalanced(node.rightNode);
    }

    /**
     * 获取某一个节点的高度值
     * @param node
     * @return
     */
    public int getHeight(Node node){
        if (node == null){
            return 0;
        }
        return node.height;
    }

    /**
     * 获取某个节点的平衡因子
     * 平衡因子其实就是左孩子的高度减去右孩子的高度,有正负
     * @param node
     * @return
     */
    public int balanceFactor(Node node){
        if (node == null){
            return 0;
        }
        return getHeight(node.leftNode) - getHeight(node.rightNode);
    }

    /**
     * 对以node为根节点的树进行右旋转
     // 对节点y进行向右旋转操作，返回旋转后新的根节点x
     //        y                              x
     //       / \                           /   \
     //      x   T4     向右旋转 (y)        z     y
     //     / \       - - - - - - - ->    / \   / \
     //    z   T3                       T1  T2 T3 T4
     //   / \
     // T1   T2
     * @param node node
     * @return 旋转后新的子树的根节点
     */
    public Node rightRoate(Node node){
        Node x = node.leftNode;
        Node T3 = x.rightNode;
        x.rightNode = node;
        node.leftNode = T3;

        //旋转完成之后更新树的高度,其实只有x和y的高度发生变化
        x.height = Math.max(getHeight(x.leftNode), getHeight(x.rightNode)) + 1;
        node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;

        return x;
    }

    /**
     * 对以node为根节点的树进行左旋转
     // 对节点y进行向左旋转操作，返回旋转后新的根节点x
     //    y                             x
     //  /  \                          /   \
     // T1   x      向左旋转 (y)       y     z
     //     / \   - - - - - - - ->   / \   / \
     //   T2  z                     T1 T2 T3 T4
     //      / \
     //     T3 T4
     * @param node node
     * @return 返回旋转后新的子树的根
     */
    public Node leftRoate(Node node){
        Node x = node.rightNode;
        Node T2 = x.leftNode;
        x.leftNode = node;
        node.rightNode = T2;
        //旋转完成之后更新树的高度，其实只有x和y的高度发生变化
        x.height = Math.max(getHeight(x.leftNode), getHeight(x.rightNode)) + 1;
        node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;

        return x;
    }

    /**
     * 插入元素
     * @param key
     * @param value
     */
    public void add(K key, V value){
        root = add(root, key, value);
    }

    /**
     * 向以node为根节点的树上插入
     * @param node node
     * @param key key
     * @param value value
     * @return
     */
    private Node add(Node node, K key, V value){
        if (node == null){
            node = new Node(key,value);
            size ++;
            return node;
        }

        if (node.key.compareTo(key) > 0){
            node.leftNode = add(node.leftNode, key, value);
        }else if (node.key.compareTo(key) < 0){
            node.rightNode = add(node.rightNode, key, value);
        }else{
            node.value = value;
        }

        //更新树的高度
        node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;

        //LL
        if (balanceFactor(node) >  1 && (balanceFactor(node.leftNode) > 0)){
            node = rightRoate(node);
        }
        //RR
        if (balanceFactor(node) < -1 && (balanceFactor(node.rightNode ) > 0)){
            node = leftRoate(node);
        }

        //LR
        //        y      -                 y                                x
        //       / \                     /  \                             /   \
        //      x   T4    向左旋转(x)   z    T4        向右旋转 (y)       z     y
        //     / \        - - - - - >  / \           - - - - - - - ->    / \   / \
        //    z   T3                  x  T3                             T1  T2 T3 T4
        //       / \                 /  \
        //     T1   T2              T1  T2
        if (balanceFactor(node) > 1 && (balanceFactor(node.leftNode) < 0)){
            node.leftNode = leftRoate(node.leftNode);
            node = rightRoate(node);
        }

        //RL
        //      y      -                 y                                    z
        //     / \                      /  \                                /   \
        //    T1  x         向右旋转(x) T1  z             向左旋转 (y)      y    x
        //       / \        - - - - - >    / \           - - - - - - - ->  / \   / \
        //      z   T4                    T2  x                           T1  T2 T3 T4
        //     / \                          /  \
        //   T2   T3                       T3  T4
        if (balanceFactor(node) < -1 && (balanceFactor(node.rightNode) > 0)){
            node.rightNode = rightRoate(node.rightNode);
            node = leftRoate(node);
        }

        return node;
    }

    /**
     * 返回以node为根的子树的key所在的节点
     * @param node
     * @param key
     * @return
     */
    private Node getNode(Node node, K key){
        if (node == null){
            return null;
        }
        if (node.key.equals(key)){
            return node;
        }else if (node.key.compareTo(key) > 0){
            return getNode(node.leftNode, key);
        }else {
            return getNode(node.rightNode, key);
        }
    }

    /**
     * 是否包含k这个节点
     * @param key key
     * @return
     */
    public boolean contains(K key){
        return getNode(root, key) != null;
    }

    /**
     * 返回key节点对应的value
     * @param key key
     * @return
     */
    public V get(K key){
        Node node = getNode(root, key);
        return node == null? null : node.value;
    }

    /**
     * 更新某个节点的值
     * @param key
     * @param value
     */
    public void set(K key, V value){
        Node node = getNode(root, key);
        if (node == null){
            throw new IllegalArgumentException("This key does not contains");
        }
        node.value = value;
    }

    /**
     * 删除某个节点对应的元素
     * @param key
     * @return
     */
    public V remove(K key){
        Node node = getNode(root,key);
        if (node == null){
            throw  new IllegalArgumentException("Error");
        }
        root = remove(root, key);
        return node.value;
    }

    /**
     * 返回树中最小的元素的节点
     * @param node
     * @return
     */
    public Node minimum(Node node){
        if (node == null){
            return null;
        }
        if (node.leftNode == null){
            return node;
        }
        return minimum(node.leftNode);
    }

    /**
     * 删除node为节点的树中key的元素
     * @param node
     * @param key
     * @return
     */
    private Node remove(Node node, K key){

        if (node == null){
            return null;
        }
        Node retNode;

        if (node.key.compareTo(key) > 0){
            node.leftNode = remove(node.leftNode, key);
            retNode = node;
        }else if (node.key.compareTo(key) < 0){
            node.rightNode = remove(node.rightNode, key);
            retNode = node;
        }else {

            //左子树为空
            if (node.leftNode == null){
                Node right = node.rightNode;
                node.rightNode = null;
                retNode = right;
                size--;
            }
            //右子树为空
            else if (node.rightNode == null){
                Node left = node.leftNode;
                node.leftNode = null;
                retNode = left;
                size --;
            }
            //左右子树均不为空的时候
            else {
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                Node successor = minimum(node.rightNode);
                successor.rightNode = remove(node.rightNode, successor.key);
                successor.leftNode = node.leftNode;

                node.leftNode = node.rightNode = null;
                 retNode = successor;
            }

            if (retNode == null){
                return null;
            }
            retNode.height = Math.max(getHeight(retNode.rightNode), getHeight(retNode.leftNode));

            //LL
            if (balanceFactor(retNode) >  1 && (balanceFactor(retNode.leftNode) > 0)){
                retNode = rightRoate(retNode);
            }
            //RR
            if (balanceFactor(retNode) < -1 && (balanceFactor(retNode.rightNode ) > 0)){
                retNode = leftRoate(retNode);
            }
            //LR
            if (balanceFactor(retNode) > 1 && (balanceFactor(retNode.leftNode) < 0)){
                retNode.leftNode = leftRoate(retNode.leftNode);
                retNode = rightRoate(retNode);
            }
            //RL
            if (balanceFactor(node) < -1 && (balanceFactor(node.rightNode) > 0)){
                retNode.rightNode = rightRoate(retNode.rightNode);
                retNode = leftRoate(retNode);
            }
        }
        return retNode;
    }
}