红黑树的底层阐述
欢迎查看本人的私人博客： http://39.106.81.183:8000
红黑树介绍
首先说为什么叫红黑树？有接触过AVL（平衡二叉树）的应该知道，在AVL树中，维持树的平衡是靠平衡因子，说白了就是左右子树的高度相差不能超过1，且左右子树各是AVL树。但是在红黑树中，维持树的平衡靠的可不是平衡因子，而是每个节点的颜色（红黑树的节点只能为红色或者黑色），这是红黑树与AVL树的区别。
红黑树与AVL树的具体区别如下：
1、红黑树的节点只能为黑色或者红色
2、红色树靠的是节点的颜色来维持平衡，但是AVL树靠的是平衡因子来维持平衡
3、AVL树是绝对平衡的，但是红黑树是相对平衡的（原因在于红黑树的性质5）
4、红黑树应用的场景是增删改查比较多的地方，而AVL树多用在查询较多的地方
5、红黑树的插入效率更高（原因是红黑树是相对平衡的），AVL树的插入效率略低于红黑树（AVL是绝对平衡的）
其实AVL树和红黑树都是一种叫做二叉搜索树的延伸（Binary Search Tree，BTS），之所以叫做BTS，主要原因的搜索的效率是相当的高，这种BTS树的结构是父节点的值大于左子节点，且小于右子节点，如图1所示。
BTS树查找的时间复杂度为O(logn)，但是O(logn)的时间复杂度是维持在树的平衡基础上（就是保持树的平衡），一旦树的平衡遭到破坏，那么时间复杂度一下就降到了O(n)。
那么作为BTS特例的红黑树就更猛了，不光可以将查找的时间复杂度降低为O(logn)，而且插入、删除的的时间复杂度也为O(logn)，这是AVL树无法与之相媲美的。
红黑树的应用场景：
- 红黑树的应用场景第一个就是应用在
C++ STL的set、map中。 - 应用在java中的
TreeMap、TreeSet中，在jdk1.8之后，又应用在了HashMap中（可以参考本人的另一篇博客，专门介绍的HashMap）。 - Linux的的
进程调度，用红黑树管理进程控制块，进程的虚拟内存空间都存储在一棵红黑树上，每个虚拟内存空间都对应红黑树的一个节点，左指针指向相邻的低虚拟内存空间，右指针指向相邻的高地址虚拟内存空间。
红黑树的性质(约束条件)：
- 每个节点只能为红或者黑。
- 根节点必须为黑。
- 一条路径上不能出现两个相邻的红色节点。
- 空叶子节点是黑色的。
- 从根节点到任意一个叶子结点的路径上，黑色节点的数量相同。
对性质的详细解释：
第一、二条性质就不解释了，我来解释一下第三、四、五条性质。
咱们用一张图来解释一下性质三（如图2）：
从根节点开始46 -> 12 -> 13这条路径，存在了两个连续的红色节点，这就是违背了性质三。
解释一下性质四（如图3）：
最后的叶子结点是空的节点，也叫NIL节点，并不是二叉树中的NUll指针，这点是要注意的，并且这个空叶子结点只能是黑色的。
解释一下性质五（如图4）：
可以看到，图4中从根节点到叶子节点一共有8条路径，每条路径上共有3个黑色节点，这就符合了红黑树的第五条性质。
红黑树节点的数据结构：
每个节点的数据结构如图5所示：
好了，红黑树的基本信息就介绍到这里了，如果大家想了解关于红黑树的更多详细介绍，可以查看一下我在结尾处附上的参考文章。
节点旋转的介绍
左旋：
右旋：
红黑树的插入操作
红黑树插入的默认节点是红色的，因为这么做可以避免破坏红黑树的第五条性质（如果插入的是黑节点，就破坏了红黑树的第五条性质），所以采用了默认插入红色的节点。
调整一棵红黑树至平衡只用到了两步，就是recolor(重新赋值颜色)，旋转（左旋或者右旋）
咱们就结合实际进行知识点的讲解。
待插入的数据为：12、3、6、9、1、100、7
首先插入12，这个就一个节点，咱们就不说了，然后插入3、6。当插入6时，插入后如图8所示。
此时红黑树已经不满足第三条性质了（一条路径上不能出现两个相邻的红色节点），那么怎们就得对其recolor，3变为黑色，12变为红色，但是由于12是根节点，所以12只能为黑色。如图9所示。
此时可以看出红黑树是不平衡的，怎么看出来的？就是因为6的父节点3没有兄弟节点。其实判断红黑树是否平衡就是要看插入节点的父亲节点，如果他父亲节点的颜色和他父亲节点的兄弟节点的颜色相同，证明是平衡的，如果不相同，就是不平衡的，如果他父亲没有兄弟节点，也是不平衡的，不平衡怎么办呢，这好办呀，旋转呗。
那好，怎么接下来就开始旋转。
先以6为旋转点进行左旋，旋转后如下（如图10）。由于6变成了根节点，所以6被重新recolor为黑色。
插入9、1、100，此时红黑树还是平衡的，如图11所示。
当插入7之后，如图12所示。
此时节点9和7冲突了，这时候咱们就需要重新进行recolor了，将9、100变为黑色，12变为红色，如图13所示。
那么，这棵红黑树就构建完了。
总结
- 不断地进行
recolor。 - 判断待插入节点的
父亲的兄弟节点的状态，从而判断红黑树是否平衡，如果不平衡，则进行相应的旋转。 - 如果有两个
相邻的红色节点，那么应该将当前待插入节点的父亲和叔叔变为黑色，他的爷爷变为红色，重新插入爷爷节点。
节点的删除这我就不说了，大家有兴趣可以看一下下面的文章。