前言
近期需要使用红黑树进行操作。此文目的只为巩固rbtree的一些概念和用法。代码原型为linux 中的rbtree
下图为一个红g
关于红黑树的概念有的人会想到RB，
红黑树这个名词大家都听过，那红黑树在这过程中他用在那里呢，
有的朋友说红黑树用在面试中，有的朋友说始终体会不到红黑树的优势到底在哪里，
现在呢跟大家讲一下，在面试中红黑树出现的概率是很高的，大家记住哦《面试中红黑树出现的概率是很高的》
有的人在面试中只能想到手撕红黑树，个大家解释一下啊，面试中手写红黑树非常非常少，而且有很多人写不出来，
那面试中怎么面试红黑树呢，
比如
1，进程的调度如何实现，如何使用红黑树的，
2，关于内存管理怎么跟红黑树有关系
3.网卡数据，
在以上这些场景，如何使用红黑树的？
什么是红黑树呢，
这里有四棵树中间有一个假设的前提就是，所有的叶子点都隐藏，并且是黑色的，
所以大家都不去担心叶子节点
关于红黑树的性质
1，每个结点是红的或黑的
2，根结点是黑的
3，每个 叶子结点 是黑的
4，如果一个结点是红的，则它的两个儿子都是黑的
5，对每个结点，从该结点到其子孙结点所有路径上的包含相同数目的黑结点
这几条性质大家都懂吧
下面这四颗红黑树，带红色的黑色的，那些是红黑树，那些不是红黑树，
对应着上面5个性质看一下，
（1）1为什么不是呢，违背的性质五，
（2）3很明显也违背了性质五，
（3）4违背了根结点它不是黑色的，
红黑树树实现的原理
大家可以看到这里是一颗红黑树
同黑的结点不管从那个角度它是满足红黑树的性质的，
比如说我们的添加与删除它如何证明红黑树，
红黑树主要用于存储有序的数据，它的时间复杂度是O(logn)，非常高效
添加规则
红黑树添加的4种情形
（1）新节点位于根节点，其没有父节点时，处理思路：将该节点直接设为黑色即可
（2）新节点的父节点已然是黑色时，处理思路：不用动，这已然是一颗红黑树
（3）父节点 和叔 节点都是红色时，处理思路：a.将父节点和叔节点设为黑色;b.将祖父节点设为红色;c.将祖父节点设为当前节点，并继续对新当前节点进行操作
（4）父节点是红色，叔节点是黑色时，又分如下四种情况：
当前节点是父亲的左孩子，父亲是祖父的左孩子（Left-Left），处理思路：a.将祖父节点右旋;b.交换父节点和祖父节点的颜色当前节点是父亲的右孩子，父亲是祖父的左孩子（Right-Left），处理思路：a.将父节点左旋，并将父节点作为当前节点; b.然后再使用Left Left情形当前节点是父亲的右孩子，父亲是祖父的右孩子（Right-Right），处理思路：a.将祖父节点左旋;b.交换父节点和祖父节点的颜色当前节点是父亲的左孩子，父亲是祖父的右孩子（Left-Right），处理思路：a.将父节点右旋，并将父节点作为当前节点; b.然后再使用Right Right情形
4、添加图例
通过插入 12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17 完成上述所有情形的展示。
（1）添加12
说明：添加的节点若是根节点，则直接将其设置为黑色
（2）添加1
说明：添加的节点若不是根节点，则将其设置为红色
（3）添加9
（4）添加2
（5）添加0
（6）添加11
（7）添加7
（8）添加19
（9）添加4
（10）添加15
（11）添加18
（12）添加5
（13）添加14
（14）添加13
（15）添加10
（16）添加16
（17）添加6
（18）添加3
（19）添加8
（20）添加17
添加的过程讲解完毕。改天在跟大家讲删除，一起学习的可以后台私信“资料”送相关学习资料可以一起学习交流大家也可以关注一下，记得后台私信“资料”送学习视频 需要C/C++ Linux服务器架构师学习资料后台私信“资料”（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ， MySQL ，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等等。。。），免费分享
