数据结构和平衡二叉树的讲解（数据结构与算法-二叉查找树平衡）

上节讨论的DSW算法可以从全局重新平衡树：每个节点都可能参与树的重新平衡，或者从节点中移除数据，或者重新设置指针的值。但是，当插入或删除元素时，将只影响树的一部分，此时树的重新平衡可以只在局部进行。局部平衡二叉查找树有一个鼎鼎大名的算法，叫做AVL算法，由AVL算法构建出来的二叉树称之为AVL树。

AVL树首先是一颗二叉查找树，其次，AVL树要求每个节点左右子树的高度差最大为1。例如，图1-1中的所有树都是AVL树。节点中的数字表示平衡因子，即左右子树的高度差。平衡因子等于右子树的高度减去左子树的高度。对于AVL树，所有的平衡因子都应是 1、0或-1。平衡AVL树的技术不保证得到的树是完全平衡的，但却是高度平衡的。有关平衡的概念可以参考数据结构与算法-二叉查找树平衡(DSW)。

假设我们已经有了一颗AVL树，那么如何保证在插入或者删除元素时继续保持AVL树的特性呢？

• 插入

前人对于AVL树的插入操作进行总结，发现一共有4种情况需要讨论。其中，在左子树中插入有两种情况，在右子树中插入也有两种情况。并且它们是对称的，因此，我们以右子树为例，只需要讨论两种情况即可。

假设我们在AVL树中插入一个新的节点p，那么p的父节点以及祖父节点的平衡因子都有可能改变，我们从下到上更新节点的平衡因子，如果发现某个节点的平衡因子成为 2或者-2，那么就以该节点为根截取这段子树。如果根节点平衡因子成为了 2，代表节点插入到了右子树中，如果根节点平衡因子成为了-2，代表节点插入到了左子树。我们这里只讨论 2，即节点插入到右子树上的两种情况。

如果节点平衡因子变成了 2，那么，我们可以将这颗子树抽象出来，它必然是下面这种样子：

也就是说，如果插入新节点使P节点的平衡因子成了 2，那么以P为根的子树，必然是上面的样子。插入的新节点要么放在Q的左子树上，要么放在Q的右子树上，这就是我们要讨论的两种情况。

1、RR

第一种情况有个简称，叫做RR，也就是说新节点插入到右子树的右节点，就像这样：

怎么处理呢？P节点的左子树比右子树低，还记得左旋的效果吗？左旋可以提高左子树的高度，降低右子树的高度，用在这里正合适。将Q节点围绕P节点进行左旋之后效果如下：

非常完美，左旋在这里产生了两个效果。首先，左旋使当前子树重新保持平衡，其次，左旋没有改变当前子树的高度。左旋之前子树高度为h 2，左旋之后依然是h 2。这就意味着，从Q节点开始往上的节点不需要更新平衡因子了。所以，左旋使得算法变得足够简单。

• RL

顾名思义，RL的意思是将新节点插入到右子树的左节点上，就像这样：

怎么处理呢？首先还是左旋，但是很快你会发现，左旋确实提高了左子树高度，但是太高了，又造成了新的不平衡，就像这样：

究其原因，是h 1那颗子树大大提高了左子树高度，我们必须把它放在右子树上才行，可以这样处理。首先，我们认为，如果是因为在P树的右子树的左节点上插入元素导致P节点不平衡，那么，在没有插入新节点之前，P树肯定是下面这种样子的：

Q的左子树插入了新的节点，可能插入到R的左子树或者右子树，先不管这个，为了降低Q的左子树的高度，将R围绕着Q进行右旋，结果是这样：

靠谱，R的左子树高度就是就是m1树的高度，既可能是h - 1，也可能是h，但是都比h 1要小，这时我们再做一次左旋，结果如下：

完美，R树最终平衡了，并且R树的高度依然保持在h 2，这也意味着不必更新R节点之上的祖先节点的平衡因子了。至于P和Q节点的平衡因子，这要看新节点是插入到m1树还是m2树上了，但是无论如何，R树都已经高度平衡了。

总结一下，对于RL形式的子树，首先对右子树的左节点做一次右旋，然后对新的根节点做一次左旋即可。

插入还有LL，LR两种形式，但是它们分别和RR，RL形式对称，这里就不多介绍了。

这里有个我看到的非常精辟的总结，引用一下：

下面介绍删除节点之后如何平衡二叉查找树。

• 删除

删除比插入更加复杂，但是有着插入节点积累的经验，理解删除反而更加容易。

删除节点首先面对的问题是平衡因子从哪个节点开始变化的？这就要说到二叉查找树的删除逻辑了，在数据结构与算法-二叉查找树中有着详细的介绍。这里简单介绍一下，删除叶子节点或者度为1的节点，平衡因子从被删除节点的父节点开始变化。删除度为2的节点需要使用复制删除的技巧，使用被删除节点的直接前驱或者直接后继来替换被删除节点，然后删除直接前驱或者直接后继，那么，平衡因子就是从直接前驱或者直接后继的父节点开始变化的。

既然知道了平衡因子开始变化的节点，就可以从下到上的更新平衡因子的变化。

在探讨插入节点引起的二叉树的变化时，我们总结出了RR、RL、LL、LR四种情况，删除节点会引起怎样的变化呢？

删除和插入有两个不同点：

1、删除不仅包含以上四中变化，还多出两种，当然这两种也是对称的

多出来的两种是当前节点的父节点的平衡因子等于 2或者-2时，当前节点的平衡因子等于0。

插入节点之所以没有这两种变化，是因为插入节点使当前节点平衡因子变成0，说明当前节点的高度没有变化，更加不会引起祖先节点的平衡因子变化了。而删除节点时，如果当前节点平衡因子变成0，那么当前节点的高度其实变小了，可能引起祖先节点的平衡因子变化。

怎么处理这种情况呢？如果父节点平衡因子等于 2，那就对当前节点进行左旋。如果父节点平衡因子等于-2，那就对当前节点进行右旋即可。

2、重新平衡过程没有在发现平衡因子为 2或者-2的第一个节点P后停止，而是追踪到根节点

在插入节点的重新平衡过程中，我们在意的是第一个平衡因子为 2或者-2的节点，原因在于我们执行左旋或者右旋之后，子树不仅重新平衡并且高度也和没有插入节点之前保持一致，因此，祖先节点的平衡因子就不会发生变化了。但是删除节点发生了变化，重新平衡之后子树的高度变小了。

为什么重新平衡之后，插入节点高度不变而删除节点高度变小呢？

可以思考下平衡的过程，假设平衡因子变化为 2的节点为P，它的左子树高度为h，右子树高度必然为h 1，只有在右子树插入新的节点，P节点的平衡因子才会变化为 2，重新平衡之后该树的左右子树高度为h 1，因此该树的高度h 2没有变化。但是对于删除又有不同，假设P节点左子树高度为h，右子树高度必然为h 1，只有在左子树删除节点之后，P节点的平衡因子才会变化为2，重新平衡之后该树的左右子树的高度为h，那么该树的高度h 1比原来就减少了1。因为上述原因，删除节点之后重新平衡的逻辑不能只执行一次，而是从平衡因子发生变化的节点开始往上一直追踪到根节点，发现不平衡的节点都要执行平衡逻辑。

到此为止，AVL树中添加和删除节点的逻辑已经探讨完毕。当然，这里纯粹是学术上的探讨，没有代码示例，更加精深的内容需要在实践中摸索。

知识的积累从来不是看了一两篇文章就可以完成的，毕竟，功夫在诗外。

数据结构与算法-二叉查找树平衡(DSW)

,