知识卡片
树的高度影响路径成本
节点数相同时,分支分布均衡的树可保持较短根到叶路径,单侧延伸则退化成链状。沿单条路径查找的工作因而可能从对数高度变为线性高度。
必须说明算法是否利用树的额外性质,例如搜索树按比较选一侧;普通二叉树按值搜索可能仍要遍历全部节点。退化也不表示取根值等所有操作都变线性。
树章问答给出另一种构造路线:把互异输入排序,选中间元素作根,再递归构造左右区间,可建立初始高度较均衡的搜索树。它是一次性构造方法,不替代后续插删时的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 中,对于基本数据类型,== 用于对比两