数据结构——平衡二叉树（AVL树）（java版）

1 引言

二叉树是数据结构中的重点与难点，也是应用较为广泛的一类数据结构。二叉树的基础知识在之前的数据结构——二叉树基础中已经详细介绍。本篇文章将着重介绍两类二叉树，二叉搜索树和平衡二叉树。

1.1 为什么要有树结构？

2 二叉搜索树

2.1 定义

二叉搜索树又称二叉查找树，亦称为二叉排序树。设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y] <= key[x]；如果y是x的右子树的一个节点，则key[y] >= key[x]。

2.2 性质

（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）左、右子树也分别为二叉搜索树；

例如：下图所示的二叉树为一棵二叉搜索树。

  例如：下图所示不是一棵二叉搜索树，因为节点40的左孩子节点值为44，不满足二叉搜索树的定义。

2.3 节点结构

二叉树的节点结构通常包含三部分，其中有：左孩子的指针，右孩子指针以及节点元素。节点的图示如下：

代码定义：

    private class Node{

        public E e;
        public Node left ,right;

        public Node(E e){
            this.e = e;//元素
            left = null;//左孩子
            right = null;//右孩子
        }
    }

2.4 创建二叉搜索树

现有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下：

（1）i = 0，A[0] = 61，节点61作为根节点；
  （2）i = 1，A[1] = 87，87 > 61，且节点61右孩子为空，故81为61节点的右孩子；
  （3）i = 2，A[2] = 59，59 < 61，且节点61左孩子为空，故59为61节点的左孩子；
  （4）i = 3，A[3] = 47，47 < 59，且节点59左孩子为空，故47为59节点的左孩子；
  （5）i = 4，A[4] = 35，35 < 47，且节点47左孩子为空，故35为47节点的左孩子；
  （6）i = 5，A[5] = 73，73 < 87，且节点87左孩子为空，故73为87节点的左孩子；
  （7）i = 6，A[6] = 51，47 < 51，且节点47右孩子为空，故51为47节点的右孩子；
  （8）i = 7，A[7] = 98，98 < 87，且节点87右孩子为空，故98为87节点的右孩子；
  （9）i = 8，A[8] = 93，93 < 98，且节点98左孩子为空，故93为98节点的左孩子；创建完毕后如下图中的二叉搜索树：

2.5 查找

查找流程：

（1）如果树是空的，则查找结束，无匹配，返回false。
（2）如果被查找的值和节点的值相等，查找成功，返回true。
（3）如果被查找的值小于节点的值，递归查找左子树。
（4）如果被查找的值大于节点的值，递归查找右子树。

查找代码：

    //看二分搜索树中是否包含元素e
    public boolean contains(E e){
        return contains(root,e);
    }

    //看以node为根的二分搜索树中是否包含元素e , 递归算法
    private boolean contains(Node node , E e){
        if(node == null){
            return false;
        }
        if(e.compareTo(node.e) == 0){
            return true;
        }else if(e.compareTo(node.e) < 0){
            return contains(node.left,e);
        }else{//e.compareTo(node.e) > 0
            return contains(node.right , e);
        }
    }

使用二叉搜索树可以提高查找效率，其平均时间复杂度为O(log2n)。

2.6 插入

插入流程：

（1）先检测该元素是否在树中已经存在。如果已经存在，则不进行插入；
（2）若元素不存在，则进行查找过程，并将元素插入在查找结束的位置。

图解过程：

代码实现：

    //向node为根的二分搜索树中插入元素E，递归算法
    //返回插入新节点后二分搜索树的根
    //如果node为null，则新建一个节点，然后把传入的值赋值上
    //如果compareTo > 0则向它右子树插入元素，反之向左子树
    //左子树和右子树重新赋值后，返回的node还是以node为根的二分搜索树
    private Node add(Node node , E e){
        if(node == null){
            size ++;
            return new Node(e);
        }

        if(e.compareTo(node.e) < 0){
            node.left = add(node.left,e);
        }else if(e.compareTo(node.e) > 0){
            node.right = add(node.right,e);
        }
        return node;
    }

2.7 删除

（1）删除节点为叶子节点

删除叶子节点的方式最为简单，只需查找到该节点，直接删除即可。例如删除图2.4中的叶子节点37、节点51、节点60、节点73和节点93的方式是相同的。

（2） 删除的节点只有左子树

删除的节点若只有左子树，将节点的左子树替代该节点位置。例如：删除图2.4中的98节点：

（3）删除的节点只有右子树

删除的节点若只有右子树，将节点的右子树替代该节点位置。这种情况与删除左子树处理方式类似，不再赘述。

（4） 删除的节点既有左子树又有右子树。

  若删除的节点既有左子树又有右子树，这种节点删除过程相对复杂。其流程如下：
  （1）遍历待删除节点的左子树，找到其左子树中的最大节点，即删除节点的前驱节点；
  （2）将最大节点代替被删除节点；
  （3）删除左子树中的最大节点；
  （4）左子树中待删除最大节点一定为叶子节点或者仅有左子树。按照之前情形删除即可。

注：同样可以使用删除节点的右子树中最小节点，即后继节点代替删除节点，此流程与使用前驱节点类似。

删除代码：

    //返回以node为根的二分搜索树的最小值所在的节点
    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    //从二分搜索树中删除元素为e的节点
    public void remove(E e){
        root = remove(root, e);
    }

    //删除以node为根的二分搜索树中值为e的节点，递归算法
    //返回删除节点后新的二分搜索树的根
    private Node remove(Node node , E e){
         if(node == null){
             return null;
         }
         if(e.compareTo(node.e) < 0){
             node.left = remove(node.left ,e);
             return node;
         }else if(e.compareTo(node.e) > 0){
             node.right = remove(node.right , e);
             return node;
         }else{// e == node.e

             //待删除节点左子树为空的情况
             if(node.left == null){
                 Node rightNode = node.right;
                 node.right = null;
                 size --;
                 return rightNode;
             }

             //待删除节点右子树为空的情况
             if(node.right == null){
                 Node leftNode = node.left;
                 node.left = null;
                 size --;
                 return leftNode;
             }

             //待删除节点左右子树均不为空的情况
             //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
             //用这个节点顶替待删除节点的位置
             Node successor = minimum(node.right);
             //因为要替换删除节点的位置，所以删除节点右子树的最小节点
             successor.right = removeMin(node.right);
             successor.left = node.left;
             size++;
             //将要删除节点的左右子树从二叉树中断开
             node.left = node.right = null;
             //维护二叉树长度
             size--;
             //返回新节点successor，让根节点指向新节点successor
             return successor;
         }
    }
    
    //删除掉以node为根的二分搜索树中的最小节点
    //返回删除节点后新的二分搜索树的根
    //把左孩子删除后，返回右孩子
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

3 平衡二叉树

3.1 定义

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如下图所示。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为O(n)。

  在此二叉搜索树中查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列A，改为下图所示方式存储，查找元素6时只需比较3次，查找效率提升一倍。

  可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。

3.1.1 AVL

二分搜索树可能退化成链表，所以引入AVL平衡二叉树的概念，AVL树也是二分搜索树

3.2 平衡因子

定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于1的节点。在一棵平衡二叉树中，节点的平衡因子只能取-1、1或者0。
 
下图蓝色部分为平衡因子，黑色部分为层数

3.3 节点结构

定义平衡二叉树的节点结构：

    private class Node{
        public K key;
        public V value;
        public Node left,right;
        public int height;//深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡

        public Node(K key,V value){//默认构造函数
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            height = 1;
        }
    }

对于给定结点数为n的AVL树，最大高度为O(log2n).

3.4 左旋与右旋

（1） 左旋

如下图所示的平衡二叉树

如在此平衡二叉树插入节点62，树结构变为：

  可以得出40节点的左子树高度为1，右子树高度为3，此时平衡因子为-2，树失去平衡。为保证树的平衡，此时需要对节点40做出旋转，因为右子树高度高于左子树，对节点进行左旋操作，流程如下：
  （1）节点的右孩子替代此节点位置
  （2）右孩子的左子树变为该节点的右子树
  （3）节点本身变为右孩子的左子树

图解过程：

（2）右旋

右旋操作与左旋类似，操作流程为：
  （1）节点的左孩子代表此节点
  （2）节点的左孩子的右子树变为节点的左子树
  （3）将此节点作为左孩子节点的右子树。

图解过程：

3.5 插入

假设一颗AVL 树的某个节点为A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有AVL 树的平衡性 。平衡二叉树插入节点的情况分为以下四种：

（1） A的左孩子的左子树插入节点(LL)

例如：下图所示的平衡二叉树：

节点A的左孩子为B，B的左子树为D，无论在节点D的左子树或者右子树中插入F均会导致节点A失衡。因此需要对节点A进行旋转操作。A的平衡因子为2，值为正，因此对A进行右旋操作。

图解过程：

代码实现：

    //LL
    //不平衡的原因是左侧的左侧多添加了一个节点
    if(balanceFactor > 1 && getBalanceFactor(node.left) >=0){
       //返回递归的上一层，继续处理上一层的节点
       //至此，新的根节点，就已经保证了，以这个根节点为根的，
       //整棵二叉树即是一个二分搜索树，又是一棵平衡二叉树
       return rightRotate(node);
    }

    //获得节点node的平衡因子
    private int getBalanceFactor(Node node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }
    //获得节点node的高度
    private int getHeight(Node node){
        if(node == null){
            return 0 ;
        }
        return node.height;
    }
    
    //对节点y进行向右旋转操作，返回旋转后新的根节点x
    //            y                             x
    //           / \\    向右旋转(y)            /   \\
    //          x   T4  ------------>        z     y
    //         / \\                          / \\   / \\
    //        z   T3                       T1 T2 T3 T4
    //       / \\
    //      T1  T2
    private Node rightRotate(Node y){

        Node x = y.left;
        Node T3 = x.right;

        //向右旋转过程
        x.right = y;
        y.left = T3;

        //更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;

    }

（2） A的右孩子的右子树插入节点(RR)

如下图所示：插入节点F后，节点A的平衡因子为-2，对节点A进行左旋操作。

图解过程：

代码实现：

    //RR
    if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
        //新的根节点返回回去，返回给递归调用的上一层
        //以这个新的根节点为根的二叉树，就满足了平衡二叉树，又满足了二分搜索树的性质
        return leftRotate(node);
    }

    //获得节点node的平衡因子
    private int getBalanceFactor(Node node){
        if(node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }
    //获得节点node的高度
    private int getHeight(Node node){
        if(node == null){
            return 0 ;
        }
        return node.height;
    }

    //对节点y进行向左旋转操作，返回旋转后新的根节点x
    //            y                             x
    //           / \\    向左旋转(y)            /   \\
    //          T1  x  ------------>         y     z
    //             / \\                      / \\   / \\
    //            T2  z                    T1 T2 T3 T4
    //               / \\
    //              T3 T4
    private Node leftRotate(Node y){

        Node x = y.right;
        Node T2 = x.left;

        //向左旋转过程
        x.left = y;
        y.right = T2;

        //更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;
    }

（3） A的左孩子的右子树插入节点(LR)

若A的左孩子节点B的右子树E插入节点F，导致节点A失衡。

A的平衡因子为2，若仍按照右旋调整，调整过程如下：

  经过右旋调整发现，调整后树仍然失衡，说明这种情况单纯的进行右旋操作不能使树重新平衡。那么这种插入方式需要执行两步操作：
  （1）对失衡节点A的左孩子B进行左旋操作，即RR情形操作。
  （2）对失衡节点A做右旋操作，即LL情形操作。

图解过程：

代码实现：

    //LR
    //左子树比右子树高，高度差比1大，所以是不平衡的
    if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

（4） A的右孩子的左子树插入节点(RL)

右孩子插入左节点的过程与左孩子插入右节点过程类似，只需对右孩子进行LL操作，然后在对节点进行RR操作。

图解过程：

代码实现：

        //RL
        //右子树比左子树高，高度差比小于-1，所以是不平衡的
        if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

3.6 删除

平衡二叉树的删除情况与二叉搜索树删除情况相同，同样分为以下四种情况：
  （1）删除叶子节点
  （2）删除节点只有左子树
  （3）删除节点只有右子树
  （4）删除节点既有左子树又有右子树
  平衡二叉树的节点删除与二叉搜索树删除方法一致，但是需要在节点删除后判断树是否仍然保持平衡，若出现失衡情况，需要进行调整。

代码实现：

    //删除掉以node为根的二分搜索树中键为key的节点，递归算法
    //返回删除节点后新的二分搜索树的根
    private Node remove(Node node, K key){
        if(node ==null){
            return null;
        }
        Node retNode;
        if(key.compareTo(node.key) < 0){
            node.left = remove(node.left,key);
            retNode = node;
        }else if(key.compareTo(node.key) > 0){
            node.right = remove(node.right , key);
            retNode =  node;
        }else { //key.compareTo(node.key) == 0
            //待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size -- ;
                retNode = rightNode;
            }
            //待删除节点右子树为空的情况
            else if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size -- ;
                retNode = leftNode;
            }else{
                //待删除节点左右子树均不为空的情况
                //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor = minimum(node.right);
                successor.right = remove(node.right, successor.key);
                successor.left = node.left;

                node.left = node.right = null;

                retNode = successor;
            }
        }
        if(retNode == null){
            return null;
        }else{

            //更新height
            retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

            //计算平衡因子
            int balanceFactor = getBalanceFactor(retNode);

            //平衡维护
            //LL
            //不平衡的原因是左侧的左侧多添加了一个节点
            if(balanceFactor > 1 && getBalanceFactor(retNode.left) >=0){
                //返回递归的上一层，继续处理上一层的节点
                //至此，新的根节点，就已经保证了，以这个根节点为根的，
                //整棵二叉树即是一个二分搜索树，又是一棵平衡二叉树
                return rightRotate(retNode);
            }
            //RR
            if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
                //新的根节点返回回去，返回给递归调用的上一层
                //以这个新的根节点为根的二叉树，就满足了平衡二叉树，又满足了二分搜索树的性质
                return leftRotate(retNode);
            }

            //LR
            //左子树比右子树高，高度差比1大，所以是不平衡的
            if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
                node.left = leftRotate(retNode.left);
                return rightRotate(retNode);
            }

            //RL
            if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
                node.right = rightRotate(retNode.right);
                return leftRotate(retNode);
            }

            return retNode;
        }
    }

4 结语

平衡二叉树的旋转问题是二叉树学习中的重点与难点，希望读者通过本文可以更好的理解二叉树的操作。

推荐阅读

数据结构——二叉树基础