知识卡片
黑叔叔用旋转消除冲突
插入冲突遇黑叔叔时,折线形先旋成直线形,再重新着色并反向旋转祖父;左右情形对称。旋转保留键序,着色保留黑高,修复后红红相邻消失。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
In case 2, node z is a right child of its parent. A left rotation immediately transforms the situation into case 3
参考来源
- 位置:《算法导论(第4版)》第 13 章13.3 节(`OEBPS/chapter013.xhtml`,文本字符 [20000, 30000);图 13.6、Art_P440)。
- 结论依据:13.3 节情况 2 在叔黑且 z 为右孩子时左旋父节点,转成情况 3;情况 3 交换父、祖父颜色并右旋祖父,右侧镜像处理。
- 原始内容:In case 2, node z is a right child of its parent. A left rotation immediately transforms the situation into case 3