本章主要介绍的数据机构的中的红黑树的理解与学习。红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1972年发明，在当时被称为对称二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。考虑到红黑树是一种被广泛应用的数据结构，所以我们很有必要去弄懂它。
基本的概念
上面这张图就是红黑树，你会发现他有如下特征(下面的特征最好看一个特征重新看一遍红黑树)∶
- (1)每个节点只有两种颜色:红色和黑色。
- (2)根节点是黑色的。
- (3）每个叶子节点(NIL)都是黑色的空节点。
- (4)从根节点到叶子节点，不会出现两个连续的红色节点。
- (5)从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。
查询节点是最简单的一个，他的查找过程和二叉查找树一样，查找元素比当前节点大，就从右子树继续查找比较，查找元素比当前节点小，就从左子树继续查找比较。查找过程就不再赘述了。时间复杂度是log(n)。
2、插入节点插入节点是最麻烦的一个，它分为三种情况。我们一种一种看，这样比较有条理性。第一种情况:新节点没有父节点：没有父节点只有一种情况，就是插入的节点是整棵树第一个节点，也就是根节点，为此我们只需要把插入节点涂成黑色就OK了。这也就保证了性质2:根节点是黑色的。第二种情况:新节点的父节点是黑色：为此我们举一个例子，比如说上面的红黑树中，我们插入节点14。来看一下会发生什么情况?
这种情况我们发现新插入节点14的父节点就是黑色的。现在为了保证红黑树的性质，我们对照每个特性来检查—遍。只要有一条不满足，我们都需要调整。我们重新对照之后会发现每一条都符合。此时不需要调整。
第三种情况:新节点的父亲节点为红色：我们还是举个例子，比如我们在最开始的红黑树基础之上插入节点21，此时会发生什么情况呢?
此时还是老规矩，对照着红黑树的5个特征一个一个来看，只要是违反了一条就需要做出调整。我们来看一下:
- (1)每个节点只有两种颜色:红色和黑色。这—条满足。
- (2)根节点是黑色的。这一条也满足。
- (3)每个叶子节点(NIL)都是黑色的空节点。这—条满足。
- (4)从根节点到叶子节点，不会出现两个连续的红色节点。这一条发现不满足。
就是上面这一条规则没有满足，所以我们此时需要调整?问题来了如何调整呢?因为直接看父节点没办法实现，所以还需要观察另外的节点，也就是新节点的叔叔节点。根据叔叔节点的颜色来调整。调整的方式有两种:变色和旋转。
此时插入的节点是21，但是叔叔节点是27，更好是红色。我们直接来看调整的步骤:
第一步:把新节点21的父节点变成黑色。
此时重新看一下是否满足红黑树的五条特征了没，一条一条发现，第五条没有满足，也就是从任何一个节点出发，到叶子节点，这条路径上没有相同数目的黑色节点。比如从25出发。这时候怎么办呢?那就继续调整。
这时候还是老规矩，不要嫌弃麻烦，因为只有经历了一步又一步的麻烦之后，你才能牢记那5条规则特征。我们对照之后会发现节点25和节点27是两个连续的红色节点，这时候又破坏了规则4。怎么办呢?那就继续调整就OK了。
难道这时候还要继续往上调整吗?如果你这样做就错了，因为不断地往上调整最后就会把根节点变成了红色，会走进死胡同。我们往下走。
来吧，继续重新审查那5条规则特征。很明显节点17和节点25是两个连续的红色，又破坏了。是不是心太累了，调整了这么久，还是没有保证那5条规则，感觉是不是还没有平衡二叉树好。如果你现在有这种感觉，我只能说，希望你继续坚持下去，胜利就在眼前。
红黑树的删除说实话更加的复杂，如果你看过算法导论的话应该能明白一点，我们在这里也进行一个大概的讲解。 删除大致分了三种情况， (1)第一种情况:要删除的节点有零个子节点：这种情况下最简单，也就是删除的是根节点或者是叶子节点(这里的叶子节点都是指非NULL的叶子节点)，根节点直接删除即可。如果叶子节点是红色的，也可以直接删除，如果叶子节点是黑色的，那么就需要进行调整，调整的步骤和插入时调整的步骤一样。 (2）第二种情况:要删除的节点有一个子节点：这时候。把子节点的值替换掉要删除的节点的值。
现在我们的5把11替换掉之后，又回到了第一种情况。如果节点5是红色的，可以直接删除，如果节点5是黑色的，那么就需要进行调整，此时的节点5就是叶子节点。调整的步骤和插入时调整的步骤—样。
(3)第三种情况:要删除的节点有两个子节点：现在删除的节点有两个子节点，同样的我们可以执行第二种情况的操作，
若节点13之前是叶子节点，那就和第一种情况一样了，如果节点13是红色的，可以直接删除，如果节点13是黑色的，那么就需要进行调整，此时的节点13就是叶子节点。调整的步骤和插入时调整的步骤一样。若节点13之前还有子节点，那就和第二种情况一样了。那就继续替换和判断。以上呢就是删除的情况，最后一种情况是修改，这种情况是查找和插入的结合体，也就是先找到要修改的元素，修改完值之后，继续进行调整即可。现在还有最后一个问题了，都说红黑树很重要，为什么重要呢?我们来看一下使用场景。
四、使用场景：红黑树的应用真的是太多了，比如说java中的HashMap和TreeMap。还有就是linux也经常使用到。这种数据结构在面试的时候是一个常问问题，希望大家能够明白和理解。如何用java手撕红黑树。
