一种自平衡二叉查找树，通过对任意一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保从根到叶子节点的最长路径不会是最短路径的两倍，用非严格的平衡来换取增删节点时候旋转次数的下降，任何不平衡都会在三次旋转之内解决<br />红黑树的叶子节点指向空NIL，不明白，就当没有NIL叶子节点看就行了（如果需要判断，如果没有子节点可以看作是Nil节点，空叶子节点，黑色）<br />我感觉啊，因为需要跟到叶子节点的黑节点数量一致，所以需要叶子节点是黑色的，但是有的是红的怎么办呢，就给叶子节点加上Nil节点，黑节点，为空，就可以判断路径顺序了<br />
性质：
1.节点时红色或者黑色
2.根节点时黑色
3.每个叶子节点都是黑色的空节点（NIL节点）
4.每个红色节点的两个子节点都是黑色（从每个叶子节点到根的所有路径上不能有两个联系的红色节点）
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
红黑树的添加跟删除，添加的时候，添加的节点是红色的，然后再自平衡，变色，如果是黑色的话，因为原本是平衡的，加一个黑的叶子节点，必然导致不平衡，自平衡更加麻烦，删除节点话，还是还是跟AVL树差不多，不过增加了变色这一步，都是通过替换节点，成为删除叶子节点，操作，然后通过旋转，变色，达到平衡
添加节点
使用场景：
应用：
广泛用在C++的STL中，map和set都是用红黑树实现的
著名的linux进程调查，completely fair scheduler 用红黑树管理进程块
epoll在内核中的实现，用红黑树管理事件快
nginx中用红黑树管理timer等
红黑树的查询性能略逊色于AVL树，因为比AVL树会稍微不平衡对多一层，也就是说红黑树的查询性能之比相同内容的AVL树，最多多一次比较，但是红黑树在插入和删除上比AVL树，好太多，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所作的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小很多，而且红黑树的时间复杂度也是O(log n)
添加节点
1.添加节点，没有父节点，是根节点
直接将节点变为黑色，当作根节点，符合所有的红黑树规则
2.添加节点，父节点是黑色
因为默认添加的叶子节点是红色的，没有打破红黑树规则，不用调整
3.添加节点，父节点是红色，叔叔节点也是红色
新添加节点是红色的，父节点也是红色的，违背原则，先将父节点变成黑色
但是这样B路径就多出来一个黑色节点，规则5（路径黑子一致）规则打破，将祖父节点A变成红色
又会导致两个红色节点相连，依旧不符合，将叔叔节点C变为黑色
这样就平衡了，不过现在根节点是红色的，不符合，所以将根节点A当作新添加的节点，再执行一遍平衡操作，直到完全符合规则
4 添加节点，父节点是红色，叔叔节点是黑色（NIl）或者没有，且新节点是父节点的左孩子，父节点是祖父节点的左孩子
以祖父节点为轴，做一次右旋，使得父节点称为祖父节点，
现在还是不能满足规则，将节点B改为黑色，节点A改为红色，就可以符合规则
5. 添加节点，父节点是红色，叔叔节点是黑色（NIl）或者没有，且新节点是父节点的右孩子，父节点是祖父节点的左孩子
以父节点为轴，做一次左旋，使得新添加节点称为父节点（此处的黑色节点C其实是不存在）
此时情况就变成4的情况了，上面操作就可以了
6.添加节点，父节点是红色，叔叔节点是黑色（NIl）或者没有，且新节点是父节点的右孩子，父节点是祖父节点的右孩子
跟情况45是镜像关系，重复操作即可
7.添加节点，父节点是红色，叔叔节点是黑色（NIl）或者没有，且新节点是父节点的左孩子，父节点是祖父节点的右孩子
跟情况45是镜像关系，重复操作即可
总结
| 父节点 | 叔节点 | 处理 |
| 无 | 无 | 根节点，变为黑色 |
| 黑 | 随便 | 默认添加红节点，无需处理 |
| 红 | 红 | 父节点边黑，叔节点边黑，祖父变红，将祖父节点当作添加节点，重复添加操作，直到平衡 |
| 红（左） | 黑（Nil）（左） | 祖父节点，右旋，变色（父节点黑色，祖父节点红色） |
| 红（左） | 黑（Nil）（右） | 父节点，左旋，然后变为上面的情况了 |
| 红（右） | 黑（Nil）（右） | 祖父节点，左旋，变色（父节点黑色，祖父节点红色） |
| 红（右） | 黑（Nil）（左） | 父节点，右旋，然后变为上面的情况了 |
节点删除
一般分为三种情况，删除无子节点的叶子节点，删除有一个节点的节点，删除有两个子树的节点
但是删除操作都可以通过替换节点的方式，替换成删除一个或者没有子节点的节点了，
删除拥有一个子节点的节点，因为是平衡的关系，那一个节点肯定是红色节点，替换下，就成为了删除叶子节点了，
最终都会演化成删除叶子节点，
1.删除拥有两个节点的节点
删除节点（2）首先找到该节点的后继节点（3）然后替换被删除的节点（2），这样删除两个子节点的节点，就变成了删除一个或者没有子节点的节点了
如果替换节点是红色节点，直接删除就可以了
如果替换节点是黑色节点，分为两种情况
1.如果有一个子节点的话，
肯定是红色的，因为如果是黑的，就不平衡了，直接替换黑色节点跟红色子节点，然后删除红色叶子节点，就可以了
2.如果没有子节点，分为7种情况
1.父节点是红色节点，兄弟是黑色叶子节点，
直接删除黑色替换节点，交换父节点跟兄弟节点的颜色即可
2.父节点是红色节点，兄弟是黑色子节点，并且兄弟节点的左子树是红色
直接删除黑色替换节点，对兄弟节点进行右旋操作，交换兄弟节点跟右子树的颜色，对父节点进行左旋操作即可
3.父节点是红色节点，兄弟是黑色子节点，并且兄弟节点的右子树是红色
直接删除黑色替换节点，对父节点进行左旋操作，即可
4.父节点是红色节点，兄弟是黑色子节点，并且兄弟节点的两个子树都是红色
直接删除黑色替换节点，对父节点进行左旋操作，将旋转后的兄弟节点跟子节点交换颜色，即可
5.父节点是黑色节点，兄弟是红色子节点，并且兄弟节点的两个子树都是黑色
直接删除黑色替换节点，将父节点进行左旋操作，然年修改颜色（兄弟节点变成红色，兄弟左子树的右子树变为红色）
6.父节点是黑色，兄弟节点也是黑色
直接删除黑色替换节点，将兄弟节点变为红色，再将父节点的兄弟节点换成红色
7.父节点是黑色，兄弟节点是黑色，兄弟节点的子节点都是红色
直接删除黑色替换节点，将父节点左旋操作，将兄弟节点的右子树变为黑色
因为二叉树的性质解决的，树的高度很大，每次的查询数据，从磁盘种加载，磁盘IO次很多，（磁盘IO的效率很低，当存在大数据存储时，磁盘查询的时候不能读取全部数据，一次加载一个磁盘页，对应树的节点），每次的一个节点都是一次磁盘IO，而二叉树的高度很大，最坏的结果是高度次数的IO，读写过于频繁，导致效率低下，于是有了B树
若有收获，就点个赞吧
0 人点赞
