2-3 树 - C++ 中的数据结构和算法

2-3 树是数据结构中的一种树，其中树的每个节点都是 2 节点

或 3 个节点。它是一种特殊类型的3 阶B-Tree。

树中的 2 节点是具有一个数据部分和两个子节点的节点。

树中的 3 节点是具有两个数据部分和三个子节点的节点。

图：- 2-3 树

2-3 树的属性：-

• 每个内部节点要么是 2 节点，要么是 3 节点。

• 包含一个数据部分的节点可以是正好有 2 个子节点的 2 节点，也可以是没有子节点的叶节点。

• 包含两个数据部分的节点只能是具有正好 3 个子节点的 3 节点。

• 所有叶节点始终处于同一级别。

• 2-3 树始终是高度平衡的树。

• 搜索操作在 2-3 树中快速高效。

2节点：-

• 正好是两个孩子。

• 左孩子体重较轻。

• 右孩子体重更大。

• 可以是没有子节点的叶节点。

3节点：-

• 正好三个孩子。

• 2 个数据值。

• 左孩子的权重小于左数据值。

• 体重介于两个数据值之间的中间孩子。

• 权重大于右数据值的右孩子。

• 永远不能是叶节点。

2-3 树中的操作：-

1. 在 2-3 树中搜索

• 类似于对数据进行排序时的二叉搜索树中的搜索操作。

• 在 2-3 树中搜索 X。

• 如果树为空 → 返回 False

• 如果我们到达根节点，则返回 False（未找到）

• 如果 X 小于左数据部分，则搜索左子树

• 如果 X 大于左侧数据且大于右侧数据，则搜索中间子树。

• 如果 X 大于右数据部分，则搜索右子树。

2.在2-3树中插入一个节点

• 在 2-3 树中插入 X。

• 如果树为空→将 X 添加为根。

• 搜索 X 的正确位置并将其添加为叶节点。

• 如果有一个叶子节点有一个数据部分，则添加 X 和叶子节点成为 2 - 节点。

• 如果叶子节点有两个数据部分，则添加X。拆分临时3-节点，并根据排序顺序将数据移动到父节点。

制作2-3棵树并依次添加节点→10、5、8、15、23、21

3.删除2-3树中的一个节点

• 删除 2-3 树中的 X。

• 如果树为空，则返回 false。

• 搜索 X 的位置并将其删除，然后调整树。

• 如果 X 是 3 个节点的一部分，则删除 X 并调整左值和中间值。如有必要，还可以调整节点的祖先的左值和中值。

• 如果 X 是 2 个节点的一部分，则以递归方式调整和拆分树，按排序顺序排列节点。