4.设3序(阶) B ﹣树,从空树开始,按序列(20, 50, 52 60,68,70}顺序 依次插入关键码,画出得到的 B ﹣树:在得到的 B ﹣树中删除50和68,画出每一次删除后的 B ﹣树。
时间: 2024-11-18 13:18:03 浏览: 29
首先,我们来看如何构建一个3阶B-树。初始为空的B-树可以逐次接收给定的关键码并按照B-树的性质进行插入。
1. 插入20时,因为是根节点,直接插入:
- 根节点(只有一个key和两个分枝): [20]
2. 接着插入50,根节点达到满度(3个key),需要分裂成两个子节点,中间插入50:
- 根节点: [20, 50, NULL]
- 左子节点: [20] (分裂后)
- 右子节点: [NULL]
3. 再插入52,右子节点不满,所以直接插入:
- 根节点: [20, 50, 52, NULL]
4. 由于后续插入的都是大于50的数,先插入60,此时根节点左子节点已满,分裂成两部分,将60放在最右侧:
- 根节点: [20, NULL, 52, 60]
- 左子节点: [50] (分裂后)
- 右子节点: [NULL]
5. 68插入时,同样放到右子节点(分裂后):
- 根节点: [20, NULL, 52, 60, 68]
- 左子节点: [50]
- 右子节点: [68]
6. 最后,70插入,根节点右子节点满了,再次分裂:
- 根节点: [20, NULL, 52, 60, 68, 70]
- 左子节点: [50, 60] (分裂后)
- 右子节点: [68]
现在,这个B-树的样子就是这样的:
```
20
/ \
50 52
\ / \
NULL 60
\
68
\
70
```
接下来是删除过程:
1. 删除50时,先找到50所在的路径,这里是右子树的根,会合并两个子树:
- 新根节点: [20, 52, 60, 68, 70]
- 左子节点: [50, 60] 合并后
2. 删除68时,类似地找到68所在位置,然后左子树分裂:
- 新根节点: [20, 52, 60, 70]
- 左子节点: [50, 60, 68] 合并后,右子节点: [NULL]
最终得到的B-树在删除这两个键之后是这样的:
```
20
/ \
50 52
\ /
60 70
\
68
```
阅读全文