知识卡片
树高决定搜索路径上界
搜索树一次查找沿根到叶的路径进行,成本受树高控制。保持适当平衡时高度为 O(log n),有序插入却可能使未平衡搜索树退化为 O(n) 的长链。原书随机插入并未实现旋转或其他平衡维护;随机输入不是平衡保证。键比较自身的成本也需计入总时间。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.3.2 二叉树的优点 · 查看原书依据
如果一个二叉树是平衡的,它的查找、插入、删除操作需要 log(n) 步,这里的 n 是树上元素的总数量。此外,平衡二叉树的高度约为 log2(n),这意味着一个拥有 10,000 个元素的平衡树的高度大约是 14。类似的,拥有 100,000 个元素的平衡树的高度大约是 17,拥有 1,000,00
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.3.2 二叉树的优点,spine083(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.3.2.html)。
- 结论依据:原文比较有序与随机插入,并说明平衡树的对数高度;与前页无平衡代码对应。
- 原始内容:如果一个二叉树是平衡的,它的查找、插入、删除操作需要 log(n) 步,这里的 n 是树上元素的总数量。此外,平衡二叉树的高度约为 log2(n),这意味着一个拥有 10,000 个元素的平衡树的高度大约是 14。类似的,拥有 100,000 个元素的平衡树的高度大约是 17,拥有 1,000,00