知识卡片

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

树的高度影响路径成本

理解等级:中级

节点数相同时,分支分布均衡的树可保持较短根到叶路径,单侧延伸则退化成链状。沿单条路径查找的工作因而可能从对数高度变为线性高度。

必须说明算法是否利用树的额外性质,例如搜索树按比较选一侧;普通二叉树按值搜索可能仍要遍历全部节点。退化也不表示取根值等所有操作都变线性。

树章问答给出另一种构造路线:把互异输入排序,选中间元素作根,再递归构造左右区间,可建立初始高度较均衡的搜索树。它是一次性构造方法,不替代后续插删时的AVL式持续维护;排序与建树成本也应分别计入。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      当所 有节点都偏向一侧时,二叉树退化为“链表” 。 ‧ 完美二叉树是理想情况,可以充分发挥二叉树“分治”的优势。 ‧ 链表则是另一个极端,各项操作都变为线性操作,时间复杂度退化至 。 图7‑8 二叉树的最佳结构与最差结构

    • · 查看原书依据

      将输入数据排序,然后将中点元素作为根节点,再递归地构建左右子树。这样做可以最大程度保证树的平衡 性。 Q:在Java 中,字符串对比是否一定要用equals() 方法? 在Java 中,对于基本数据类型,== 用于对比两

    参考来源

    - 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[31538,31648)) - 结论依据:实际退化图与表,限定路径型操作不照抄所有操作线性。 - 原始内容:当所 有节点都偏向一侧时,二叉树退化为“链表” 。 ‧ 完美二叉树是理想情况,可以充分发挥二叉树“分治”的优势。 ‧ 链表则是另一个极端,各项操作都变为线性操作,时间复杂度退化至 。 图7‑8 二叉树的最佳结构与最差结构 补充原书证据:spine 3 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;归一字符[15084,15194)。 - 结论依据:该构建问答此前只在单元去向里归组,现将实际方法明确并入高度与形状卡,而非仅引用空泛去向。 - 原始内容:将输入数据排序,然后将中点元素作为根节点,再递归地构建左右子树。这样做可以最大程度保证树的平衡 性。 Q:在Java 中,字符串对比是否一定要用equals() 方法? 在Java 中,对于基本数据类型,== 用于对比两