知识卡片
插入保持非满递归前提
插入到非满节点时,
- 叶子直接移位写入;
- 内部节点先选孩子,若孩子已满则拆分,再按提升的分隔键选择正确半边。
设树含 n 个键、最小度为 t。这个“递归进入前先保证孩子非满”的前提使算法只向下走一条高度为 O(log_t n) 的路径,每层至多常数次块访问,整体因而为 O(log_t n) 次 I/O。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.