16.AVL 树和红黑树的实现和特性

1. 树的回顾

1.1 树 Tree

1.2 二叉树 Binary Tree

二叉树遍历：

前序（Pre-order）：根-左-右
中序（In-order）：左-根-右
后序（Post-order）：左-右-根

如果一颗树是二叉搜索树，那么它的中序就是有序的

示例代码

def preorder(self, root):
  if root:
    self.traverse_path.append(root.val)
    self.preorder(root.left)
    self.preorder(root.right)

def inorder(self, root):
  if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)

def postorder(self, root):
  if root:
    self.postorder(root.left)
    self.postorder(root.right)
    self.traverse_path.append(root.val)

1.3 二叉搜索树 Binary Search Tree

二叉搜索树，也称二叉搜索树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是指一颗空树或者具有下列性质的二叉树：

左子树上所有结点的值均小于它的根结点的值；
右子树上所有结点的值均大于它的根结点的值；
以此类推，左、右子树也分别为二叉查找树（这就是重复性！）

中序遍历：升序排列

树和链表没有本质上的区别，当一个链表的话，当它分出两个 next 的话，我们就把它称为树，所以它的数据结构就是从一维空间扩散到二维空间了，这种扩散的好处就是引入了二叉搜索树。当它本身是有序的话，那么每一次的话就可以根据它和当前结点的大小关系分出来它只走左分支还是只走右分支，这样的话查询插入和搜索的效率就从 O(n)的变成了 log2n 的时间复杂度。

如何查找结点
假设我们要查找 10，首先来和根相比，如果是小于 9 的话，只要去左子树就行了，10 是大于 9 的，那就去右子树，10 是小于 13 的就去左子树，10 是小于 11 的再去左子树就找到 10 了，而找不到的话也就是找不到。这时候你会发现查找的时间复杂度就是这个树的深度。如何这个树本身有 n 层的话，那么它的时间复杂度是 n，但是一般我们定义 n 为树的总的结点个数，这个时候它的时间复杂度平均来说就是 log2n，这里的 n 表示树里面总的结点个数。

极端情况
基于上面介绍可能会出现一种极端情况，这种极端情况的话就是在你维护二叉搜索树的时候，没有特殊处理的话，在极端情况下它会变成一根棍子，这根棍子的话就是你在插入的时候始终插在左边，这个时候二叉搜索树就退化成一个链表了。

2. AVL 树

2.1 保证性能的关键

基于上面的极端情况，所以要保证性能的关键就是保证二维的维度，也就是左右子树高度尽量平衡的，且左右子树以此类推下去都尽量平衡的，所以这里引入了一个叫做平衡二叉树这样的一个概念。

保证二维维度！ —> 左右子树结点平衡（recursively）
Balanced
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

平衡二叉树有很多很多种，在面试的时候一般喜欢出 AVL 和红黑树，以及比如说 treap，以及 splay 叫伸展树，以及后面还会有 B+树，主要子啊数据库的索引结构里面用到，。

2.2 思考：如何平衡？

大家可以首先构思一下，这颗树应该怎么平衡，这个树的平衡相对比较简单，粗略来看把 6 或者 7 挪到最上面去，也就是你可以想象成这根根子的话，直接从 6 或 7 结点开始打折了，然后变成 34567、8912，这是第一步，第一步做完之后相应的每个左右子树也类似地这么做下去，最后整个树变得平衡。

但一般来说，我们不会等到在真正的自平衡二叉树里面（AVL 和红黑树里面），不会等到这个树以及病入膏肓了，就是已经变成很极端的这根棍子的时候，再去平衡。而是在每一步进行插入或者删除操作的时候，都去判断它是否平衡，以及将它维护成平衡二叉树的状态。

2.3 AVL 树概述

发明者 G.M.Adelson-Velsky 和 Evgenii Landis
Balance Factor (平衡因子)：是它的左子树高度减去它右子树的高度（有时相反）。balance factor = {-1, 0, 1}
通过旋转操作来进行平衡（四种）
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

平衡因子{-1, 0, 1}表示它的左子树的高度减去它右子树的高度，当然也可以从右子树的高度减去左子树的高度，这里注意的是是树的高度，并不少结点个数，因为查询二叉搜索树效率只与高度有关。这里取值的高度就只有-1、0、1。

2.4 记录左右子树高度

那么我们来看关于 j 这个结点，也就是根节点，它的左子树高度是 3，右子树高度是 4，所以它的平衡因子就是右子树高度 4 减去左子树高度 3，所以它就是正 1。另外 F 这个结点，右子树高度是 1，左边子树高度是 2，1 减去 2 就是-1。G 结点就是 0。D 就 0 再减 1 就是-1。所有叶子结点可以发现，只要是叶子结点，因为它没有左右子树，所以它的高度就是 0。所以下图这棵树是一个严格意义上平衡的 AVL 树，也就是它的平衡因子值在{-1, 0, 1}之间,所以保持平衡因子不超过绝对值 1，就变成来一颗二叉搜索树。

练习：

1. 插入 14

首先会找 14 比 13 大，所以要去右边，14 又比 15 小，所以要去左边，也就是插入位置，接下来再调整平衡因子。如下图：

2. 插入 3

接下来我们看要增加 3 的话应该怎么办？应该直接走到左边，做到 4 左下，这里就插入 3 了，3 插入的时候，这时候糟糕又两个结点它的平衡因子不再 1 的范围了，变成-2 了。

2.5 旋转操作

基于上面提到的问题，接下来我们就会进行一种旋转的操作，这个旋转操作总共分为四种基础的旋转操作，我们先介绍四种基础的旋转操作之后，那么怎么来旋转大家就比较明白了。

左旋
右旋
左右旋
右左旋

子树形态：右右子树 —> 左旋

子树形态：左左子树 —> 右旋

子树形态：左右子树 —> 左右旋

这种情况就是说它是先左子树再右子树，A 这里的平衡因子变成了-2，基于这种先左子树再右子树的情况的话，我们就叫做左右子树型。左右子树型就要左右旋转。

首先 A 结点左旋一次，注意 C 是大于 B，C 是小于 A，所以它左旋的话，B 就拉下来 C 顶上去，这样的话它还是一个符合二叉树性质的，因为 B 是小于 C 的。

但是这样子你会发现，上面的情形就变成我们左左子树的情况，然后就再加上一次右旋就行了。所有它叫做左右旋转。

子树形态：右左子树 —> 右左旋

最后这种就是和上面对称的这种情况叫做右左子树的情况。

右左子树的情况，先是一次右旋，注意这里的 C 是小于 B 的，所以把它右旋上去的话，C 顶上去 B 就拉下来，这样子还是满足二叉搜索树的性质。

然后就变成右右子树的情况，再进行一次左旋操作，所以总的就是右左旋转，这个问题就解决了。

2.6 带有子树的旋转

有时候这个结点本身右所谓的子树情况，它要进行左右旋和右左旋应该怎么办？
这个时候要进行右旋操作的时候，E 结点移上来，S 结点往下拿了之后，E 的右子树要挂在 S 的左子树下去。

我们通过两个动画来加深理解：参考动画: https://zhuanlan.zhihu.com/p/63272157

右旋

左旋

上面它整个旋转和观察树的形态本身，是较为繁琐的，但其实代码来说的话也是相对来说比较对称的，本身的话代码量的确比起普通二叉搜索树要大或者是要大一截，但是它整个情况的话就这四种。所以在面试的时候就把它这四种情况都给面试官在这里列清楚了，那么你对 AVL 整个思路是完全掌握的，当然的话你也要给他解释为上面会出来 AVL，以及这个平衡因子是怎么定的？平衡因子定的由来就是因为它的查询的时间复杂度是等于树的深度的，所以的话它就会记录深度差，就得到平衡因子，平衡因子不平衡的就要去做旋转操作，就会变成这四种基础的旋转。

练习

1.插入 3

我们再回到上面插入 3 之后的问题，这颗树现在的形态就变成这个样子了，也就是 左左型，所以就要就行右旋操作。

5 挪上去 10 挪下来，8 挂在 10 的左下，如下：

2.插入 15

15 最终插入在 16 的左子树下，你就会发现这个地方 2,2 都不平衡了，它是一个典型的右左子树的情况，如下：

右左子树就要先进行所谓的右旋操作，如下：

之后再进行左旋操作，如下：

2.7 AVL 总结

AVL 是平衡二叉搜索树
每个结点存 balance factor = {-1, 0, 1}
四种旋转操作

不足：结点需要存储额外信息、且调整次数频繁。

3. 红黑树（Red-Black-Tree）

红黑树是一种近似平衡的二叉搜索树（Binary Search Tree），它能够确保任何一个结点的左右子树的高度差不小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：

根结点是黑色
每个结点要么是红色，要么是黑色
每个叶子结点（NIL 结点，空结点）是黑色的
不能有相邻的两个红色结点
从任意结点到其每个叶子结点的所有路径都包含相同数码的黑色结点。

这个性质就可以证明在这种近似平衡的状态下，它的时间复杂度还是平均来说很好的 logn 的时间复杂度。它不会进行所谓的退化，而它所需要调整的时间也是折中之后相对比较小的调整时间。

那么其他还有一种这样的一个泛化形式的，就是得到这样一个回溯它也是可以的

关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

4. 对比

AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.

AVL树的话提供了更快的 lookups（查询），比红黑树来说的话，它AVL优秀的地方是更快的 lookups。因为它是更加严格平衡的二叉搜索树，也就是说读或者是查找性能来说的话，AVL更好。

Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.

红黑树提供来更快的插入和删除的操作，因为AVL的旋转操作会更多，那么红黑树的话会更少一点，因为红黑树是一个近似平衡二叉搜索树。所以添加和删除操作的话我们认为红黑树更快。

AVL trees store balance factors or heights with each node, thus requires storage for an integer per node whereas Red Black Tree requires only 1 bit of information per node.

AVL要存额外的信息，它要存factor和height更多一点，它需要用更多的内存，附加在每个结点里面来存这些额外的信息，而红黑树要的信息非常少，它只要一个bit就来存0和1表示黑色或者红色，所以它对额外空间的消耗更小，有些同学可能会问了，这就是一个int怕什么？其实不是这样的，树的话有时候可能也会有上万个结点或者它本身性能要有差别的话，结点个数肯定是很多的情况下，如果结点个数很少的情况下，就比如说一万以内，你随便怎么用树都可以。你稍微不平衡或者不平衡多一点，其实差异不大的，真正在要追求的话，而且这些很多都是在数据库和数据仓库里面使用。所以的话就在于那个数据至少是百万和千万以上的时候，这时候的话它每个结点都加一个int的话，其实并不少一个最佳的旋转。而在这里红黑树你只要一个bit会更好。

Red Black Trees are used in most of the language libraries like map, multimap,multisetin C++ whereas AVL trees are used in databases where faster retrievals are required.

比较什么时候用红黑树，根据前面三点可以看到，如果在读操作非常非常多，写操作比较少的情况下就用AVL就好了。AVL的问题就是插入删除调整的比较繁琐，但它的好处是非常平衡，查询快。如果是插入操作比较多的话，或者插入操作和查询操作一半一半的话，一般来说是用红黑树。因为红黑树的话比较简洁比较好实现。那么一般来说红黑树是用在我们常常写的一些高级语言的库里面，比如说大家写java或者C++的那些Map、Set全部用的是红黑树。而在DB里面，一般来说DB的话读会比较多，写会比较少，举个例子：大家天天刷微博或者看朋友圈，你是读得多还是写多，除非你是超级大V，一般来说肯定是读得多。这样的话Database里面一般是用AVL。

部分图片来源于网络，版权归原作者，侵删。