知识卡片

普通读书笔记卡 · 3587.b.2.d.2 · 生成模型:未记录

搜索树成本取决于实际高度

理解等级:中级

二叉搜索树每步只进入一个子树,操作成本与树高度相关。平衡时高度可为O(log n);若键按顺序插入普通未平衡树,可能退化成单链,高度和一次操作均为O(n)。图中1到15顺序插入形成长链,而以8为根的另一插入顺序形成高度较小的树。

案例的跟踪器以地址为键,作者将慢速归因于树严重右倾;地址分配顺序与平衡策略共同影响形态,不能仅因“使用二叉树”就保证对数复杂度。书中一百万节点约20次比较是平衡树高度量级的说明,不是所有树和每次操作都恰好20次。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      没有做平衡处理,使得这棵树右倾到操作时间近似线性的程度,这种情况下更像是一个有序链表而不是一棵二叉树。想知道为什么吗,看看图1-2中的两棵二叉树。在a树中顺序插入数字1~15。它的根节点值为1,从根节点出发到达值为15的节点需要经过14个节点。b树插入了相同的数字,不过是按照这样的顺序:<8,4,1

    参考来源

    - 位置:《算法技术手册》第1章《如果需要,尽可能用实践检验》(spine1456;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1420.html;u018-ch01-003)。 - 结论依据:18全文和03133完整两树图实读;平衡条件与作者案例因果分开。 - 原始内容:没有做平衡处理,使得这棵树右倾到操作时间近似线性的程度,这种情况下更像是一个有序链表而不是一棵二叉树。想知道为什么吗,看看图1-2中的两棵二叉树。在a树中顺序插入数字1~15。它的根节点值为1,从根节点出发到达值为15的节点需要经过14个节点。b树插入了相同的数字,不过是按照这样的顺序:<8,4,1