算法基础 8:平衡树之红黑树



转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com

AIQ 机器学习大数据 知乎专栏 点击关注

我们在上一节写了平衡树的一些理念和具体的实现名(算法基础 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 都是用红黑树实现的。


更多高质资源 尽在AIQ 机器学习大数据 知乎专栏 点击关注

转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com