2-3 树
本页面介绍 2-3 树。2-3 树是一种多路搜索树，是绝对平衡的树，其所有叶节点都处于同一层级上。2-3 树是 3 阶 B 树。
定义
2-3 树中的每一个节点都有两个孩子（称为 2 节点，2-node）或三个孩子（称为 3 节点，3-node)。
-
2 节点，有一个数据元素和两个孩子。只能有两个孩子或没有孩子，不能出现只有一个孩子的情况。如果 2 节点有孩子，左子树包含的元素小于 \(a\)，右子树包含的元素大于 \(a\)。
-
3 节点，有两个数据元素和三个孩子。只能有三个孩子或没有孩子，不能出现有一个孩子或有两个孩子的情况。如果 3 节点有孩子，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
-
4 节点，有三个数据元素。只会在操作树时暂时创建，而不会永久存储在树上。
2-3 树的叶节点不含有子节点，有一个或两个数据元素。
树 \(T\) 是一个 2-3 树，当且仅当以下表述之一成立：
- \(T\) 是空树。
- \(T\) 是一个 2 节点，并带有元素 \(a\)。如果 \(T\) 有左孩子 \(p\) 和右孩子 \(q\)，则：
- \(p\) 和 \(q\) 是相同高度的 2-3 树。
- \(a\) 大于 \(p\) 中的每个元素。
- \(a\) 小于 \(q\) 中的每个数据元素。
- \(T\) 是一个 3 节点，并带有数据元素 \(a\) 和 \(b\)，其中 \(a\) 小于 \(b\)。如果 \(T\) 有左孩子 \(p\)，中间孩子 \(q\) 和右孩子 \(r\)，则：
- \(p\)、\(q\) 和 \(r\) 是相等高度的 2-3 树。
- \(a\) 大于 \(p\) 中的每个数据元素且小于 \(q\) 中的每个数据元素。
- \(b\) 大于 \(q\) 中的每个数据元素且小于 \(r\) 中的每个数据元素。
性质
- 所有内部节点都是 2 节点或 3 节点。
- 所有叶节点都在同一层级上。
- 树上的所有数据都是按顺序保存的（多路搜索树的性质）。
操作
查找
由于 2-3 树上的元素是按一定顺序存储的，所以 2-3 树的查找与二叉搜索树类似。下面在树 \(T\) 中查找元素 \(d\)。
- 如果 2–3 树 \(T\) 为空，那么 \(d\) 肯定不在 \(T\) 中，查找结束。
- 假设 \(t\) 是 \(T\) 的根节点。
- 如果 \(t\) 是一个叶子节点：
- 如果 \(d\) 不在节点 \(t\) 中，那么 \(d\) 肯定不在整个树 \(T\) 中，查找结束。
- 如果 \(d\) 在节点 \(t\) 中，那么 \(d\) 在树 \(T\) 中，查找成功结束。
- 假设 \(t\) 是一个 "2 节点"，具有左子节点 \(p\) 和右子节点 \(q\)，\(a\) 是节点 \(t\) 中的数据元素。有以下三种情况：
- 如果 \(d\) 等于 \(a\)，那么找到 \(d\) 在树 \(T\) 中，查找成功结束。
- 如果 \(d\) 小于 \(a\)，将 \(T\) 设为子树 \(p\)，并回到步骤 2 继续查找。
- 如果 \(d\) 大于 \(a\)，将 \(T\) 设为子树 \(q\)，并回到步骤 2 继续查找。
- 假设 \(t\) 是一个 "3 节点"，具有左子节点 \(p\)、中间子节点 \(q\) 和右子节点 \(r\)，\(a\) 和 \(b\) 是节点 \(t\) 中的两个数据元素，满足 $a