知识卡片
树高决定基本操作成本
搜索树的查找、最小值、前驱、插入和删除都沿树上的路径操作,成本随树高 h 变化。平衡形态可到 O(log n),退化成链表则可能 O(n);讨论二叉搜索树的性能时,必须同时说明树形和高度条件。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
Basic operations on a binary search tree take time proportional to the height of the tree.
参考来源
- 位置:《算法导论(第4版)》第 12 章导言(`OEBPS/chapter012.xhtml`,文本字符 [0, 5000))。
- 结论依据:第 12 章导言逐项列出 SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE,并指出基本操作耗时与树高成正比;完全树为 Θ(log n),链形树为 Θ(n)。
- 原始内容:Basic operations on a binary search tree take time proportional to the height of the tree.