【数据结构】二叉搜索树、平衡搜索树、红黑树

二叉搜索树（Binary Search Tree）

二叉搜索树是一种特殊的二叉树，它用来快速搜索某个值，对于每个节点都应该满足以下条件：

1. 若该节点有左子树，那么左子树中所有节点的值都应该小于该节点的值。
2. 若该节点有右子树，那么右子树中所有节点的值都应该大于该节点的值。
3. 左右子树都应该是二叉搜索树。
   根据条件三可以确定，二叉搜索树是通过递归定义的。
   并且我们可以得到以下结论：左子树节点值 < 根节点值 < 右子树节点值。
   所以二叉搜索树的中序遍历是一个升序的序列。
   但是我们构建二叉搜索树的目的不是为了排序，是为了高效地查询、插入、删除元素。

二叉搜索树示例图：

查找操作

查找操作就是从根节点开始，沿某个路径一直向下搜索的过程。要查找的值比当前节点值小就往当前节点的左子树查找；要查找的值比当前节点值大就往当前节点的右子树查找。直到找到要查找的值为止。
当节点分布均匀时，时间复杂度一般为树的高度O(logn)；
但是最坏情况下节点会退化成链表，所以时间复杂度为O(n)。

插入操作

将一个元素插入到树中，是从根节点开始，与当前节点相比较，如果比当前节点的值小，就进入该节点的左子树；如果比当前节点的值大，就进入该节点的右子树。直到遇到一个空节点，就可以将要插入的节点安放在这个空节点的位置。所以插入的节点一定是一个新添加的叶子节点。并且在二叉搜索树中，通常不允许存储重复的值。
同查询操作一样，时间复杂度为O(n)。

删除操作

删除操作分为三种情况：

1. 当要删除的节点为叶子节点的时候，直接删除。
2. 当要删除的节点有左子树或者右子树的时候，删除该节点，用该节点的子节点代替该节点。
3. 当要删除的节点既有左子树又有右子树的时候，有两种方法，但是目的都是将情况变成第一种或者第二种。
   3.1 找到该节点的直接前驱(该节点左子树中的最大值)来代替该节点，然后针对这个直接前驱完成情况二节点的删除。
   3.2 找到该节点的直接后继(该节点右子树中的最小值)来代替该节点，然后针对这个直接后继完成情况二节点的删除。

解释：
节点 x 的直接前驱：在中序遍历中，x 的前驱。在 x 的左子树的最右下节点（该节点一定没有右子树）。对于“该节点一定没有右子树”的解释：因为该节点如果有右子树，那么说明有比该节点还大的节点，那么该节点就不是 x 的直接前驱了。
节点 x 的直接后继：在中序遍历中，x 的后继。在 x 的右子树的最左下节点（该节点一定没有左子树）

演示第三种删除：

给出一个二叉搜索树，如下图所示，现要删除节点20

那么根据第三种情况，我们要先找到节点20的直接前驱（17）或者直接后继（25），然后将这个直接前驱或者直接后继复制一份，替换掉根节点。

此时我们再将原来的那个直接前驱或者直接后继删除掉即可，这时候删除它就变成了情况1或者情况2
如果选择3.1，删除17就是情况1，删除叶子节点直接删掉即可；
如果选择3.2，删除25就是情况2，用节点26代替节点25即可。

Q：可能此时就有人有疑问，难道就不会出现要删除的直接前驱或者直接后继既有左子树，又有右子树？
A：这时不可能的，直接前驱要是还有右子树，那他就不是直接前驱。根据BST定义可知一个节点的右子树的值肯定要比该节点大。所以直接前驱时没有右子树的。

我们继续以方式3.2为例演示

将25删掉之后，将26放在25的位置上。切不可放到28的右子树上去了。

这样就完成了节点20的删除。

平衡二叉树（AVL树）

我们知道，在二叉搜索树中，对于一个有序度很高的序列甚至是一个有序数列，我们在利用这个序列建二叉搜索树的时候，树会退化成一个链表，这样一来各种操作的时间复杂度将会变得很高。那么如何解决这种情况呢？我们引入了AVL树的概念，AVL树是一种自平衡的二叉搜索树，那么如何实现这个自平衡呢，就让我们接着学习。

基本概念

为保证二叉搜索树的性能，在插入、删除节点时规定，任意节点的左右子树高度差不超过 1 ，这样的二叉搜索树被称为AVL树。

左右子树的高度差被称为平衡因子（BF），BF = 左子树高度 - 右子树高度，取值范围为[-1,0,1]。

查找操作

查找原理同二叉搜索树一样，从根节点开始向下查找。时间复杂度为O(logn)（比BST更稳定）

插入操作

我们先按照二叉搜索树的算法插入一个节点，那么在途径的所有节点的平衡因子都可能会受到影响，它们的BF的绝对值可能变得大于1了，此时就应该想办法调整这棵树的结构，让它重新变成平衡二叉树。
那么如何调整呢，从哪里开始调整呢？我们要先认识一个基本概念两个基本操作。

一个基本概念两个基本操作

基本概念：最小不平衡子树。
在插入一个新节点之后，可能会造成很多节点的BF绝对值都大于1，此时我们应该找到距离新插入的节点最近的不平衡的点（BF绝对值大于1的点），以这个点为根的子树就是最小不平衡子树。
我们要调整的地方就是在最小不平衡子树处，仅需让最小不平衡子树平衡，整棵树就平衡了。为了简写，下文中称最小不平衡子树的根节点为T。

基本操作：左旋、右旋。
这两个操作都是对于T进行的，T对于T的右子树左旋、T对于T的左子树右旋。

首先来看一种简单的左旋：
7是最小不平衡子树的根节点T，现在要对T绕12进行左旋，我们可以很直观的看到左旋之后降低了T的右子树高度，使T的BF变成了0，那为什么左旋之后仍然符合二叉搜索树的要求（左子树<根节点<右子树）呢？注意理解这个地方！节点7是从12的左父亲旋转到左孩子的，不管它是父亲还是孩子，它都在12的左边，这里强调的是一种相对关系，在下面我们会举例更复杂的左旋，在旋转时，处理两个不相邻的节点时，需要关注它们的相对关系。旋转操作不仅涉及父子节点的转换，还需要考虑整个子树的结构平衡。

铺垫完了现在我们来看一种复杂的左旋：

这是一颗平衡二叉树，没有出现失衡。

当我们插入一个节点18，它会按照插入算法被安放在节点15的右孩子的位置。
这时，这个二叉树出现失衡。节点5是T节点。由于插入的新节点的位置是在T的右孩子的右子树中，属于RR型插入，需要左旋T节点来保持平衡。
这时候我们将T绕10左旋转的时候会发现，10的左边有个孩子挡住了我们的旋转，此时怎么办呢？
我们在上文中说过，要以基本原则来思考，一个节点的右子树的所有节点都是比它大的。那么可以将6放在5的右孩子上，也不破坏原本的二叉搜索树结构。让T的右孩子的左子树变成T的右子树。

于是我们得到了这个重新平衡的AVL树：

讲完基本操作，下面我们来看四种插入类型以及对应的自平衡调整方式。

AVL 树的插入与四种旋转（LL, RR, LR, RL）

在 AVL 树 中，插入新节点后，可能会导致某些节点的 平衡因子（BF） 超出 [-1, 0, 1] 的范围，这时需要针对 最小不平衡子树的根节点T 进行 旋转 来恢复平衡。 新节点不同的插入方式对应的旋转方式也是不一样的。

1. LL型
   插入方式：新节点插入在T的左孩子的左子树上，所以被称为LL型插入。
   调整方式：右旋T节点。
2. RR型
   插入方式：新节点插入在T的右孩子的右子树上。
   调整方式：左旋T节点。
3. LR型
   插入方式：新节点插入在T的左孩子的右子树上。
   调整方式：左旋孩子节点，再右旋T节点。
4. RL型
   插入方式：新节点插入在T的右孩子的左子树上。
   调整方式：右旋孩子节点，再左旋T节点。

练习：构建以下序列的AVL树：10 6 18 12 13 8 20 17 28

删除操作

同插入操作一样，删除操作也是先通过二叉搜索树的删除算法删除一个节点e，然后就要从这个节点e开始向上找到第一个不平衡的节点T，于是就要对这个节点进行调整。
如何调整呢？我们首先要找到以这个T节点为根的子树中最高的儿孙节点，根据孙子节点相对于儿子节点的位置，判断属于哪种类型（LL、RR、LR、RL），然后对这个T进行调整。调整完了T之后，要继续向上寻找不平衡的点继续调整。

为什么插入操作只用调整一次，而删除操作调整完一次之后还要继续查找不平衡的点？因为插入操作是要在固定的位置插入的，这个位置取决于值的大小，而删除操作是在任意位置删除一个节点，那么任意删除的这个节点很可能就影响到了其他很多个节点的平衡，所以要向上挨着调整。

如何寻找最高的儿孙节点？如下图所示，假设T为最小不平衡子树根节点，我们需要在T的左右子树中寻找较高的那个子树，较高子树的根节点就是最高儿子节点。然后我们继续在最高儿子节点的左右子树中寻找较高的那个子树，此时这个子树的根节点就是最高孙子节点。

注：黄色节点为最高儿子节点，绿色节点为最高孙子节点。

红黑树（RBT）

基本概念

红黑树是在二叉搜索树的基础上，在每个节点中增加了一个储存节点颜色的信息位，同过对任意一条从根到叶子节点路径上的各个节点的着色限制，确保没有一条路径比其他的路径长出两倍。这样一来就保证了二叉搜索树的相对平衡，不会出现极端情况。这就是红黑树。

RBT的规则

注意：在RBT中我们所说的叶子节点（NIL节点）与正常的二叉树中的叶子节点（Leaf Node）是有区别的，RBT的叶子节点是指空节点
1.每个节点要么是红色要么是黑色
2.根节点或者叶子节点必须是黑色
3.红色节点的两个孩子必须都是黑色节点，就是说不会有两个相连的红色节点
4.对于任意一个节点，这个节点到其所有叶子节点的路径上，每条路径上的黑色节点的数量必须是相同的

RBT的性质

1.最长路径不会超过最短路径的两倍。

最短路径：全由黑色节点组成，设其长度为 b。
最长路径：红黑节点交替出现，由于红色节点不能连续，最长路径的黑色节点数也为 b，红色节点数最多为 b-1，因此最长路径长度为 2b-1。
所以最长路径不会超过最短路径的两倍。

2.有n个节点的红黑树，树的高度 h <= 2log2(n + 1)

由这个性质可以得到，在RBT中的查询、插入、删除操作时间复杂度都是O(logn)。

2. 1黑高度的定义

黑高度（black-height）是指从某个节点到叶子节点的路径上的黑色节点数量（不包括该节点本身）。根据性质5，所有路径的黑高度相同。

2.2 红黑树的高度与黑高度的关系

设红黑树的黑高度为 bh，则树的高度 h 满足：h <= 2 * bh
这是因为红节点不能连续出现，路径上的红色节点数量最多与黑色节点数量相等。

2.3 节点数量与黑高度的关系

对于黑高度为 bh 的红黑树，节点数量 n 满足：n >= 2^bh - 1

这是因为黑高度为 bh 的树至少是一个完全二叉树，节点数量为 2^bh - 1。

2.4 推导高度与节点数量的关系

由 n >= 2^bh - 1，可得：bh <= log2(n + 1)
结合 h <= 2 * bh，得到：h <= 2 * log2(n + 1)

查找操作

原理同二叉搜索树的查找操作
由于红黑树的高度 h <= 2 * log2(n + 1)，查找操作的时间复杂度为 O(log n)。

插入操作

新节点颜色

插入操作的原理也是按照二叉搜索树的算法插入元素，但是这个插入的新节点应该是什么颜色呢？
很明显新节点设置为红色会更好。
如果新节点设置为黑色，那么在插入一个新节点的时候，他一定会使从根节点到叶子结点这条路径上的黑色节点数目变多，那么每次插入都需要重新调整这条路径上的黑色节点数目，这样很麻烦。
如果新节点颜色设置为红色，那么只可能违反两个红色节点不相连或者根节点不能为红色这两个原则，这两个调整起来很简单，并且有可能在插入新节点的时候并不破坏树的结构。

插入后调整方式

插入的节点是根节点

只需要将新节点的颜色由红色设置为黑色即可。

新节点的叔叔节点是红色

这种情况不需要旋转操作，此时要将父亲、叔叔、爷爷节点全部改变颜色。并且将改变后的爷爷节点当作新插入的节点继续向上判断直至RBT树平衡。

叔叔节点是黑色

这时候需要看新节点和爷爷节点的位置关系，通过旋转 + 变色来调整，分四种情况：

1. LL型
   新节点是爷爷节点的左孩子的左孩子
   调整方式：右旋父亲节点 + 父爷变色
2. RR型
   新节点是爷爷节点的右孩子的右孩子
   调整方式：左旋父亲节点 + 父爷变色
3. LR型
   新节点是爷爷节点的左孩子的右孩子
   调整方式：先左旋孩子节点，再右旋父亲节点 + 儿爷变色
4. RL型
   新节点是爷爷节点的右孩子的左孩子
   调整方式：先右旋孩子节点，再左旋父亲节点 + 儿爷变色