近期需要使用红黑树进行操作。此文目的只为巩固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等等。。。），免费分享
,
