知识卡片

普通读书笔记卡 · 1292.f.1.a.5.d.2

黑叔叔用旋转消除冲突

理解等级:中级

插入冲突遇黑叔叔时,折线形先旋成直线形,再重新着色并反向旋转祖父;左右情形对称。旋转保留键序,着色保留黑高,修复后红红相邻消失。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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