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 个节点的一部分，则以递归方式调整和拆分树，按排序顺序排列节点。
以上是 2-3 树 - C++ 中的数据结构和算法 的全部内容， 来源链接： utcz.com/z/363262.html
