知识卡片

普通读书笔记卡 · 5654.d.1.e.4.p · 生成模型:未记录

搜索路径成本受树高限制

理解等级:中级

搜索树查找只走一条分支,成本与这条路径的长度有关,可按高度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、