数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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 节点的一部分，则以递归方式调整和拆分树，并按排序顺序排列节点。
6000+ 次浏览
