红黑树其实就是一种自平衡的二叉查找树，因此在了解红黑树之前，先来看下二叉查找树的原理

---

1. 二叉查找树

那么何为二叉查找树呢？其实是将二分查找的思想给结合到树的结构中来，二叉查找树只有左子树和右子树。具有以下三个特性:

1. 左子树上面的所有节点的值都小于它的根节点的值
2. 右子树上面的所有节点的值都大于它的根节点的值
3. 左子树和右子树也满足1和2两个特性

二叉查找树采用二分查找，在树结构平衡的情况下查找效率比较高，时间复杂度为O(logn),但是一般情况下都不会有平衡的二叉查找树。如果一颗树按照10,9,8,7,6,5的方式插入，那么就会变成如下所示:

二叉查找树.png

这种情况下二叉查找树就跟顺序查找一样，时间复杂度变成了O(n)。因此二叉查找树本身就是个方差非常大的查找方式。
所以后面提出了平衡二叉树的概念，也就是自平衡的二叉查找树。

---

2.平衡二叉树

平衡二叉树有两个特性:

1. 必须是二叉查找树
2. 每个节点的左子树和右子树的高度差最多为1。
   这样平衡二叉树的查找效率就会很高，时间复杂度为O(logn)，但是平衡二叉树带来的另一个问题就是每次插入时，会有大量的旋转操作来达到自平衡，从而导致插入效率低下(具体实现方式不是本文重点)。
   那么为了解决平衡二叉树自平衡效率低下的问题，就出现了红黑树的数据结构

---

3.红黑树

相对于平衡二叉树来说，红黑树是一种弱平衡的平衡二叉树，红黑树的左右字数高度最多为2。红黑树有以下五个特性:

1. 节点必须为红色或者黑色
2. 根节点必须为黑色
3. 不能有连续的两个红色节点
4. 叶子节点必须是黑色的空节点
5. 每个节点到达其对应的叶子节点所经过的黑色节点数必须是相同的。

因此下面几种情况都不属于红黑树

1.jpg
2.jpg
3.jpg
4.jpg 5.jpg

• 图1存在白色节点，不满足特性1。
• 图2根节点是红色的，不满足特性2
• 图3存在两个连续的红色节点，不满足特性3
• 图4存在不为NIL的红色节点，不满足特性4
• 图5节点8到节点7对应的子节点的黑色节点数为3(8和7以及空节点都是黑色节点)，而节点8到节点9对应的子节点的黑色节点数为2(8和空节点都是黑色节点)，不满足特性5。

上面几幅图都不是红黑树，如果一旦在插入或者删除以后出现上面几种情况，那么必然要进行变色和旋转的操作。
那么就先来介绍一下旋转好了,旋转分为左旋转和右旋转。

• 左旋转：以某个节点为旋转点，将该节点的右子节点作为父节点，将该节点的右子节点的左子节点作为该节点的右节点，然后其左子节点保持不变。
• 右旋转：以某个节点为旋转点，将该节点的左子节点作为父节点，将该节点的左子节点的右子节点作为该节点的左节点，然后其右子节点保持不变。

上述定义感觉比较拗口难懂，我们举个栗子方便理解(下面仅仅用作理解左旋转和右旋转的概念，因此就用普通的二叉树做例子):

左旋.jpg

先来看左旋：

1. 以节点10为旋转点，然后将节点15作为父节点，节点15就到第一层，此时节点10就变成了节点15的左子节点。
2. 将节点10的右子节点(节点15)的左子节点(节点13)作为节点10的右子节点。
3. 节点10的左子节点和节点15的右子节点保持不变

右旋.jpg

在看看右旋：

1. 以节点10为旋转点，然后将节点7作为父节点，节点7就到第一层，此时节点10就变成了节点15的右子节点。
2. 将节点10的左子节点(节点7)的右子节点(节点8)作为节点10的左子节点。
3. 节点10的右子节点和节点7的左子节点保持不变

上面介绍完了左旋和右旋，接下来看下变色，不过变色其实就是红色变黑色，黑色变红色，所以单纯的变色这里就不做介绍，主要结合一颗红黑树的节点插入来理解变色和旋转的意义。
这里重点提一下:插入节点默认插入的是红色节点，为何？因为假设插入的是黑色节点，那么特性5必然是不满足的，也就是说我们就必须得多做一次自平衡的操作。这样也就会降低红黑树的插入性能
下面先给一张插入的流程图:

插入流程.jpg

1. 首先从根节点开始判断
2. 如果节点为空，直接插入。否则走步骤3
3. key值判断，如果key值相等，更新当前节点的value值。如果插入的key值较大，则走步骤4。如果插入的key值较小，则走步骤5
4. 往右子树查找，然后走步骤2
5. 往左子树查找，然后走步骤2

接下来给出一个例子:

红黑树.jpg

上图所示就是个红黑树，这个时候如果插入key为17的红色节点，那么这颗红黑树依然是符合规则的红黑树，不需要做任何变化。
如果插入key为24的红色节点:

插入24红色节点.jpg
此时就打破了红黑树的特性3，因此我们需要进行变色或者旋转。
这个时候首先考虑的是变色。有两种做法：1、将节点24变为黑色 2、将节点23变为黑色

我们先来看下1的可行性，当节点24变为黑色时，凭空出现了一个黑色节点，那么必然要将另外一个节点变为黑色或者红色，此时就只能将23变为黑色，那么节点15到右叶子节点的黑色节点明显大于节点15到左叶子节点黑色节点，需要做大量的旋转才能达到自平衡，因此此做法不可行。
那么我们看下2的可行性，当节点23变为黑色时，凭空出现了一个黑色节点，那么必然要将另外一个节点变为黑色或者红色，这个时候可以将节点20变为红色节点

节点20变为红色，节点23变为黑色.jpg
我们发现此时 节点20到左叶子节点的黑色节点数 要小于 节点20到右叶子节点的黑色节点数。因此不符合特性5，所以还需要做一次左旋:
左旋.jpg
此时就符合了红黑树的特性。
上述举了其中一种情况的例子来讲解了红黑树的完整变色以及旋转的过程，其他情况基本类似，本文不做赘述，有兴趣的可以自行研究。

---

总结

1. 二叉查找树在插入的时候最快，但是查询速度最慢
2. 平衡二叉树在插入的时候最慢，查询的速度最快
3. 红黑树在插入的时候较快，查询的速度也是较快
   可以根据不同的业务场景来采用对应的数据结构。