平衡二叉树之AVL树与红黑树

zhyjc6于2020-04-19发布 约6542字·约14分钟 本文总阅读量次

红黑树和AVL树都是二叉搜索树，说到二叉搜索树，就得先提二叉树，说到二叉树还得再说说树。下面就让我们来简单梳理一下从树到AVL树以及红黑树的过程吧！

树

树是一种数据结构，是用来模拟具有树状结构性质的数据集合。它是由 $n(n \ge 0)$ 个有限结点组成一个具有层次关系的集合。树具有以下特点：

术语

树的分类

二叉树

每个结点都至多只有两个子结点的树。

二叉搜索树

定义

二叉查找树（Binary Search Tree，BST），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛。

基本操作

查找

递归查找是否存在key。如果等于当前结点值，则查找终止，如果小于当前结点值，则在当前结点左子树中继续查找，否则在右子树中查找。

插入

原树中不存在key，插入key返回true，否则返回false。要插入结点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的结点也需要从根结点开始进行比较，小于根结点则与根结点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父结点的信息及待插入的位置是父结点的左子树还是右子树，才能插入到正确的位置。

构造

循环地作插入操作。

删除

删除结点是所有操作中最复杂的，待删除的结点分为以下三种情况：

复杂度

不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有 n 个元素，那么平均每次操作需要$O(logn)$的时间。

操作 平均 最差
空间 $O(n) $ $O(n)$
查找 $O(log n)$ $O(n)$
插入 $O(logn)$ $O(n)$
删除 $O(log n)$ $O(n)$

AVL树

AVL树首先是二叉搜索树，但是是改进的二叉查找树。改进的方法很简单，即添加条件：每个结点的左右子树的高度之差至多为1。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。

术语

基本操作

插入（insert）：在树中插入一个新值。

首先根据普通 BST 插入结点的方式插入结点，这可能会改变其祖先结点的平衡因子，使其绝对值大于1，这时候该树就不是 AVL 树了，因此我们需要做出调整。调整方式分为左旋和右旋两种。设最小不平衡子树的根结点为 root，左右旋的实现简单来说就是：

设插入结点后最小不平衡子树的根结点为root，根据插入结点位置可以分为以下四种情况：

删除（delete）：在树中删除一个值。

删除比插入还要复杂。首先按照普通 BST 删除的方式删除该结点，然后向根结点回溯判断其祖先结点是否平衡，如果父结点到根结点都平衡，那么删除完成；如果有祖先结点不平衡，那么就判断其是属于哪种失衡。设失衡结点为w，失衡结点的左右子树中高度较大的子树的根结点为x，x结点的左右子树中高度较大的子树的根结点为y，那么我们就可以通过w、x、y的相对位置来判断w是处于哪种失衡：

知道了具体的失衡原因，就根据插入结点的再平衡方法使其平衡。然后再从w结点向根结点回溯判断是否仍有不平衡结点，如果有，继续以上操作；否则说明已经平衡，删除完成。

查找

可以像普通二叉查找树一样的进行，所以耗费 $O(logn)$ 时间，因为 AVL 树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。

复杂度

操作 平均 最差
空间 $O(n)$ $O(n)$
搜索 $O(logn)$ $O(logn)$
插入 $O(log⁡n)$ $O(logn)$
删除 $O(logn)$ $O(logn)$

红黑树

和 AVL 树一样，红黑树也是二叉搜索树，具有一定的平衡性，但没有 AVL 树那么平衡。相对于二叉搜索树，红黑树附加了以下性质：

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

最长路径长度不可能大于最短路径的两倍。因为根结点和叶子结点都是黑色，而红色结点不能连续出现，因此最长路径是 黑红黑…红黑，交替出现（n个黑结点，n-1个红结点，路径长为2(n-1)），而最短路径是全是黑结点（n个黑结点，路径长为n-1）。

术语

基本操作

查找

同二叉搜索树

插入

首先进行普通的 BST 插入，设插入的结点为N，并将插入结点设为红色。然后再分类讨论：

注意：在情形四和情形五中，我们假定父结点P是其祖父G的左子结点。如果它是右子结点，情形4和情形5中的 左 和 右 应当对调。

  1. 情形一：如果N为根结点，那么将其改为黑色，插入完成！

    下面的情况 N都不为根结点。

  2. 情形二：如果N的父结点是黑色，那么不做任何操作，插入完成！

    下面的情况 N的父结点颜色都为红色。

  3. 情形三：如果N的父结点和叔叔结点都是红色，那么N的祖父结点一定是黑色。为了使红色的N合法，我们翻转父结点和叔叔结点为黑色，翻转祖父结点为红色。但是红色的祖父结点可能是根结点，这违反了性质2；也有可能祖父结点的父结点是红色，那么就出现了父子结点连续为红色，违反了性质4。要解决这个问题，我们把祖父结点当作新插入的结点递归地进行以上操作。

    下面的情况都是：N的父结点 P是红色而叔叔结点 U是黑色。

  4. 情形四：如果N的父结点P是红色而叔叔结点U是黑色，并且新结点N是其父结点P的右子结点而父结点又是其父结点的左子结点（左右）。在这种情形下，我们先进行一次左旋转调换新结点N和父结点P的角色；接着，我们按情形5处理以前的父结点以解决仍然失效的性质4。注意这个改变会导致某些路径通过它们以前不通过的新结点N（比如图中1号叶子结点）或不通过结点P（比如图中3号叶子结点），但由于这两个结点都是红色的，所以性质5仍有效。

  5. 情形五：如果N的父结点P是红色而叔叔结点U是黑色，并且新结点N是父结点P的左子结点，而父结点P又是其父结点G的左子结点（左左）。在这种情形下，我们进行针对祖父结点G的一次右旋转；在旋转产生的树中，以前的父结点P现在是新结点N和以前的祖父结点G的父结点。我们知道以前的祖父结点G是黑色，否则父结点P就不可能是红色（性质4）。我们切换以前的父结点P和祖父结点G的颜色，结果的树满足性质4。性质5也仍然保持满足，因为通过这三个结点中任何一个的所有路径以前都通过祖父结点G，现在它们都通过以前的父结点P。在各自的情形下，这都是三个结点中唯一的黑色结点。

    总结：总的来说就是先变色，变色的过程中不涉及旋转，如果变色不能解决问题，那么就使用旋转，但旋转的过程会涉及变色。

删除

同样，删除还是比插入更复杂。但是我们可以利用 AVL 的基础将其简化。

如果删除的结点有两个非叶子结点（NIL），那么问题可以转化为删除另一个只有一个非叶子儿子结点的问题。因为我们可以找到其直接前驱结点，仅仅交换两个结点的值但不改变两个结点颜色，这样我们就转换成只需要删除其直接前驱结点了。而其前驱结点是其左子树中的最大结点，最多只有一个非叶子的儿子结点。所以我们把问题化简了。

那么如何删除最多只有一个非叶子儿子结点的结点呢？

复杂度

一棵有 n 个内部结点的红黑树的高度至多为 $2log_2(n+1)$

设结点x的黑高(black-height)为bh(x)

证明：先证明以任一结点x为根的子树中至少包含 $2^{bh(x)}-1$ 个内部结点，要证明这一点，对x的高度进行归纳。如果x的高度为0，则x必为叶结点(NIL)，且以x为根结点的子树至少包含 $2^{bh(x)}-1=2^0-1=0$ 个内部结点。对于归纳步骤，考虑一个高度为正值且有两个子结点的内部结点x，每个子结点有黑高 $bh(x)$ 或 $bh(x)-1$ ，其分别取决于x的颜色是红是黑。由于x的子结点的高度比x本身的高度要低，可以利用归纳假设得出每个子结点至少有 $2^{bh(x)-1}-1$ 个内部结点的结论 。于是，以x为根结点的子树至少包含 $(2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1 = 2^{bh(x)}-1$ 个内部结点。

设红黑树的高度为h，那么从根结点到叶结点的任何一条简单路径上都至少有一半的结点为黑色，因此，跟的黑高至少为 $h/2$ ；于是有：$n \ge 2^{h/2}-1$，整理得：$h \le 2log_2(n+1)$

——《算法导论》

操作 平均 最差
空间 $O(n) $ $O(n)$
查找 $O(log n)$ $O(log n)$
插入 $O(logn)$ $O(log n)$
删除 $O(log n)$ $O(log n)$

红黑树还是AVL树？

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree.

参考资料