知识卡片

普通读书笔记卡 · 5654.d.1.e.1.a.1.a.1

折线失衡要先转孩子

理解等级:中级

当失衡路径朝同一方向延伸,单旋可以调整;若高子树的更高孩子朝反方向,形成折线,需要先旋转这个孩子,把形状变直,再旋转失衡根。

选择依据是失衡节点及较高侧孩子的平衡因子,不能只看根向哪边高。左偏且左孩子右偏采用先左后右,右偏且右孩子左偏采用先右后左;相等因子也要按代码条件正确处理。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号,来确定失衡节点 属于图7‑32 中的哪种情况。 表7‑3 四种旋转情况的选择条件 第7 章 树 hello‑algo.com 167 失衡节点的平衡因子 子

    参考来源

    - 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[10765,10875)) - 结论依据:实际rotate条件>=0/<=0及双旋图支持选择与边界。 - 原始内容:通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号,来确定失衡节点 属于图7‑32 中的哪种情况。 表7‑3 四种旋转情况的选择条件 第7 章 树 hello‑algo.com 167 失衡节点的平衡因子 子