为什么要有红黑树?

从理论上来说，二叉搜索树的查询、插入和删除一个节点的时间复杂度均为O（log(n)）,已经完全可以满足我们的要求了，那么为什么还要有红黑树呢？
我们来看一个例子，向二叉搜索树中依次插入（1，2，3，4，5，6），插入之后是这样的.

二叉搜索树退化成了链表！！！这时候查询、插入和删除一个元素的时候，时间复杂度变成了O（n），
显然这是不能接受的。出现这种情况情况的原因是二叉搜索树没有自平衡的机制，
所以就有了平衡二叉树的概念。
RBTree-1.png

平衡二叉树（Balanced Binary Tree）具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
还是刚刚的例子，假如我们用平衡二叉树来实现的话，插入完元素后应该是下面这样的（不唯一）
RBTree-2.png

平衡二叉树保证了在最差的情况下，二叉树依然能够保持绝对的平衡，即左右两个子树的高度差的绝对值不超过1。但是这又会带来一个问题，那就是平衡二叉树的定义过于严格，导致每次插入或者删除一个元素之后，都要去维护二叉树整体的平衡，这样产生额外的代价又太大了。

二叉搜索树可能退化成链表，而平衡二叉树维护平衡的代价开销又太大了，那怎么办呢？
这就要谈到“中庸之道”的智慧了。说白了就是把平衡的定义适当放宽，不那么严格，这样二叉树既不会退化成链表，维护平衡的开销也可以接受。这时候这使用红黑树

什么是红黑树?

红黑树的定义与性质

**
红黑树是一种含 红黑节点并能自平衡的二叉搜索树. 它满足下面5个性质

  1. 每个节点要么是黑色, 要么是红色
  2. 根节点一定是黑色
  3. 每个叶子节点(NIL)是黑色
  4. 每个红色节点的两个子节点一定都是黑色.(即红色节点不会相连)
  5. 任意一节点到每个叶子节点的路径都包含相同数量的黑节点

演示的网址:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

1301290-20190418213125801-537737111.jpg
1.为什么要有红色节点?
如果只有黑色节点的话, 就只是一颗普通的黑树(二叉搜索树), 引入红色节点, 是为引起树的变化

2.为什么根节点一定是黑色?
因为麻烦。
假设你有一个红色的根节点，现在，你要加入一个新的节点，按照要求，这个节点必须是黑色的，
因为不能有连续的红色，然后，会变成下图这样
image.png
但是这个时候它又不符合第5条限定，每条路径上的黑色节点的数量必须是一样的。
左边的路径黑色的节点数量为1，右边的路径黑色节点数量为2.
这个时候，唯一能做的就是进行变色或者旋转，把根节点变成黑色的，把子节点变成红色的。如下图
image.png
既然加入第二个节点后就会必须要把根节点变成黑色的，那为什么不一开始就要求根节点是黑色的。

3.为什么红色节点的子节点一定是黑色 ?
红色节点的子节点一定是黑色, 即红色节点不能连续
这是为了保证树的平衡，保证最长的路径最多是最短路径的的两倍

想象一下，如果没有这条定义即红色节点能够连续的话是怎么样 ,
那下面这颗树是满足其他所以定义, 但是达不到自平衡的需求
image.png

而只要引入红色节点不能的连续的规矩, 整个树的结构就能自己发生变化了. 如下图
image.png

如何实现红黑树?

实现红黑树最重要是如何让红黑树的自平衡, 先了解相关的概念和名词

节点相关概念

当前新增节点 C -Current
兄弟节点 B -Brother
父亲节点 P -Parents
祖父节点 G **-Grandfather
叔叔节点 U -Uncle
根节点 R** - Root
红黑树的自平衡每次只考虑CPGU三代即可, 其他部分无需考虑
image.png

自平衡

红黑树自平衡包括: 变色和旋转, 其中旋转又可以分为 左旋 和 右旋. 旋转要有圆心, 有方向
旋转节点围绕子节点旋转(子节点为圆心)
image.png

左旋

旋转节点绕圆心逆时针方向, 基于最短路劲来确定方向旋转节点围绕子节点旋转(子节点为圆心)
image.png

右旋

旋转节点绕圆心顺时针方向, 基于最短路劲来确定方向旋转节点围绕子节点旋转(子节点为圆心)

image.png

红黑树的新增操作

红黑树 - 图12各种情况具体对应操作

情况1: C == root :::info 1.新增C当前节点, 默认为红色
2.修改C当前节点颜色为黑色 :::

情况2: C.parent == balck :::warning 新增节点C, 颜色为红色 :::

情况3: C.parent ==red && C.uncle == red :::success 1.新增C当前节点, 默认为红色
2.P父节点变成黑色
3.U叔叔节点变成黑色
4.G祖父节点变成红色
5.[如果祖父节点变红导致不满足红黑树性质]
将祖父节点作为新增节点C 递归处理[12345情况处理] :::

情况4: C.parent == red && C.uncle != red && C.parent < C :::info 插入节点是其父的右子节点:
1.变色P节点和G节点
2.以P节点为圆心, G节点为旋转节点,做左旋操作 :::

情况5: C.parent == red && C.uncle != red && C.parent > C :::danger 插入节点是其父的左子节点
1.以当前节点为圆心, 其父节点为旋转节点, 做右旋操作
2.旋转后, 置父节点为当前节点, 这时变成了情况4, 再处理一遍情况4 :::

以一个空树为例, 依次插入1-2-3-5-4, 对应的情况是1-2-4-3-5
一个空树插入1, 对应情况1, 没有父节点

默认插入为红色, 将其修改为黑色

image.png

插入2, 对应情况2, 父节点是黑色

不用做任何操作

image.png

插入3, 对应情况4, 父节点是红色, 无叔节点, 且是右子节点;

1.变色P节点和G节点 2.以P节点为圆心, G节点为旋转节点,做左旋操作

image.png

插入5, 对应情况3, 父节点是红色, 叔节点也是红色

1.新增C当前节点, 默认为红色 2.GPU变色, 变色后002是红色导致, 将002当作新增节点进行递归处理
3.这是符合情况1, 没有父节点, 将002红色改成黑色

image.png

插入4, 对应情况5, 父节点是红色, 无叔节点,且是左子节点

1.以当前节点为圆心, 其父节点为旋转节点, 做右旋操作 2.旋转后, 置父节点为当前节点, 这时变成了情况4, 再处理一遍情况4

image.png

红黑树的删除操作

删除的操作,从本质上讲就是一个穷举的过程
红黑树中删除一个节点，遇到的各种情形就是其子节点的状态和颜色的组合，
子节点状态共有3种：无子节点、有一个子节点、有两个子节点，
颜色有红色和黑色两种，所以共会有6种组合。

接下来逐一分析： 红黑树 - 图18组合3:** **只有一个子节点且本身是红色
这是一种不可能的情况，此时不符合性质5, 如图.
image.png

组合4: 只有一个子节点且本身是黑色
这种情况这个子节点一定是红色, 此时直接删掉node, 用子节点代替node位置, 并将value着黑即可.
image.png

组合5&6: 被删节点有2个子节点, 且被删节点为黑色或红色
当被删结点node有两个子结点时，我们先找到这个被删结点的后继结点successor(前驱节点也可以)，
然后用successor替换node的值，不用改变颜色，此时转换为删除node的后继节点successor。

这里使用node的后继节点替换node，必然是下图两种形态中的一种:
image.png
若是(a)的情形，用successor代替node后，转换为successor被删，
若successor为红色，则变成了组合1；
若successor为黑色，则变成了组合2。

若是(b)的情形，用successor代替node后，转换为successor被删，
若successor为红色，则变成了组合1（组合3是不可能的）；
若successor为黑色，则变成了组合2或4。

组合2：被删结点无子结点，且被删结点为黑色
因为删除黑色结点会破坏红黑树的性质5，所以为了不破坏性质5，将node删除后用一个拥有额外黑色的null替代它（可以想象是将node删除后，在这个位置放了一个黑色的权值），剩下的就是调平的过程，最终这个游离的黑色权值被扔掉，整个删除操作完成。
image.png

然后再结合node的父结点P 和其兄弟结点B 来分析。
情形一：brother为黑色，且brother有一个与其方向一致的红色子结点son
image.png
图(c )中，白色代表随便是黑或是红，方形结点存储的是一个游离的黑色权值。
将brother和father旋转（是左旋还是右旋自己根据情景体会，下同），并重新上色后，变成了图(d)，
将游离的黑色权值扔掉，此时不违背任何红黑树的性质，删除操作完成。
图(c )中的情形颠倒过来，也是一样的操作。

情形二：brother为黑色，且brother有一个与其方向不一致的红色子结点son
image.png
图(e)中，将son和brother旋转，重新上色后，变成了图(f)，转化为情形一。
图(e)中的情形颠倒过来，也是一样的操作。

情形三：brother为黑色，且brother无红色子结点
此时若father为红，则重新着色即可，删除操作完成。如图下图(g)和(h)
image.png
此时若father为黑，则重新着色，将游离的黑色权值存到father（此时father的黑色权重为2），
将father作为新的结点进行情形判断，遇到情形一、情形二，则进行相应的调整，完成删除操作；
如果没有，则结点一直上溯，直到根结点存储额外的黑色，此时将该额外的黑色扔掉，即完成了删除操作。

image.png

注意： 这里第二种情况有点不好理解，之所以要加一个游离的黑色是因为删除node后造成node子树和brother子树的黑节点个数不平衡，这里的操作实际是将brother子树中黑节点个数减少一个，而将father黑色权重设为2，
这样father左右两边的子树不用加游离的权值都是平衡的了。接下来将问题转移到了father、father的father、father的brother三个之间，这样向上递归，如果一直是这种情况，最终必定转化为root的左子节点或者右子节点权重为2，同样的将root黑色权重设为2，将另外一边的黑色权重减小1，再将root的黑色权重扔掉一个，此时整棵树重回平衡，只是root到叶节点路径的黑节点少了一个。

情形四：brother为红色，则father必为黑色。
image.png

图(i)中，将brother和father旋转，重新上色后，变成了图(j)，新的brother（原来的son）变成了黑色，这样就成了情形一、二、三中的一种。如果将son和brother旋转，无论怎么重新上色，都会破坏红黑树的性质4或5，例如图(k)。 图(i)中的情形颠倒过来，也是一样的操作。

image.png

至此，所有情形都以分析完毕，总的来说，我们要处理的是3种组合、7种情形，其中很多过程都是目标转移的过程，最终转移到可以通过旋转和变色达到平衡的节点或者转移到root节点，使红黑树重回平衡。