红黑树是一种特殊的数据结构,是一个可以自平衡的二叉树,查找,删除,新增,效率都很好,今天就一起来了解一下红黑树。首先先来看看效果:

红黑树原理及实现 gif 红黑树原理及实现

假如有三个数,10,20,5,那么先插入一个节点10(根节点),因为20大于10,所以20放在10的右边,5小于10,5放在10的左边。本章所讲的红黑树是按照数字大小来划分左右树的。

红黑树的特点就是从根节点到叶子节点的路径上所有黑色节点的个数相同,并且最长路径不会超过最短路径2倍。无论你如何增加,删除,都能保持这个特性,这个特性可以保证在查找的时候是很高效的。

红黑树的规则

1.节点是红色或黑色。

2.根是黑色。

3.所有叶子都是黑色(叶子是NIL节点)。

4.每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)。

第三条其实不用太在意,一般NIL节点都是黑色的,NIL节点如下所示:

上面最重要的规则就是第4条和第5条,第4条说的是两个红色的求不能直接作为父子,简称双红问题,第5条则是红黑树的关键所在,从任意一个节点到叶子节点所经过的黑色节点数目相同。

红黑树最难的部分就是在于新增和删除后如何根据上面的规则,让红黑树重新找找到平衡,下面看看红黑树在增加,删除的时候如何保持平衡。

红黑树的新增

红黑树的根节点必须是黑色,这个是规定的,除了根节点外,插入的节点我们一般选用红色的,因为如果是黑色的,那么势必会增加某一条路径上的长度,如果是红色的,那么则不会出现长度问题。

这样的话,那么就很容易出现"双红问题",例如:

background Layer 1 5 3 10 15 b(black) r(red) r(red) r(red) 新插入的红色3和红色5造成了“双红”问题

因此插入的时候其实就是要去解决双红问题,让树在不出现双红问题的情况下保持平衡。

情况1:自己的"叔叔节点"也是红色的:

background Layer 1 grandNode parNode uncleNode node r r r b grandNode parNode uncleNode node r r->b r->b b->r

这种情况下,让自己的parNode,uncleNode变成黑色,grandNode变成红色,但是因为grandNode变成红色可能和它上面的节点造成另外一个双红问题,所以在grandNode继续检测双红问题。

情况2:自己和parNode都是左分支:grandNode右旋(同时右分支,则左旋)

background Layer 1 grandNode parNode node r r b grandNode parNode node r r->b b->r grandNode右旋

右旋就是左边的分支上来,自己下去,同时交换自己和左分支节点的颜色。这样操作后,红黑树还是平衡的,左分支和右分支上黑色节点的个数相同。

情况3:自己是左分支,parNode是右分支,parNode右旋,然后检测parNode双红问题。(自己是右分支,parNode是左分支,parNode左旋,然后检测parNode双红问题)

background Layer 1 grandNode parNode node r r b parNode右旋 grandNode parNode node r r b

这种情况实际上是为了将双红扭转到一边,变成情况2,这样就可以用情况2来处理了。

红黑树的删除

相比红黑树的新增,红黑树的删除就复杂的多了,删除主要有两个步骤,第一是缝接树,第二是验证是否符合红黑树。

缝接树的意思就是我们删除了一个节点,破坏了树的上下结构,因此我们删除节点后,首先就是要把上下关系重新进行缝合。我们先来看看关于缝接树的各种情况。

情况1:删除的节点没有左孩子且没有右孩子

这种情况表示删除的是叶子节点,如果这个节点是红色的,那么并不影响整个红黑树,只要把该节点在parNode对应位置设置成一个NIL节点即可。

如果要删除的这个叶子节点是黑色的,那么我们要对这个节点的parNode进行红黑树验证。

特殊情况就是删除的是一个根节点,那么treeNode置空。

background Layer 1 siblinNode parNode node r b r 删除红色叶子节点对红黑树没影响 siblinNode parNode node b b b 删除黑色叶子节点,造成一条那条路径变短 删除后要验证红黑树 删除后不用验证

情况2:删除的节点有左边孩子且没有右孩子

这种情况首先要把该节点左边的孩子挂在该节点的parNode左边:

background Layer 1 parNode node childNode r r b 删除红色叶子节点对红黑树没影响 删除黑色叶子节点,造成一条那条路径变短 删除后要验证红黑树 删除后不用验证 要删除的节点 把childNode挂在parNode左边 parNode node childNode r b b 要删除的节点 把childNode挂在parNode左边

特殊情况就是如果删除的是treeNode根节点,那么则把左边孩子变成treeNode。

background Layer 1 treeNode childNode r b 要删除根节点 childNode变成根节点 同时颜色变成黑色

情况3:删除的节点有右边孩子且没有左孩子

这种情况和情况2类似,只不过反过来了。

情况4:删除的节点有左孩子且有右孩子

这种情况比较复杂,我们要首先找到一个和要被删除节点内容差不多“替死鬼”,然后将它的内容复制给要被删除的节点,然后对这个"替死鬼"进行删除。

background Layer 1 parNode node 要删除根节点 childNode1 childNode2 一直找右节点 复制 内容 替死鬼 r 变成它的右节点 替死鬼是红色的,只要把它的左节点放到它的上层节点的右边即可 parNode node 要删除根节点 childNode1 childNode2 一直找右节点 复制 内容 替死鬼 b 变成它的右节点 替死鬼是黑色的,删除后破坏了红黑树的平衡,要验证。

找替死鬼的方法是,先找到这个节点的左节点,然后一直找这个左节点的右节点,最末端的这个节点就是“替死鬼”节点。

如果替死鬼节点的左边没有内容的话,其实我们就不用纠正位置了,只要看替死鬼节点是红还是黑就好了。

不过这里有一种特殊情况,就是要被删除的节点左节点上没有右节点:

background Layer 1 parNode node 要删除根节点 childNode1 childNode2 替死鬼是红色的,只要把它的左节点放到它的上层节点的左边即可 替死鬼 复制 内容 挂在左边 r parNode node 要删除根节点 childNode1 childNode2 替死鬼是黑色的,破坏了平衡,因此要验证红黑树的特性 替死鬼 复制 内容 挂在左边 b

这种情况下,被删除节点的左节点就是“替死鬼”节点,然后把“替死鬼”的左节点接到被删除节点的左侧。

红黑树删除验证平衡

上面讲解了红黑树删除后的缝接操作,其中里面很多地方讲到了如果删除的节点是黑色的,需要验证平衡,这节主要讲如何验证删除后的平衡。

情况1:被删除节点的兄弟节点是黑色,且有两个黑色的孩子。

background Layer 1 parNode node b sibling b b b NIL NIL b b NIL NIL 删除节点 r parNode sibling b->r b b NIL NIL b NIL r->b 删除前每条路径上有2个黑节点 删除后每条路径还是2个黑节点 parNode为红色 parNode node b sibling b b b NIL NIL b b NIL NIL 删除节点 b parNode sibling b->r b b NIL NIL b NIL b 删除前每条路径上有3个黑节点 删除后每条路径2个黑节点 parNode为黑色 内部虽然平衡,但是外部不一定平衡 对parNode继续检测

这里要分parNode是黑色还是红色,如果是红色,把sibing变成红,parNode变成黑就好,内部平衡,和之前路径上黑节点个数没变。如果是黑色,把sibling变成红,但是这让虽让内部平衡,但是比外面每条路径上还是少了一个黑节点,因此对parNode继续检测。

情况2:兄弟节点是红色:

background Layer 1 parNode node b sibling r b b 删除节点 b 删除前每条路径上有2个黑节点 parNode左旋转 b b parNode b->r sibling r->b 删除后每条路径上还是2个黑节点

当删除节点是左节点的时候,parNode左旋转,sibling和parNode交换颜色,即可达到树的平衡;当删除节点是右节点的时候,parNode右旋转,sibling和parNode交换颜色,可达到树的平衡。

第3种情况:自己是左节点,兄弟节点的右孩子是红色的。(自己是右节点,兄弟节点的左孩子是红色的)

background Layer 1 parNode node b sibling b r 删除节点 r 删除前每条路径上有1个黑节点 parNode sibling b->r r->b r->b parNode左旋转(红色) 删除后每条路径上还是1个黑节点 parNode node b sibling b r 删除节点 b 删除前每条路径上有2个黑节点 parNode sibling b r->b b parNode左旋转(黑色) 删除后每条路径上还是2个黑节点

这里旋转要注意parNode的颜色,如果parNode是红色的话,parNode旋转后,sibling右孩子要变成黑色,且sibling和parNode交换颜色;如果parNode是黑色的话,只要sibling右孩子变成黑色就好了。

第4种情况:自己是左节点,兄弟节点的右孩子是黑色的。(自己是右节点,兄弟节点的左孩子是黑色的)

background Layer 1 parNode node b sibling b 删除节点 r sibling右旋转 r parNode node b sibling r->b 删除节点 r b->r

这种情况其实主要是把它变成情况3,接着对删除元素进行验证。

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字