网上有很多红-黑树的段子，很多人都说，红-黑树只会存在于段子里，不会在面试中或者实际项目中让你实现。来看看网友都是怎么说的：
通常，如果有面试官问我红黑数这种问题。
我一般扭头就走。
不是因为，这个职位用不到还问这个。
而是因为。
我 tmd 真的不会啊 - -|||
很多人看着这个网友说的，感觉很扎心。别急，还有更扎心的：
这有什么难的！
Map map = new TreeMap();
手动斜眼，已经写完了
如果这样，面试官一定也是一脸懵逼啊~ 不过也没错，TreeMap 内部的确就是用红-黑树实现的。学红-黑树不仅仅是用来应付面试官，武侠小说里说：招式只是形式，要练神功，必须要懂心法。这篇文章就带你慢慢拨开红-黑树的面纱，特别是文章中的动态图会让你很直观的感受红-黑树的旋转。当然咯，理解了这篇文章，面试也能轻松搞定啦~
我们知道，二叉搜索树是个很好的数据结构，可以快速地找到一个给定关键字的数据项，并且可以快速地插入和删除数据项。但是二叉搜索树有个很麻烦的问题，如果树中插入的是随机数据，则执行效果很好，但如果插入的是有序或者逆序的数据，那么二叉搜索树的执行速度就变得很慢。因为当插入数值有序时，二叉树就是非平衡的了，排在一条线上，其实就变成了一个链表……它的快速查找、插入和删除指定数据项的能力就丧失了。
为了能以较快的时间 O(logN) 来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的），这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。红-黑树的就是这样的一棵平衡树，对一个要插入的数据项，插入例程要检查会不会破坏树的特征，如果破坏了，程序就会进行纠正，根据需要改变树的结构，从而保持树的平衡。那么红-黑树都有哪些特征呢？
1. 红-黑树的特征
它主要有两个特征： 1.节点都有颜色；2.在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则。首先第一个特征很好解决，在节点类中添加一个数据字段，例如 boolean 型变量，以此来表示节点的颜色信息。第二个特征比较复杂，红-黑树有它的几个规则，如果遵循这些规则，那么树就是平衡的。红-黑树的主要规则如下：
- 1.每个节点不是红色就是黑色的；
- 2.根节点总是黑色的；
- 3.如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
- 4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
在红-黑树中插入的节点都是红色的，这不是偶然的，因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小。原因是：插入黑色节点总会改变黑色高度（违背规则4），但是插入红色节点只有一半的机会会违背规则3。另外违背规则3比违背规则4要更容易修正。当插入一个新的节点时，可能会破坏这种平衡性，那么红-黑树是如何修正的呢？
2. 平衡性的修正
红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。这看起来有点抽象，我们分别来介绍它们。
2.1 变色
改变节点颜色比较容易理解，因为它违背了规则3。假设现在有个节点E，然后插入节点A和节点S，节点A在左子节点，S在右子节点，目前是平衡的。如果此时再插一个节点，那么就出现了不平衡了，因为红色节点的子节点必须为黑色，但是新插的节点是红色的。所以这时候就必须改变节点颜色了。所以我们将根的两个子节点从红色变为黑色（至于为什么都要变，下面插入的时候会详细介绍），将父节点会从黑色变成红色。可以用如下示意图表示一下：
2.2 左旋
通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。示意图如下：
左旋有个很萌萌哒的动态示意图，可以方便理解：
2.3 右旋
右旋可左旋刚好相反，这里不再赘述，直接看示意图：
当然咯，右旋也有个萌萌的动态图：
这里主要介绍了红-黑树对平衡的三种修正方式，大家有个感性的认识，那么什么时候该修正呢？什么时候该用哪种修正呢？这将是接下来我们要探讨的问题。
