知识卡片
搜索路径成本受树高限制
搜索树查找只走一条分支,成本与这条路径的长度有关,可按高度h写O(h),不能仅因“只走一个分支”就推出O(log n)。树高受平衡维护限制时可得对数路径,退化成单链时仍是O(n)。
02865按已排序单词插入会不断向右延伸。原XHTML写的是2¹⁶个单词,即65536,纯文本“216”丢了上标;对比意图是六万多节点的长链与只有十几层的矮树,而不是216个单词。
随机插入可能改善典型形状,却仍可能抽到不利顺序,不能保证最坏只查约16项;原段这一说法过强。因此需要明确的平衡机制来提供高度约束,后续AVL正是为此。
160旋转恢复局部高度差从而维护总体路径界;局部高度平衡不等于完全二叉树形状,不能用146较强填满条件定义所有AVL。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
树必须是保持平衡的。回顾一下保持一棵树的平衡是指对于给定数量的结点,要使得树的高度尽可能短。保持二叉搜索树处于平衡的状态是非常重要的,因为这代表着我们查找的分支都不会特别长。 为了更进一步理解保持一棵二叉搜索树平衡的重要性,不妨考虑一下当一棵二叉搜索树变得越来越不平衡时的状态。如果是这样的话,查找一
- · 查看原书依据
AVL树。[1] AVL树(Adel'son-Vel'skii and Landis)是一种特殊类型的二叉树,它的每个结点都保存一份额外的信息:结点的平衡因子。结点的平衡因子是它的右子树高度减去它的左子树高度的结果(见图9-9)。当插入结点时,AVL树需要自我调整,使得所有结点的平衡因子保持为+1、
参考来源
- 位置:《算法精解:C语言描述》第9章《二叉搜索树介绍》(spine1297;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1264.html;u158-ch09-017)。
- 结论依据:158完整性能和平衡说明、02865图及原XHTML全部sup标记实读,分清O(h)、条件下对数和退化线性;不将随机输入冒充最坏保证。
- 原始内容:树必须是保持平衡的。回顾一下保持一棵树的平衡是指对于给定数量的结点,要使得树的高度尽可能短。保持二叉搜索树处于平衡的状态是非常重要的,因为这代表着我们查找的分支都不会特别长。 为了更进一步理解保持一棵二叉搜索树平衡的重要性,不妨考虑一下当一棵二叉搜索树变得越来越不平衡时的状态。如果是这样的话,查找一
- 位置:《算法精解:C语言描述》第9章《二叉搜索树的实现与分析》(spine1299;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1266.html;u160-ch09-017)。
- 结论依据:160旋转恢复局部高度差从而维护总体路径界;局部高度平衡不等于完全二叉树形状,不能用146较强填满条件定义所有AVL。
- 原始内容:AVL树。[1] AVL树(Adel'son-Vel'skii and Landis)是一种特殊类型的二叉树,它的每个结点都保存一份额外的信息:结点的平衡因子。结点的平衡因子是它的右子树高度减去它的左子树高度的结果(见图9-9)。当插入结点时,AVL树需要自我调整,使得所有结点的平衡因子保持为+1、