知识卡片
搜索代价由树高约束
搜索树的比较次数取决于沿途节点数,即树高。递增顺序插入普通搜索树可能使它退化成单链,最坏查询仍为线性。平衡策略维持较小高度,以额外更新工作和可能的元数据换取对数级查找。
O(log n)描述增长尺度,不是对任意n恰好log₂n次比较。1024个节点的最小可能高度若按根为第一层计为11层;原文“只访问10个”不作精确最坏界。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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 非常不平衡的二叉树 这种退化了的情况看起来很像单链表,不仅失去了二叉树的优点,而且也要负担并未使用的左指针的额外成本。我们更希望二叉树最终看起来像图