知识卡片

普通读书笔记卡 · 5579.a

搜索代价由树高约束

理解等级:初级

搜索树的比较次数取决于沿途节点数,即树高。递增顺序插入普通搜索树可能使它退化成单链,最坏查询仍为线性。平衡策略维持较小高度,以额外更新工作和可能的元数据换取对数级查找。

O(log n)描述增长尺度,不是对任意n恰好log₂n次比较。1024个节点的最小可能高度若按根为第一层计为11层;原文“只访问10个”不作精确最坏界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 7.11 层次数据结构 · 查看原书依据

      你可能已经注意到,树的排列依赖于插入顺序。图7-27展示了按顺序4、5、6、8、9插入数字的情况。 图7-27 非常不平衡的二叉树 这种退化了的情况看起来很像单链表,不仅失去了二叉树的优点,而且也要负担并未使用的左指针的额外成本。我们更希望二叉树最终看起来像图

    参考来源

    - 位置:《计算机系统解密》7.11 层次数据结构(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0078.html) - 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。 - 原始内容:你可能已经注意到,树的排列依赖于插入顺序。图7-27展示了按顺序4、5、6、8、9插入数字的情况。 图7-27 非常不平衡的二叉树 这种退化了的情况看起来很像单链表,不仅失去了二叉树的优点,而且也要负担并未使用的左指针的额外成本。我们更希望二叉树最终看起来像图