平衡二叉树

发表于 | Edited on | 分类于 | Comments： | Views： ℃

1. 平衡二叉树的定义

定义

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

AVL树特性

一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二叉查找树(空树的高度为-1)，这个差值也称为平衡因子（其取值可以是1，0，-1，平衡因子是某个结点左右子树层数的差值，有的书上定义是左边减去右边，有的书上定义是右边减去左边，这样可能会有正负的区别，但是这个并不影响我们对平衡二叉树的讨论）此处输入图片的描述

图(1)显然就是一棵平衡二叉树，它每个结点的左子树和右子树的高度最多相差1，同时也是一棵二叉查找树，而图二虽然也是一棵二叉查找树，但是它每个结点的左子树和右子树的高度相差却到达了2，因此不是平衡二叉树。理解了平衡二叉树的概念后，我们在思考一下，那些操作可能引起平衡发生变化呢？显然只有那些引起结点数量变化的操作才可能导致平衡被改变，也就是删除和插入操作了，如下图，我们把6插入到图a后，结构变成了图b，这时原本的平衡二叉树就失去平衡了。

此处输入图片的描述

显然图b已失去平衡，如果发生这样的情况，我们就必须考虑插入元素后恢复二叉树的平衡性质，实际上也总是可以通过对树进行简单的修复来让其重新恢复到平衡，而这样的简单操作我们就称之为旋转，当然旋转也有单旋转和双旋转之分，无论是插入还是删除，只有那些从插入或者删除点到根结点的路径上的结点的平衡才有可能被改变，因为只有这些结点的子树才可能发生变化，所以最终也只需针对这些点进行平衡修复操作即可。

2. 平衡二叉树的设计与实现

2.1 AVL节点定义

class AvlNode<T>{
    T data;
    AvlNode<T> left;
    AvlNode<T> right;
    int height;
    
    AvlNode(T thedata){
        this(thedata, null, null);
    }
    
    AvlNode(T thedata, AvlNode<T> lt, AvlNode<T> rt){
        data = thedata;
        left = lt;
        right = rt;
        height = 0;
    }
}

为了满足平衡二叉树的特性，需要在原来的二叉搜索树(BST)的结点中添加一个height的字段表示高度，方便我们计算，这里强调一下，高度和深度一组相反的概念，高度是指当前结点到叶子结点的最长路径，如所有叶子结点的高度都为0，而深度则是指从根结点到当前结点的最大路径，如根结点的深度为0。这里约定空结点（空子树）的高度为-1，叶子结点的高度为0，非叶子节点的高度则根据其子树的高度而计算获取，如下图：
此处输入图片的描述

2.2 平衡二叉树的单旋转算法与实现

左左单旋转(LL)

从下图可以看出，结点X并不能满足AVL树的性质，因为它的左子树比右子树深2层，这种情况就是典型的LL情景，此时需要通过右向旋转来修复失衡的树，如图1，X经过右旋转后变成图2，W变为根结点，X变为W的右子树，同时W的右子树变为X的左子树，树又重新回到平衡，各个结点的子树高度差都已在正常范围。一般情况下，我们把X结点称为失衡点，修复一棵被破坏的AVL树时，找到失衡点是很重要的并把通过一次旋转即可修复平衡的操作叫做单旋转，从图3和图4可知，在原始AVL树插入7结点后，结点9变为失衡点，树再满足AVL性质，因此需要对9结点进行左左单旋转(即向右旋转)后，得到图4，我们发现此时并没有操作树的根结点(6)，实际上这是因为正常情况下，不必从树的根结点进行旋转，而是从插入结点处开始，向上遍历树，并更新和修复在这个路径上的每个结点的平衡及其平衡信息(高度)即可。

此处输入图片的描述

代码实现：

/**
 * 左左情况单旋转
 * @param k2
 * @return
 */
private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2){
    AvlNode<T> k1 = k2.left; //把k1结点旋转为根结点
    k2.left = k1.right;      //同时k1的右子树变为k2的左子树
    k1.right = k2;           //k2变为k1的右子树
    k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
    k1.height = Math.max(height(k1.left), k2.height) + 1;
    return k1;      //返回新的根  
}

右右单旋转(RR)

接着再来看看右右单旋转(RR)的情景，如下图，可以发现与左左单旋转的情况恰好是一种镜像关系，同样结点X并不能满足AVL树的性质，在这样的情景下，需要对X结点进行左旋转来修复树的平衡，如图1经左旋转后变了图2，此时X变为了根结点，W变为X的左孩子，X的左子树变为W的右子树，而树又重新恢复了平衡。如图3和图4的实例情景，原始的AVL树在12处插入结点18后，结点10就变成了失衡点，因为10的左子树和右子树的高度相差2，显然不符合AVL树性质，需要对结点10进行右右单旋转修复(向左旋转)，然后得到图4，此时树重新回到了平衡，这便是右右单旋转(RR)的修复情景。

此处输入图片的描述
代码实现：

/**
  * 右右情况单旋转  
  * @param k2
  * @return
  */
 private AvlNode<T> rotateWithRightChild(AvlNode<T> k2){
     AvlNode<T> k1 = k2.right;  //把k1结点旋转为根结点
     k2.right = k1.left;        //同时k1的左子树变为k2的右子树
     k1.left = k2;              //k2变为k1的左子树
     k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
     k1.height = Math.max(height(k1.right), k2.height) + 1;
     return k1;      //返回新的根   
 }

2.3 平衡二叉树的双旋转算法与实现

前面两种情景都已分析完，它们都是基于单旋转的算法，但这种算法存在一个问题，那就是对情景②③无法生效，根本问题在于子树Y太深了，如下图所示：
此处输入图片的描述
显然经过一次单旋转的修复后无论是X或者W作为根结点都无法符合AVL树的性质，此时就需要用双旋转算法来实现了。

左右双旋转(LR)

为了重新平衡，通过上述的分析显然不能把X根结点，而X与W间的旋转也解决不了问题，那唯一的旋转就是把Y作为新根。这样的话，X、W就不得不成为Y的孩子结点，其中W作为Y的左孩子结点，而X成为Y的右孩子结点。这里我们以下图为例来分析，为了达到以上结果，需要W、Y进行单旋转（图1），这里我们可把WY组成的子树看成前面的右右旋转情景，然后进行左向旋转，得到图2，W变为Y的左子树同时Y的左子树B变成W的右子树，其他不变，到此第一次旋转完成，进行第二次旋转，以X结点向右进行旋转(同样可看作左左情景)，由图2得到图3，X变成Y的右孩子结点并且Y的右子树C变成X的左子树，第二次旋转完成，树也重新恢复到平衡。

此处输入图片的描述
在左右双旋转实例图中，在原AVL树种插入结点7后，结点8变成了失衡点，此时需要把6结点变为根结点才能重新恢复平衡。因此先进行左向旋转再进行右向旋转，最后树恢复平衡。算法代码实现如下：

/**
 * 左右旋转
 * @param k3
 * @return
 */
private AvlNode<T> doubleWithLeftChild(AvlNode<T> k3){
    try{
        k3.left = rotateWithRightChild(k3.left);  //k3的左孩子节点进行RR旋转
    }catch(NullPointerException e){
        throw e;
    }
    return rotateWithLeftChild(k3);    //k3进行LL旋转
}

右左双旋转(RL)

此处输入图片的描述

实现代码：

/**
  * 右左旋转
  * @param k3
  * @return
  */
 private AvlNode<T> doubleWithRightChild(AvlNode<T> k3){
     try{
         k3.right = rotateWithLeftChild(k3.right);
     }catch(NullPointerException e){
         throw e;
     }
     return rotateWithRightChild(k3);
 }

2.4 平衡二叉树插入操作的实现

与BST（二叉查找树）的插入实现原理一样，使用递归算法，根据值大小查找到插入位置，然后进行插入操作，插入完成后，我们需要进行平衡判断，评估子树是否需要进行平衡修复，需要则利用上述的四种情景套入代码即可，最后要记得重新计算插入结点路径上的高度。代码实现如下：

public void insert(T data){
      root = insert(data, root);
}
 private AvlNode<T> insert(T x, AvlNode<T> t){
      if(t == null) {
          t=new AvlNode<T>(x, null, null);
      }else {
          int compareResult = myCompare(x, t.data);
          if (compareResult < 0) {
              t.left = insert(x, t.left);
              if (height(t.left) - height(t.right) == 2) {
                  if (myCompare(x, t.left.data) < 0)     //左左情况
                      t = rotateWithLeftChild(t);
                  else                                    //左右情况
                      t = doubleWithLeftChild(t);
              }
          } else if (compareResult > 0) {
              t.right = insert(x, t.right);
              if (height(t.right) - height(t.left) == 2) {
                  if (myCompare(x, t.right.data) < 0)        //右左情况
                      t = doubleWithRightChild(t);
                  else                                        //右右情况
                      t = rotateWithRightChild(t);
              }
          }
      }
      //完了之后更新height值  
      t.height = Math.max(height(t.left), height(t.right))+1;
      return t;
  }

2.5 平衡二叉树删除操作的实现

递归的实现方案:和二叉查找树中删除方法的实现类似，但是在移除结点后需要进行平衡检测，以便判断是否需要进行平衡修复，这种实现方式在删除时效率并不高。下面给出实现代码：

public void remove(T data){
    root = remove(data, root);
}
private AvlNode<T> remove(T data,AvlNode<T> p){

    if(p ==null)
        return null;

    int result=data.compareTo(p.data);

    //从左子树查找需要删除的元素
    if(result<0){
        p.left=remove(data,p.left);

        //检测是否平衡
        if(height(p.right)-height(p.left)==2){
            AvlNode<T> currentNode=p.right;
            //判断需要那种旋转
            if(height(currentNode.left)>height(currentNode.right)){
                //LL
                p=rotateWithLeftChild(p);
            }else{
                //LR
                p=doubleWithLeftChild(p);
            }
        }

    }
    //从右子树查找需要删除的元素
    else if(result>0){
        p.right=remove(data,p.right);
        //检测是否平衡
        if(height(p.left)-height(p.right)==2){
            AvlNode<T> currentNode=p.left;
            //判断需要那种旋转
            if(height(currentNode.right)>height(currentNode.left)){
                //RR
                p=rotateWithRightChild(p);
            }else{
                //RL
                p=doubleWithRightChild(p);
            }
        }
    }
    //已找到需要删除的元素,并且要删除的结点拥有两个子节点
    else if(p.right!=null&&p.left!=null){

        //寻找替换结点
        p.data=findMin(p.right).data;

        //移除用于替换的结点
        p.right = remove( p.data, p.right );
    }
    else {
        //只有一个孩子结点或者只是叶子结点的情况
        p=(p.left!=null)? p.left:p.right;
    }

    //更新高度值
    if(p!=null)
        p.height = Math.max( height( p.left ), height( p.right ) ) + 1;
    return p;
}

2.6 中序遍历

public void print(){
    print(this.root);
}
private void print(AvlNode node){
    if(node != null){
        print(node.left);
        System.out.println(node.data+",");
        print(node.right);
    }
}
-------------本文结束感谢您的阅读-------------