知识卡片

普通读书笔记卡 · 3633.a.8.b.1.a

插入保持非满递归前提

理解等级:高级

插入到非满节点时,

  • 叶子直接移位写入;
  • 内部节点先选孩子,若孩子已满则拆分,再按提升的分隔键选择正确半边。

设树含 n 个键、最小度为 t。这个“递归进入前先保证孩子非满”的前提使算法只向下走一条高度为 O(log_t n) 的路径,每层至多常数次块访问,整体因而为 O(log_t n) 次 I/O。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第18章 B树 · 查看原书依据

      Line 13 detects whether the recursion would descend to a full child, in which case line 14 calls B-TREE-SPLIT-CHILD to split that child into two nonfull children, and lines 15–16 determine which of the two children is the correct one to descend to.

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[20000,30000))。 - 结论依据:原文逐行说明选择子节点、预拆满孩子和复杂度界。 - 原始内容:Line 13 detects whether the recursion would descend to a full child, in which case line 14 calls B-T REE -S PLIT -C HILD to split that child into two nonfull children, and lines 15–16 determine which of the two children is the correct one to descend to.