算法基础8：平衡树之红黑树
算法是基础，小蓝同学准备些总结一系列算法分享给大家，这是第8篇《平衡查找树概述》，非常赞！希望对大家有帮助，大家会喜欢！
前面系列文章：
我们在上一节写了平衡树的一些理念和具体的实现名（算法基础7：平衡查找树概述），为了解决其查找成本较高的这个问题，我们采取了扩大节点来减少层级的方式来达到这个目标。根据这个理念，我们找到了平衡查找树树。
一、 下面我们来一起聊一聊平衡树的具体实现红黑树。红黑树需要满足的五条性质：
性质一：节点是红色或者是黑色；注（红色节点可以理解成一种过渡节点，实现平衡树）
在树里面的节点不是红色的就是黑色的，没有其他颜色，要不怎么叫红黑树呢，是吧。
性质二：根节点是黑色；
根节点总是黑色的。它不能为红。
性质三：每个叶节点（NIL或空节点）是黑色；
这个可能有点理解困难，可以看图：
这个图片就是一个红黑树，NIL节点是个空节点，并且是黑色的。
性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；
就是连续的两个节点不能是连续的红色，连续的两个节点的意思就是父节点与子节点不能是连续的红色。
性质五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点；**
还是看图：
我们所有的红黑树都满足这5个特性，也是由于有着5个特性 所有他的时间复杂度才可以保持在对数范围。
下面我们介绍下旋转：旋转的目的是将节点多的一支出让节点给另一个节点少的一支，旋转操作在插入和删除操作中经常会用到，所以要熟记。
二、结点插入
将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。
1.将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了
2.对于"特性4"，是有可能违背的！
总之：新插入的结点是红色！
3.插入的5种情况：
（1）如果插入的是根结点，由于原树是空树，此情况只会违反性质2，因此直接把此结点涂为黑色；
（2） 如果插入的结点的父结点是黑色，由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时什么也不做。
（3） 如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色；
解决： 将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。
以下（4）（5）都以左孩子为例，右孩子进行对称操作即可
（4）当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子；
解决： 父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋。
5）当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子；
解决：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。问题转为（4）
总结：整个过程就是解决以上几个问题，关键是整个过程要更新当前节点是哪个结点
三、应用场景
1.著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
2.epoll在内核中的实现，用红黑树管理事件块
3.nginx中，用红黑树管理timer等
4.Java的TreeMap实现
5.广泛用在C++的STL中。map和set都是用红黑树实现的。
猜你喜欢
加入技术讨论群
《大数据和云计算技术》社区群人数已经3000+，欢迎大家加下面助手微信，拉大家进群，自由交流。
喜欢钉钉扫码下面的群：
喜欢QQ群的，可以扫描下面二维码：
欢迎大家通过二维码打赏支持技术社区（英雄请留名，社区感谢您，打赏次数超过108+）：
相关内容
微信扫码咨询专知VIP会员