图解平衡二叉树

平衡二叉树这个概念对于学过数据结构的人来说并不陌生，平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），它是一棵空树，或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

    平衡二叉树一般是一个有序树，它具有二叉树的所有性质，其遍历操作和二叉树的遍历操作相同。但是由于其对二叉树施加了额外限制，因而其添加、删除操作都必须保证平衡二叉树的因子被保持。

    平衡二叉树中引入了一个概念：平衡二叉树节点的平衡因子，它指的是该节点的两个子树，即左子树和右子树的高度差，即用左子树的高度减去右子树的高度，如果该节点的某个子树不存在，则该子树的高度为0,如果高度差的绝对值超过1就要根据情况进行调整。平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1;

很显然，平衡二叉树是在二叉排序树(BST)上引入的，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降，那么AVL就保持住了(BST)的最好时间复杂度O(logn)，所以每次的插入和删除都要确保二叉树的平衡，那么怎么保持平衡呢？

为了更好的明白下面的图解和代码，我们先来看平衡二叉树结构定义：

typedef struct AVLNode *Tree;

typedef int ElementType;

struct AVLNode

{

    int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡

    Tree parent; //该结点的父节点，方便操作

    ElementType val; //结点值

    Tree lchild;

    Tree rchild;

    AVLNode(int val=0) //默认构造函数

    {

        parent=NULL;

        depth=0;

        lchild=rchild=NULL;

        this->val=val;

    }

};

把需要重新平衡的结点叫做α，由于任意两个结点最多只有两个儿子，因此高度不平衡时，α结点的两颗子树的高度相差2.容易看出，这种不平衡可能出现在下面4中情况中：

1.对α的左儿子的左子树进行一次插入

2.对α的左儿子的右子树进行一次插入

3.对α的右儿子的左子树进行一次插入

4.对α的右儿子的右子树进行一次插入

情形1和情形4是关于α的镜像对称，二情形2和情形3也是关于α的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。

第一种情况是插入发生在“外边”的情形（左左或右右），该情况可以通过一次单旋转完成调整；第二种情况是插入发生在“内部”的情形（左右或右左），这种情况比较复杂，需要通过双旋转来调整。

我们针对平衡二叉树出现不平衡的情况，推出了旋转的方法。

一、单旋转

 

上图是左左的情况，k2结点不满足平衡性，它的左子树k1比右子树z深两层，k1子树中更深的是k1的左子树x，因此属于左左情况。

 

为了恢复平衡，我们把x上移一层，并把z下移一层，但此时实际已经超出了AVL树的性质要求。为此，重新安排结点以形成一颗等价的树。为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。这种情况称之为单旋转。

二、双旋转

对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转，也就是双旋转。

对于上图的情况，为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后就变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。

平衡二叉树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

想要更深入学习平衡二叉树或者其他数据结构的小伙伴可以在本站的数据结构专题页面学习更多相关知识，等你沉浸到数据结构的世界当中才会发现一入‘’数据‘’深似海，从此‘’结构‘’是路人。