3

我有两本书的数据结构。在两本书中，有两种不同的 B-Tree 插入方法：

假设我想在 B 树中插入一个值 k。在搜索适当的叶节点以插入值 k 之后，计算特定叶节点中存在的值。如果叶节点已满，则：

1.从叶子元素和新元素中选择一个中值。然后将节点分成两个节点。中值转移到父节点。

2.在m/2-1（m为树的顺序）位置后将节点拆分为两个节点。中值移动到父节点。然后将值插入到适当的位置。

以下哪种方法是正确的？

另一个问题：

对于 n 阶 B-Tree，节点必须包含的最小键数是多少？我已经搜索了互联网和书籍，但无法获得确切的等式，通过它我可以找出最小的键数：例如，如果order=5 那么任何节点（root 除外）的最小键数为 2。这是怎么来的？

任何答案将不胜感激！

4

1 回答 1

7

根据 Knuth 的定义，m 阶 B-tree 是一棵满足以下性质的树：

  • 每个节点最多有 m 个子节点。
  • 每个非叶节点（根节点除外）至少有 ceil(m⁄2) 个子节点。
  • 如果根不是叶节点，则根至少有两个子节点。
  • 具有 k 个子节点的非叶节点包含 k-1 个键。
  • 所有叶子都出现在同一级别，并携带信息。

每个内部节点的键充当分割其子树的分隔值。例如，如果一个内部节点有 3 个子节点（或子树），那么它必须有 2 个键：a1 和 a2。最左子树中的所有值都小于 a1，中间子树中的所有值都在 a1 和 a2 之间，最右子树中的所有值都大于 a2。

内部节点

内部节点是除叶节点和根节点之外的所有节点。它们通常表示为一组有序的元素和子指针。每个内部节点包含最多 U 个子节点和最少 L 个子节点。因此，元素的数量总是比子指针的数量少 1（元素的数量在 L-1 和 U-1 之间）。U 必须是 2L 或 2L-1；因此每个内部节点至少是半满的。U 和 L 之间的关系意味着两个半满节点可以连接成一个合法节点，一个完整节点可以分成两个合法节点（如果有空间将一个元素向上推入父节点）。这些属性使删除和插入新值到 B-tree 和调整树以保留 B-tree 属性成为可能。

根节点

根节点的子节点数量与内部节点的上限相同，但没有下限。例如，当整个树中的元素少于 L−1 个时，根将是树中唯一的节点，根本没有子节点。

叶节点

叶节点对元素的数量有相同的限制，但没有子节点，也没有子指针。

http://en.wikipedia.org/wiki/B-Tree

添加：

使用 Knuths 定义的 5 阶 B 树（最大子节点数）[4 将是最大键数]。

拆分后内部节点的最小子节点数为 3 [2 个键]。因为一个节点在溢出 B-Tree 的顺序时会分裂。

列表 11108、3267、11357、12080、6092 的 B 树

添加3267、11108、11357、12080后；这是显示钥匙，而不是孩子。

└── 3267, 11108, 11357, 12080

然后加6092；这是显示钥匙，而不是孩子。

拆分前（键数 > order-1）[5 > 5-1=4]：

└── 3267, 6092, 11108, 11357, 12080

拆分后：

└── 11108
    ├── 3267, 6092
    └── 11357, 12080

注意：根节点没有其他节点的最小键/子节点数。

删除：

删除后重新平衡

如果从叶节点中删除一个元素使其低于最小大小，则必须重新分配一些元素以使所有节点达到最小值。在某些情况下，重新排列会将缺陷转移到父级，并且重新分配必须迭代地应用到树上，甚至可能应用到根。由于最小元素计数不适用于根，因此使根成为唯一的缺陷节点不是问题。重新平衡树的算法如下：[需要引用]

  1. 如果右兄弟的元素数量超过最小数量

    • 将分隔符添加到缺陷节点的末尾
    • 用右兄弟的第一个元素替换父中的分隔符
    • 将右兄弟的第一个孩子附加为缺陷节点的最后一个孩子

  2. 否则，如果左兄弟元素的数量超过最小数量

    • 将分隔符添加到缺陷节点的开头
    • 用左兄弟的最后一个元素替换父中的分隔符
    • 插入左兄弟的最后一个孩子作为缺陷节点的第一个孩子

  3. 如果两个直接兄弟姐妹只有最少数量的元素

    • 创建一个新节点，其中包含缺陷节点中的所有元素、其一个兄弟节点中的所有元素以及两个组合兄弟节点之间的父节点中的分隔符
    • 从父节点中移除分隔符，并将其分隔的两个子节点替换为组合节点
    • 如果这使父节点中的元素数量低于最小值，则对有缺陷的节点重复这些步骤，除非它是根，因为允许根有缺陷

唯一需要考虑的另一种情况是根没有元素和一个孩子。在这种情况下，将其替换为唯一的孩子就足够了。

预删除节点 9062。

└── 6169, 12789
    ├── 1009, 4238, 5139
    ├── 6625, 9062
    └── 12909, 14508, 14703, 14985

平衡前

└── 6169, 12789
    ├── 1009, 4238, 5139
    ├── 6625 
    └── 12909, 14508, 14703, 14985

平衡后

└── 6169, 12909
    ├── 1009, 4238, 5139
    ├── 6625, 12789
    └── 14508, 14703, 14985

如您所见，中间节点子节点从其父节点借了 12789 以满足最低要求，父节点从其最右边的子节点借了 12909 以满足其最低要求。

于 2013-02-23T13:32:16.093 回答