【原】初探AVL树

树在计算机中是一种非常重要的数据结构，而二叉树是每个节点最多有两个子节点，没有子节点的称为叶节点。今天我想总结一些有关AVL树的相关知识。
AVL tree是一个二叉搜索树，从名字我们就可以看出来，其目的是为了提高二叉排序树的搜索性能，其查找数据的时间复杂度为：O(log n)，n为节点个数。
平衡因子：左子树高度-右子树高度
形成一个AVL树有以下条件：

• 如果树是AVL树，那么它的左右子树都是AVL树。
• 左右子树高度差小于1。

AVL树的插入：
我们把距离插入点最近的不平衡点称为X节点，这时候，有四种情况需要考虑：

1. 插入前A节点平衡因子为-1，插入节点在X的左子树中，不影响树的平衡。
2. 插入前A节点平衡因子为1，插入节点在X的右子树中，不影响树的平衡。
3. 插入前A节点平衡因子为-1，插入节点在X的右子树中，影响树的平衡。
4. 插入前A节点平衡因子为1，插入节点在X的左子树中，影响树的平衡。
   
   通常把第3种情况称为R型不平衡，也就是上图中所示的不平衡状态。插入在X节点的右子树的右子树上，称为RR型(如上图所示)，插入在X节点的右子树的左子树上，称为RL型。同理第4种情况对应的不平衡有LL型和LR型。
   平衡的调整：
   对于情况RR和LL我称之为外侧插入，可以使用单旋转方式调整解决。
   

当类似图一中的RR型插入，单旋转之后结果：

当类似图二左图的LL型插入，单旋转之后

情况LR和RL我称之为内侧插入，可以使用双旋转方式调整解决。

上图经过一次旋转之后：

再经过一次旋转之后：

AVL树的删除：

AVL树的删除操作和插入操作相比较起来，肯定是删除操作比较繁琐复杂一些，因为插入只涉及到插入，而删除首先得确定被删除节点，接下来可能涉及到删除之后的重新调整平衡(插入操作)，其实调整平衡的操作相当于又一次的插入过程。
在介绍不平衡状态之前，首先统一下称呼，我们把删除发生在左子树，删除之后平衡因子变为-2的情况，称为L型，对应的右子树删除，平衡因子变为2的情况，我们称之为R型。
可能出现需要调整的不平衡情况(L型与R型对称，此处只说L型)：
1.L0型的删除，如下图：

删除前如上图，此处我们是L型，所以删除值为4的节点。删除调整之后，如下图所示：

由上图可以看出，L0型的调整实际上是对根节点进行一次左旋调整得到，便得到了平衡的AVL树，R0型相对应的做一次右旋操作。
2.L(-1)型的调整：

删除前如上图所示，删除值为4的节点，删除之后，出现根节点的平衡因子变为-2的情况，所以进行调整，如下图：

经过一次左旋之后，节点的平衡因子都变成了0。与L(-1)对应的是R1型，R1型需要做一次右旋，此处不再详述。
3.L1型的删除调整：

L1型的AVL树，如上图所示，此时我们需要删除节点值为4的节点，值为9的节点处出现了平衡因子值为1，所以称L1型，删除调整：

删除节点值为4的节点之后，第一次旋转，以值为9的节点进行右旋，如上图所示。接下来进行第二次旋转：

再进行一次左旋，得到如图AVL树。R(-1)和L1是对称的。
以上有关AVL树的知识点，只是一个小小的原理总结，之后哪天心血来潮的话，在博客上更新一下C语言代码实现。

“鸟欲高飞先振翅,人求上进先读书。”—李苦禅