知识卡片

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

空根由唯一孩子接替

理解等级:中级

合并可能令根节点变空。

此时删去空根,让它唯一的孩子成为新根,B 树高度减一;这是删除导致树高下降的方式,仍保持非空树根至少有一个键。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      In cases 2c and 3b, if node x is the root, it could end up having no keys. When this situation occurs, then x is deleted, and x’s only child x.c1 becomes the new root of the tree. This action decreases the height of the tree by one and preserves the property that the root of the tree contains at least one key (unless the tree is empty).

    参考来源

    - 位置:《算法导论(第4版)》第18章《B树》(OEBPS/chapter018.xhtml,文本字符[30000,40000))。 - 结论依据:原文明确根在合并后变空时由唯一孩子接替并降高。 - 原始内容:In cases 2c and 3b, if node x is the root, it could end up having no keys. When this situation occurs, then x is deleted, and x ’s only child x . c 1 becomes the new root of the tree. This action decreases the height of the tree by one and preserves the property that the root of the tree contains at least one key (unless the tree is empty).