← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 5654.d.1.e.4.e · 生成模型:未记录

树高约束不同于逐层填满

理解等级:中级

限制树高能减少根到深层节点的路径,但不同平衡方案允许不同形状。本书此节将前层满、叶子位于末两层的形状称为平衡,并进一步把末层从左填充称为“左平衡”;不能把这个较强填充条件套到所有平衡搜索树。

02839先填满上方层,再让最底层从左连续排列,对应常用的完全二叉树形状。NIST对完全二叉树的定义明确包含末层尽量靠左,而平衡树有不同方案和容许程度。完全二叉树、平衡树(2026-11-06核验)。

因此后文AVL按局部子树高度差维护,与堆使用的逐层从左填满是不同条件;不能据某层未填满就直接断言一棵搜索树不平衡。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      左平衡的。图9-4所示的就是一棵左平衡树。我们将在9.5节中看到关于平衡树的重要应用。在第10章中,我们将学习如何利用左平衡二叉树来帮助实现堆和优先级队列。 图 9-4 左平衡二叉树

    参考来源

    - 位置:《算法精解:C语言描述》第9章《树的平衡》(spine1286;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1253.html;u146-ch09-006)。 - 结论依据:146完整定义、02839整图实读,区分书内“左平衡”与标准完全二叉树词义,NIST原始术语页提供不同平衡方案的核验,不提前虚标AVL实现已读。 - 原始内容:左平衡的。图9-4所示的就是一棵左平衡树。我们将在9.5节中看到关于平衡树的重要应用。在第10章中,我们将学习如何利用左平衡二叉树来帮助实现堆和优先级队列。 图 9-4 左平衡二叉树