Github: 插入一个红节点引起右旋转
Email: BuddyZhang1 buddy.zhang@aliyun.com
目录
红黑树插入一个红节点引起右旋转原理
对结点 S 做右旋操作时,假设其左孩子为 E 而不是T.nil, 以 S 到 E 的链为 “支轴” 进
行。使 E 成为该子树新的根结点, S 成为 E 的右孩子,E 的右孩子成为 S 的左孩子。
如上图,当插入 4 之后,红黑树 5 节点需要进行右旋达到平衡,那么以 5 到 6 的链为
“支轴” 进行。使用 5 节点成为新的根节点, 6 成为 5 的右孩子,4 称为 5 的左
孩子。如下图:
核心代码实现
为了实现右旋操作,参考内核中的实现进行分析,位于 lib/rbtree.c 文件中,关于右旋的
实现如下:
核心代码首先判断 gparent (gparent 为 parent 的父节点) 的左孩子是否存在,对于需要右
旋的部分,gparent 的左孩子是存在的。接着按照右旋的原理,以 gparent 节点到 parent 节
点为支轴进行右旋。此时 parent 的右孩子变成了 gparent 的左孩子,对应的代码就是:
“gparent->rb_left = tmp”, gparent 自己变成了 parent 的右孩子, 对应的代码就是:
“parent->rb_right = gparent”。如果此时 tmp 存在,也就是原先 parent 的右孩子存在,
那么,设置 tmp 的父节点为 gparent。接着调用 __rb_rotate_set_parents() 函数修改
gparent 和 parent 之间的关系,代码如下:
首先获得 gparent 的父节点,然后将 parent 在红黑树 __rb_parent_color 成员继承
gparent 的 __rb_parent_color. 然后设置 gparent 的 __rb_parent_color 为
parent。最后修改 gparent 原先的父节点的节点信息,函数如下:
逻辑很简单,就是判断 gpraent 是原始父节点的左孩子还是右孩子,然后将原始父节点的
左孩子或右孩子指向 parent 节点。如果 gparent 的父节点不存在,那么 gparent 原先是
root 节点,那么就将 root 节点指向 parent 节点。
通过上面的源码,rbtree 已经完成右旋操作,并设置好了各个节点之间的关系,使红黑树再一次
达到平衡。
红黑树插入一个红节点引起右旋转与 2-3 树的关系
毕竟红黑树是 2-3 树的一种表现形式,因此插入一个红节点到引起红黑树右旋转的原理也符合 2-3 树
的原理。当插入一个红节点之后,父节点此时已经是一个 3- 节点,向最左边插入红节点的时候,父
节点已经变成一个零时的 4- 节点,此时需要对 2-3 树进行分裂操作,将 4- 节点中,中间节点
提取,将一个 4- 节点拆分成 3 个 2- 节点,由于提取之后的节点需要向上融合,因此需要将该节点
设置为 RED,而子节点都是 2- 节点,因此子节点的颜色都是 BLACK。在分裂过程中,由于新增加
的红节点从最左边插入,因此在分裂的时候,零时 4- 节点的最右侧的两个孩子归 4- 节点最右节点
所有,这样就完成了一次 2-3 树的提取,分离,合并操作,对应到红黑树就是一次右旋转操作。
如上图,在 2-3 树中,当向一个 3- (n0:R|p0:B) 节点的左边插入一个红节点 n1,此时变成一个
零时的 4- (n1:R|n0:R|p0:B) 节点,此时需要进行分离,将 n0:R 节点向上提取,由于要和
上一层节点进行融合,那么需要将 n0 节点变成红色,但由于上图中父节点已经是根节点了,所有
将 n0 设置为黑色,n1 继续保持红色,n1 与 n0 同时构成一个 3- 节点。由于分裂,n0 的右孩子
成为了 p0 的左孩子。p0 自己成为了 n0 的右孩子。对应的红黑树如右边。更多红黑树与 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 开发环境
赞赏一下吧 🙂