数据结构：平衡二叉树

在学习平衡二叉树之前，我们需要先对二叉查找树进行一定的了解，其特征是：查找的性能取决于树的形状。因此在某些极端情况下，二叉查找树会退化为一个线性链表，查找效率的时间复杂度从O(log2n)降到了O(n)。为了规避这个缺点，引入了平衡二叉树。可以理解为平衡二叉树是基于二叉查找树的优化。

 

平衡二叉树在二叉查找树的基础之上增加了一个新的特性：每一个节点的左子树与右子树高度相差最多为1，这个高度的限制就可以避免出现树结构退化为线性链表的情况。因此，即便是在最坏情况下，平衡二叉树的查找，插入，删除时间复杂度都为O(log2n)。

 

实现原理

在了解了平衡二叉树大致的概念后，再看一下它具体实现的方式吧(゜▽゜*)

既然是要求每一个节点的左子树与右子树高度相差最多为1，那么就可以对节点对象引入一个属性值进行判断，这个属性值也就是平衡因子，其值为节点的左子树深度 - 右子树深度。在构建一棵平衡二叉树时，每当插入一个新的节点，都需要检查插入后是否破坏了树的平衡，如果失衡，那么则需要通过旋转去改变树的结构，使其再次平衡。

可以说旋转是平衡二叉树的核心，也是相对来说比较难懂的概念了，当然难懂只是针对于我这种空间想象能力比较差的( ′⌒`)

当然旋转也分几种情况，下面通过图片进行每种情况的示例：

 

旋转

①在节点X的左孩子节点的左子树中插入了新的元素（简称左左）

如图，在节点9的左孩子5的左子树3插入了新的节点2，可以判断出节点9为失衡节点。

此时我们对失衡节点9进行一次以轴为节点5的右旋转，该树再次恢复了平衡。

 

代码实现

可以观察到，节点8从节点5的右孩子变为了节点9的左孩子，节点5从节点9的左孩子变为了9的父节点。

那么我们可以对此进行代码描述

    private AVLNode<T> rotateRight(AVLNode<T> x){
        //w节点为失衡节点x的左孩子
        AVLNode<T> w = x.left;
        //1 失衡节点的左孩子变为w节点的右孩子
        x.left=w.right;
        //2 w节点的右孩子变为失衡节点x
        w.right=x;
        //重新计算x节点和w节点的高度
        x.height=Math.max(height(x.left),height(x.right))+1;
        w.height=Math.max(height(w.left),x.height)+1;
        return w;//返回新的根结点
    }

 

②在节点X的右孩子节点的右子树中插入了元素（简称右右）

如图，在节点5的右孩子9的右子树11插入了新的节点14，可以判断出节点5为失衡节点。

此时我们对失衡节点5进行一次以轴为节点9的左旋转，该树再次恢复了平衡。

 

代码实现

可以观察到，节点7从节点9的左孩子变为了节点5的右孩子，节点9从节点5的右孩子变为了5的父节点。

不知道各位有没有发现，右右的情况完全是与左左相反的。

那么我们可以对此进行代码描述

    private AVLNode<T> rotateLeft(AVLNode<T> w){
        //x为失衡结点w的右节点
        AVLNode<T> x=w.right;
        //将失衡结点w的右子树变为x的左子树
        w.right=x.left;
        //x的左子树变为失衡结点x
        x.left=w;
        //重新计算x w的高度
        x.height=Math.max(height(x.left),w.height)+1;
        w.height=Math.max(height(w.left),height(w.right))+1;
        //返回新的根结点
        return x;
    }

 

③在节点X的左孩子节点的右子树中插入了元素（简称左右）

该情况就稍微有些复杂了，我们仅通过一次旋转并不能获取到平衡的二叉树，此时需要先通过一次左旋转将其不稳定二叉树转换为左左的情况，再通过一次右旋转得到平衡二叉树。

如图，在节点15的左孩子6的右子树8插入了新的节点10，可以判断出节点15为失衡节点。

将节点6进行一次以8为轴的左旋转，此时得到我们之前分析的第①种情况：左左

此时再将节点15进行一次以8为轴的右旋转，该树再次恢复了平衡。

 

代码实现

可以观察到，在原树中插入了节点10以后，节点15变成了失衡节点，此时需要把节点8变为根节点才能重新恢复平衡。因此需要先对失衡节点的左孩子8进行左旋转，在对失衡节点15进行右旋转。

private AVLNode<T> RotateLeftAndRight(AVLNode<T> x){
    //x的左孩子先进行左旋转
    x.left=singleRotateRight(x.left);
    //再进行x的右旋转
    return singleRotateLeft(x);
}

 

 

④在节点X的右孩子节点的左子树中插入了元素（简称右左）

与情况③互为镜像，此时需要先通过一次右旋转将其不稳定二叉树转换为右右的情况，再通过一次左旋转得到平衡二叉树。

如图，在节点8的右孩子15的左子树10插入了新的节点9，可以判断出节点8为失衡节点。

将节点10进行一次以15为轴的右旋转，此时得到我们之前分析的第②种情况：右右

此时再将结点8进行一次以10为轴的左旋转，该树再次恢复了平衡。

 

代码实现

与情况③互为镜像

private AVLNode<T> rotateRightAndLeft(AVLNode<T> x){
    //x的右孩子先进行右旋转
    x.right=rotateRight(x.right);
    //再进行x的左旋转
    return rotateLeft(x);
}