Github: 插入一个红节点引起颜色翻转
Email: BuddyZhang1 buddy.zhang@aliyun.com
目录
红黑树插入一个红节点引起颜色翻转原理
父节点是祖父节点的左孩子,新插入一个红节点,与父节点和祖父节点构成一个
临时的 4-node 的时候,即一个节点的两个子节点均为红色,此时需要颜色翻转。
颜色翻转的触发场景:
红黑树中涉及的一些结论:
核心代码实现
为了实现上面讨论的颜色翻转操作,参考内核中的实现进行分析,位于 lib/rbtree.c 文件中,
实现如下:
首先确认父节点是祖父节点的左孩子,新插入的节点是父节点的左孩子,叔叔节点是红节点,但插入
新节点到父节点的左边,此时由于不满足红黑树的性质,需要将父节点和叔叔节点都设置为黑色。
然后将祖父节点设置为红色节点。此时颜色翻转已经完成。此时由于祖父节点还是一个红节点,需要
继续与更上层的节点进行操作,但本文只讨论颜色翻转,因此这里不继续讨论下去。
红黑树插入一个红节点引起颜色翻转与 2-3 树的关系
毕竟红黑树是 2-3 树的一种表现形式,因此插入一个红节点到引起红黑树颜色翻转原理也符合 2-3 树
的原理。由于父节点是祖父节点的左孩子,那么祖父节点是一个 2- 节点。父节点此时是一个黑节点,
叔叔节点也是一个红色节点,但插入红节点之后,祖父节点,叔叔节点与父节点一同组成了一个 4- 节点,
但这个 4- 节点的颜色是 “红-黑-红”,因此此时需要对父节点向上融合,因此父节点的颜色设置
为红色,两个孩子节点设置为黑节点,这样一个 4- 节点被拆成了三个 2- 节点,此时颜色翻转完成,
但是由于父节点还是一个红节点,需要等待与更上一层的节点进行融合。由于本文之讲解颜色翻转,
因此不继续讨论下去,如下图。
如上图,在为添加红节点之前,p0 节点是一个 2- 节点,当添加一个红节点 n0 的时候,此时
n1、p0、n2 节点构成了一个零时的 4- 节点,需要分裂和提取操作,将一个 4- 节点分裂成 3 个
2- 节点,因此将 n1 与 n2 节点设置为黑色节点,由于 p0 节点需要继续向上融合,因此
需要将 p0 设置为红色。此时颜色翻转完成。更多红黑树与 2-3 树的关系请看文档:
红黑树与 2-3 树的关系分析
红黑树插入一个红节点引起颜色翻转实践
实践源码
实践源码 GitHub
开发者可以从上面的链接中获得所有的实践代码,也可以使用如下命令获得:
实践源码具体内容如下:
源码编译
使用如下命令进行编译:
源码运行
实践源码的运行很简单,可以使用如下命令,并且运行结果如下:
运行分析
在实践代码中,使用二叉查找树的方法,向红黑树插入红节点,然后调用 rb_insert_color()
红黑树实际插入操作。开发者可以使用调试工具跟踪 rb_insert_color() 的调用过程。
附录
Data Structure Visualizations
红黑树与 2-3 树的关系
BiscuitOS Home
BiscuitOS Driver
BiscuitOS Kernel Build
Linux Kernel
Bootlin: Elixir Cross Referencer
搭建高效的 Linux 开发环境
赞赏一下吧 🙂