前言

我不喜欢搞什么“一文看懂XXX”的标题，因为如果一开始看到“一文读懂XXX”的标题，然后放松警惕，但当读完后，发现自己没有懂，难免会感到失落与担忧。大多数时候，这不是读者的问题，而是写作者的问题，写作者并没有将内容写得通俗易懂，却起这种标题去吸引眼球，从而使部分读者产生心理落差，这是极不负责的表现。
因为马上就要算法考试了，所以代码没时间写了，一部分概念也没时间细说了，这次就先把变色和旋转的规则说一说，剩下的等考完试再补。

为什么要红黑树？

相关的理由我在二叉查找树哪里提过，这里可以移步二叉查找树
简单来说，就是如果只用二叉查找树，当插入的数据是递增或者是递减的时候，二叉查找树就会退化成一个链表，查找时间由 O(logn) 退化为 O(n)。
在JDK1.8中，对HashMap进行了优化，当链表长度大于8时，就会将链表改为红黑树，从而增加查找效率。所以了解红黑树，对我们去学习源码也有很大的帮助。

红黑树需要遵守的性质

红黑树要遵守以下性质，才能保证总体平衡（具体是为什么我也搞不清楚…可能和图论数论的知识相关吧）

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点，即NULL）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树的变换方式

红黑树一共有下面三种变换方式

1. 变色
2. 左旋
3. 右旋

变色
顾名思义，就是由红变黑，或是由黑变红


左旋
多说无益，直接上动图

右旋
直接上动图

红黑树的变换原则

上一部分介绍了什么是变色、左旋和右旋，这一部分我来介绍什么时候需要变色、左旋或右旋，首先我们要明确，每次插入的新节点，都默认是红色节点。 下面我们正式开始。

1. 变色： 当父节点和叔父节点都是红色时，父节点和叔父节点都变成黑色，祖父节点变为红色，如下

6的父节点和叔父节点都是红色

变色

2. 左旋： 当父节点为红，叔父节点为黑，且插入的节点为右孩子，则进行左旋

节点12，父红，叔黑，且为右孩子

对节点12进行左旋

3. 右旋： 右旋比左旋要复杂，其中还涉及变色的操作。当父节点为红，叔父节点为黑，且插入的节点为左孩子，则先将父节点变黑，祖父节点变红，再对父节点进行右旋

节点5，父红，叔黑，且为左孩子

先将节点5的父变黑，祖父变红

再对节点5的父节点12 进行右旋

下面我来演示一个完整的插入示例

这里我们插入元素6

因为节点6的父、叔都为红，所以变色

节点12，父黑，叔红，且为右子树，要左旋

在节点12左旋完后，节点5也要变化，因为节点5父红叔黑，且为左子树，所以要右旋

先对节点5的父，祖父节点进行变色

再对节点5的父节点，即节点12进行右旋操作 最后获得的，就是调整好的红黑树

代码展示

--------------------------------------待施工---------------------------------------
因为要算法考试了，所以暂时没工夫写了，所以先空在这里
如果想看好的红黑树代码
读者可以去翻jdk1.8中 HashMap的源码，里面涉及红黑树的代码写的十分的好

红黑树和AVL树该怎么选择

我之前看到相关的介绍上讲，在实际测试中，AVL树的查找效率是要略优于红黑树的，但这不意味着红黑树就一无是处。
因为AVL树是高度平衡的查找树，所以几乎每一次插入，都会影响树的平衡，从而要进行调整，这样多次插入下来，AVL树调整的时间肯定就会把比红黑树少的那么一点点查找时间给耗尽了。
所以，如果涉及大量的插入、删除操作，建议选择红黑树，但是如果只是涉及大量的查找，那建议使用AVL树。

完~