这一篇我们来看看红黑树，首先说一下我啃红黑树的一点想法，刚开始的时候比较蒙，what？这到底是什么鬼啊？还有这种操作？有好久的时间我都缓不过来，直到我玩了两把王者之后回头一看，好像有点儿意思，所以有的时候碰到一个问题困扰了很久可以先让自己的头脑放松一下，哈哈！
不瞎扯咳，开始今天的正题；
前提：看红黑树之前一定要先会搜索二叉树
1.红黑树的概念
红黑树到底是个什么鬼呢？我最开始也在想这个问题，你说前面的搜索二叉树多牛，各种操作效率也不错，用起来很爽啊，为什么突然又冒出来了红黑树啊？
确实，搜索二叉树一般情况下足够了，但是有个很大的缺陷，向搜索二叉树中插入的数据必须是随机性比较强大的；如果你是插入的顺序是按照一定的顺序的，比如10、9、8、7、6、5、4、3、2、1，你把这十个数据插入到搜索二叉树中你就会看到一个比较有趣的现象；玛德，这二叉树居然变成链表了（此时的链表也可以说是不平衡树），这就意味着变成链表之后就丧失了身为搜索二叉树的所有特性，这就很可怕，而且当这种有顺序的数据很多的时候，就特别坑爹，查询的效率贼慢；
所以就出现了红黑树这种数据结构，可以说这是一种特殊的搜索二叉树，是对搜索二叉树进行改进之后的一种很完美的二叉树，这种数据结构最厉害的就是可以自动调整树的结构，就比如上面这种有顺序的数据插入到红黑树之后，红黑树就会自动的啪啪啪给你一顿调节最后还是一棵正常的搜索二叉树，不会变成链表就对了；
那么就有人要问了，要怎么样才能将一个搜索二叉树变成红黑树呢？
答：这很容易回答，字如其名，你把搜索二叉树的每个节点要么涂成红色要么涂成黑色，使得最后这个二叉树中所有节点只有红黑两种颜色，这就是一个红黑树；
这时还有人要问了，是不是可以随意把搜索二叉树中的节点涂成红色或者黑色呢？
答：emmmm.....你觉得有这么容易么？哪有这么随便的！肯定是要符合一些规则你才能涂啊，而且大佬们已经把这些规则总结出来了，我们只需要记好这些笔记就好了！
下面我们就看看红黑树要满足的规则：
（1）：每个节点不是红色就是黑色；
（2）：根节点总是黑色；
（3）：不能有两个连续的红色节点；
（4）：从根节点到每一个叶节点或空子节点的黑色节点的数量一定要相同，这个黑色节点的数量叫做黑色高度，所以这个规则换句话来说就是根节点到每一个叶节点或空子节点的黑色高度相等；
这四个规则很重要，任何红黑树都必须同时满足这四个规则，否则就不是红黑树，前三个很容易，话说第四个的空子节点是什么意思呢？字如其名，就是一个空的节点，里面什么都没有，可以当作一个null节点，比如下图所示，这个其实理解就好，不用在意；
第四条规则为了好理解才从根节点开始的，其实从任意一个节点开始也是一样的；可以拆分为两条，某个节点到该节点每一个叶节点的黑色高度要一样，同时还要该节点到该节点的每一个空子节点的黑色高度要一样；
空子节点的定义为：非叶节点可以接子节点的位置；（注意，有的版本没有这个空子节点这个说法，只是说每一个叶节点（NIL）都是黑色的。。。。而且这里的叶节点和之前我们理解的叶节点还不一样，看看下图，但本篇我们还是按照空子节点的这个说法，参考《java数据结构和算法第二版》），理解了之后其实是一样的
我们再看看下面这个我截的图，假如不看那两个空子节点，看起来好像是符合红黑树规则的，但是我们还要判断根节点到每个空子节点的黑色高度是不是一样，结果不一样，于是下图其实违背了规则四；
这里继续说一点东西：
新插入的节点必须是红色的，为什么呢？你想啊，你往一个正常的红黑树中插入一个黑色节点，肯定就会百分之百违反第四规则，这就比较坑，每插入一个节点你都要想办法去调整整个树的颜色和结构，这很影响效率；但是假如你插入的节点是红色的，而且这个红色节点还刚好是插入在一个黑色的叶节点那里，诶呀，舒服，什么都不用动；当然还有可能插入到另一个红色节点下面，所以插入红色节点违反规则的概率是百分之五十，用脚趾头都能想到新插入的节点肯定要是红色的啊！
2.红黑树调整的方式
对了，知不知道计算机中红黑树怎么区分红黑色节点啊？我们不可能真的去给计算机中的节点涂颜色吧。。。。其实我们只需要在节点类中添加一个Boolean color的属性即可，color为true表示黑色，false为红色；
我们在插入红色的节点的时候有两种可能：（1）刚好把这个红色节点插入到一个黑色节点下面，这个时候直接添加就好；（2）比较不幸，插入到一个红色节点下面，这个时候就违反规则3，连续两个节点为红色，这个时候我们要对红黑树的颜色和进行一定调整；
我们对不符合规则的红黑树进行调整操作主要是分为两个步骤：改变颜色和旋转
改变颜色就不多说了，看名字就知道，我们重点就看看旋转到底是什么鬼？通过改变一些节点的颜色使得满足红黑树规则；
通常情况下旋转分为左旋（逆时针）和右旋（顺时针），我们就简单看看右旋吧，左旋差不多；注意下图这里的右旋可不是绕着节点A旋转啊，A叫做顶端，这里相当于是把这两个节点之间的路径进行了一个旋转；（这里很像绕着A节点旋转，很抱歉不是绕着A旋转，下面我们看看红黑树中的右旋就看的很明显了。。。）
在红黑树中的右旋，在下图中80是“顶端节点”，经过右旋之后顶端节点变为右子节点，而原来的左子节点50变为顶端节点，这样调整了之后70这个节点就没地方放了，于是我们可以顺着右旋之后的50节点的右子节点找到可以存放的位置，也就是80的左子节点，我们可以把70这个节点的移动看作横向移动；
从右往左看就是左旋，这里就不详说了。。。，
对了，顺便提一下，假如这里的70节点有子节点，那么子节点也会跟着一起移动的；我们把70这个节点叫做80这个顶端节点的内侧子孙节点，把30叫做顶端节点80的外侧子孙节点，这个还是很好理解的，30这个节点在树的靠外面，70这个节点始终都是在中里面。。。。
网上找到两张动态的图可以看看右旋和左旋，可以好好理解这旋转，旋转真的很重要！！！
3.添加红黑树节点
下面我们通过慢慢的添加一个一个节点，看看红黑树当遇到问题的时候是怎么调整的；
（1）
（2）
（3）右图这种情况下根节点左边两层，右边一层，稍微有点不平衡，但是没有违反红黑树规则，于是我们不必在意什么；但是假如一条路径比另外一条路径多两层或者两层以上，这个肯定是会违反红黑树规则的，为什么呢？我也不是怎么清楚可能是经过大佬们无数次试验得出来的结论吧！
（4）
此时我们碰到这种情况，第一感觉是改变10和25的颜色，下图所示，看起来貌似是符合红黑树结构的；但是我们要记住当一条路径多于另外一条路径两层及以上的时候肯定会违反红黑树规则，我们再仔细看看这个图就会发现违反了第四规则中：根节点到空子节点的黑色长度要一样
所以我们可以知道只是单纯的改变颜色肯定是不能满足红黑树规则的，我们还要再进行旋转，我们以25为顶端节点进行右旋，变成了下图，满足条件，ok