树 Story —— 平衡二叉树
本文详细阐述了平衡二叉树 原理，适合新手阅读，以及老手回顾。
在计算机科学中，AVL 树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。二叉查找树查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n)。AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
平衡二叉树，又被称为「AVL树」，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
（我们平时所说的平衡二叉树，大部分指的是平衡二叉排序树，但是单说平衡二叉树的话，并不一定是有序的）
平衡二叉树
以上三个都是二叉平衡树，只要满足左右子树高度差不超过 1 ，就是平衡二叉树。
子树高度
而上图虽然和上上面三个二叉树很像，但是它是不平衡的，节点 18 的左子树高度是 0，而右子树高度是 2，所以它不是平衡二叉树。
如何将不平衡二叉树调节成平衡二叉树呢？
在平衡二叉树插入或删除之前，二叉树一定是平衡的。插入或删除节点，导致了二叉树不平衡。
插入导致不平衡状态有四种情形：左左、左右、右右、右左。
插入节点
插入节点 LL
插入节点 LR
为什么要分四种情况呢？因为四种的插入方式，会导致不同的平衡策略。
其实这四种情况，可以缩减为两种，剩下的两种只是相互对称的处理方式。
如果情况是 左左（右右）那么可以通过一次右旋（左旋）即可完成平衡，而左右（右左）则需要左旋+右旋（右旋+左旋）来完成平衡，下面我们分别介绍一下这四次平衡的过程。
右旋节点10
当插入节点属于「左左」时，我们只需要将根节点「右旋」，即可使二叉树平衡。右旋的流程如下
右旋过程
假设需要右旋节点 10，蓝色标记。将节点 10 的左子节点向上提到根节点 10 的位置，节点 10 移动为节点 7 的右子节点，而节点 7 的原右子节点则成为节点 10 的左子节点。
左旋过程
左旋 + 右旋
当时左右或者右左的时候，需要进行两次旋转才可以使二叉树平衡。
左右的时候，需要先将插入的节点 5 的祖父节点 3 进行左旋，然后再将节点 3 的祖父节点 7 右旋 ，最后得到一个平衡二叉树。重申一下平衡二叉树的原则：左右子树的高度之差不能大于 1。
删除节点
删除节点后，如果出现不平衡，则需要进行平衡调整。平衡调整逃不过 LL、RR、LR、RL 的情况，所以不管树出现了哪种不平衡，都可以通过左旋和右旋来使不平衡的二叉树变得平衡。
如果删除的节点 7 有左右节点，则选择「左子树-最大节点 6」或者「右子树-最小节点 8 」与被删除的节点交换，并移除交换后的节点。
如果左子树和右子树的高度不一致，通常选择高度较高的子树进行替换。此例子中选择了左子树的最大节点 6 与被删除的节点 7 进行了替换。
如果删除的节点 3 有左右节点，可以选择「左子树-最大节点」或者「右子树-最小节点 」
如果左右高度一致，比如删除节点 3，那么可以选择后继节点 6 与节点 3 替换后，删除节点 3。（选择节点 1 替换可以达到同样目的，理论上也是合理的）
删除节点 8 后，导致不平衡，则需要针对不同情况进行旋转操作，让不平衡转为平衡。
删除节点后的不平衡，也分为四种情况，这四种情况与插入一个新节点是一样的。可以理解成，删除一个节点导致不平衡，等于新插入一个节点导致不平衡。
上面的例子中，删除节点 8，相当于在节点 8 的父节点节点 7 的左子树插入新节点（不管是节点 1 还是节点 6 ）。同插入节点的左左 LL 的情形。所以进行一次右旋即可使树平衡。
总结
对于二叉查找树，如果高度过高，会导致二分查找效率变低，会从 O(logn) 甚至变成 O(n) 的复杂度。
所以我们需要将二叉查找树的高度降低，宽度变大，就成为了平衡二叉排序树。
平衡二叉树的任意节点的两个子树高度之差不能大于 1 。平衡二叉排序树继承了二叉查找树的规则。
平衡二叉树不一定是有序的，不过大部分的时候默认是平衡二叉排序树。平衡二叉树家族中，有另外一个耳熟能详的数据结构——红黑树。
标签:
