2-3 树 - C++ 中的数据结构和算法
2-3 树是数据结构中的一种树，其中树的每个节点都是 2 节点
或 3 节点。它是具有 3 阶的特殊类型的 B 树。
树中的 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 个节点的一部分，则以递归方式调整和拆分树，按排序顺序排列节点。
