5. 2-3 树¶
5.1. 2-3 树¶
本节介绍一种称为 2-3 树的数据结构。 2-3 树不是二叉树，它的形状遵循以下定义：
一个结点包含一个或两个键。
每个内部结点要么有两个子结点（含一个键时）， 要么有三个子结点（含两个键时）。名字由此而来。
所有叶结点都在树的同一层，因此树始终保持高度平衡。
除了这些形状性质外，2-3 树还具有与 BST 类似的搜索树性质。 对每个结点，左子树中所有后代结点的值都小于第一个键的值， 而中间子树中的值大于等于第一个键的值。 如果存在右子树（等价地，如果结点存储了两个键）， 则中间子树中所有后代的值小于第二个键的值， 右子树中的值大于等于第二个键的值。 维持这些形状和查找性质，要求在插入和删除结点时采取特殊动作。 2-3 树相对 BST 的优势在于：它能以相对较低的代价保持高度平衡。 下面是一棵 2-3 树的例子。
结点显示为带有两个键字段的矩形框。 （这些结点实际上会包含完整记录或指向完整记录的指针， 但图中只画出键。） 只有两个子结点的内部结点，其右侧键字段为空。 叶结点可能包含一个或两个键。 下面是 2-3 树结点类的一种实现。
// 2-3 tree node implementation
class TTNode<Key extends Comparable<? super Key>,E> {
private E lval; // The left record
private Key lkey; // The node's left key
private E rval; // The right record
private Key rkey; // The node's right key
private TTNode<Key,E> left; // Pointer to left child
private TTNode<Key,E> center; // Pointer to middle child
private TTNode<Key,E> right; // Pointer to right child
public TTNode() { center = left = right = null; }
public TTNode(Key lk, E lv, Key rk, E rv,
TTNode<Key,E> p1, TTNode<Key,E> p2,
TTNode<Key,E> p3) {
lkey = lk; rkey = rk;
lval = lv; rval = rv;
left = p1; center = p2; right = p3;
}
public boolean isLeaf() { return left == null; }
public TTNode<Key,E> lchild() { return left; }
public TTNode<Key,E> rchild() { return right; }
public TTNode<Key,E> cchild() { return center; }
public Key lkey() { return lkey; } // Left key
public E lval() { return lval; } // Left value
public Key rkey() { return rkey; } // Right key
public E rval() { return rval; } // Right value
public void setLeft(Key k, E e) { lkey = k; lval = e; }
public void setRight(Key k, E e) { rkey = k; rval = e; }
public void setLeftChild(TTNode<Key,E> it) { left = it; }
public void setCenterChild(TTNode<Key,E> it)
{ center = it; }
public void setRightChild(TTNode<Key,E> it)
{ right = it; }
}
注意，这份示例声明没有区分叶结点和内部结点，因此空间效率 不高，因为每个叶结点都存储了三个指针。 我们可以用 类层次 来实现相互独立的内部结点和叶结点类型。
从 2-3 树的定义规则出发，可以推导出树的结点数与树的深度之间 的关系。 高度为 \(k\) 的 2-3 树至少有 \(2^{k-1}\) 个叶结点， 因为当每个内部结点都只有两个子结点时，它会退化为完全二叉树的 形状。 高度为 \(k\) 的 2-3 树至多有 \(3^{k-1}\) 个叶结点， 因为每个内部结点至多有三个子结点。
在 2-3 树中查找一个值与在 BST 中查找类似。 查找从根开始。 若根不包含查找键 \(K\)，则查找进入唯一可能包含 \(K\) 的那棵子树。 根结点中存储的值决定哪棵子树是正确的。 例如，在图 17.5.1 的树中查找值 30， 我们从根结点开始。 因为 30 介于 18 与 33 之间，它只可能在中间子树中。 查找根结点的中间子结点即可得到想要的记录。 如果查找 15，第一步同样是查找根结点。 因为 15 小于 18，所以走第一个（左）分支。 在下一层，走第二个分支到达包含 15 的叶结点。 如果查找键是 16，那么在遇到包含 15 的叶结点时就会发现 查找键不在树中。 下面是 2-3 树查找方法的一种实现。
private E findhelp(TTNode<Key,E> root, Key k) {
if (root == null) { return null; } // val not found
if (k.compareTo(root.lkey()) == 0) { return root.lval(); }
if ((root.rkey() != null) && (k.compareTo(root.rkey())
== 0))
{ return root.rval(); }
if (k.compareTo(root.lkey()) < 0) { // Search left
return findhelp(root.lchild(), k);
}
else if (root.rkey() == null) { // Search center
return findhelp(root.cchild(), k);
}
else if (k.compareTo(root.rkey()) < 0) { // Search center
return findhelp(root.cchild(), k);
}
else { return findhelp(root.rchild(), k); } // Search right
}
向 2-3 树插入与向 BST 插入在某种程度上类似：新记录会被放到 合适的叶结点中。 与 BST 插入不同的是，不会为被插入的记录创建新的子结点， 也就是说，2-3 树不向下生长。 第一步是找到若该记录在树中时将包含它的那个叶结点。 如果这个叶结点只包含一个值，那么新记录可以直接加入该结点， 无需对树做进一步修改，如下面的可视化所示。
如果我们把新记录插入到一个已包含两条记录的叶结点 \(L\) 中，就必须创建更多空间。 考虑结点 \(L\) 的两条记录与待插入的记录，不必在意哪两条 原本就在 \(L\) 中、哪条是新记录。 第一步是把 \(L\) 分裂成两个结点。 为此，必须从空闲存储中创建一个新结点—记为 \(L'\)—。 \(L\) 获得三个键值中最小的那条记录， \(L'\) 获得最大的那条。 三个键值居中的那条记录连同指向 \(L'\) 的指针一起 被上传到父结点。 这称为一次 提升。 被提升的键随后插入父结点。 如果父结点当前只包含一条记录（因此只有两个子结点）， 那么只需把被提升的记录和指向 \(L'\) 的指针加入父结点。 如果父结点已满，则重复"分裂并提升"的过程。 下面是一个简单提升的例子。
这张幻灯片展示了当提升导致根分裂、为树增加一层时会发生什么。 注意，所有叶结点的深度始终相等。
下面是插入过程的一种实现。
private TTNode<Key,E> inserthelp(TTNode<Key,E> rt, Key k, E e) {
TTNode<Key,E> retval;
if (rt == null) {// Empty tree: create a leaf node for root
return new TTNode<Key,E>(k, e, null, null, null, null, null);
}
if (rt.isLeaf()) { // At leaf node: insert here
return rt.add(new TTNode<Key,E>(k, e, null, null, null, null, null));
}
// Add to internal node
if (k.compareTo(rt.lkey()) < 0) { // Insert left
retval = inserthelp(rt.lchild(), k, e);
if (retval == rt.lchild()) { return rt; }
else { return rt.add(retval); }
}
else if((rt.rkey() == null) || (k.compareTo(rt.rkey()) < 0)) {
retval = inserthelp(rt.cchild(), k, e);
if (retval == rt.cchild()) { return rt; }
else { return rt.add(retval); }
}
else { // Insert right
retval = inserthelp(rt.rchild(), k, e);
if (retval == rt.rchild()) { return rt; }
else { return rt.add(retval); }
}
}
// Add a new key/value pair to the node. There might be a subtree
// associated with the record being added. This information comes
// in the form of a 2-3 tree node with one key and a (possibly null)
// subtree through the center pointer field.
public TTNode<Key,E> add(TTNode<Key,E> it) {
if (rkey == null) { // Only one key, add here
if (lkey.compareTo(it.lkey()) < 0) {
rkey = it.lkey(); rval = it.lval();
center = it.lchild(); right = it.cchild();
}
else {
rkey = lkey; rval = lval; right = center;
lkey = it.lkey(); lval = it.lval();
center = it.cchild();
}
return this;
}
else if (lkey.compareTo(it.lkey()) >= 0) { // Add left
TTNode<Key,E> N1 = new TTNode<Key,E>(lkey, lval, null, null, it, this, null);
it.setLeftChild(left);
left = center; center = right; right = null;
lkey = rkey; lval = rval; rkey = null; rval = null;
return N1;
}
else if (rkey.compareTo(it.lkey()) >= 0) { // Add center
it.setCenterChild(new TTNode<Key,E>(rkey, rval, null, null, it.cchild(), right, null));
it.setLeftChild(this);
rkey = null; rval = null; right = null;
return it;
}
else { // Add right
TTNode<Key,E> N1 = new TTNode<Key,E>(rkey, rval, null, null, this, it, null);
it.setLeftChild(right);
right = null; rkey = null; rval = null;
return N1;
}
}
注意 inserthelp 接受三个参数。
第一个是指向当前子树根的指针，名为 rt 。
第二个是要插入记录的键，第三个是记录本身。
inserthelp 的返回值是指向 2-3 树结点的指针。
如果 rt 未变，则返回指向 rt 的指针。
如果 rt 发生了变化（插入导致结点分裂），
则返回指向新子树根的指针，键值和记录值位于最左侧字段，
（单个）子树的指针位于中间指针字段。
随后，这个修改过的结点会被加入父结点，如上面的分裂可视化
所示。
从 2-3 树中删除记录时，有三种情况需要考虑。 最简单的情况是：要从包含两条记录的叶结点中移除一条记录。 此时只需移除该记录，其他结点不受影响。 第二种情况是：要移除的是叶结点中唯一的记录。 第三种情况是：要从内部结点中移除一条记录。 在第二种和第三种情况中，被删除的记录都要由另一条能顶替它、 且保持正确次序的记录来代替，这与从 BST 中移除结点类似。 如果树足够稀疏，就可能找不到这样的记录，使所有结点仍能维持 至少一条记录。 这时就要合并兄弟结点。 2-3 树的删除操作过于复杂，这里不再进一步描述。 完整的删除讨论将推迟到下一节，在那里可以针对 B 树的一个特定 变体进行推广。
2-3 树的插入和删除例程并不在树的底部添加新结点。 它们让叶结点分裂或合并，可能引发向上传播到根的连锁效应。 必要时根会分裂，创建新的根结点，使树加深一层。 删除时，若根的最后两个子结点合并， 则移除根结点，树就少了一层。 无论哪种情况，所有叶结点始终在同一层。 当所有叶结点都在同一层时，我们称树是 高度平衡 的。 由于 2-3 树是高度平衡的，且每个内部结点至少有两个子结点， 可知树的最大深度是 \(\log n\)。 因此，2-3 树的插入、查找和删除操作都需要 \(\Theta(\log n)\) 时间。
点击这里 是另一个可视化，可以让你构建并与 2-3 树交互。 实际上，这个可视化展示的数据结构比 2-3 树更一般。 要看 2-3 树的行为，请务必使用"Max Degree = 3"设置。 该可视化由旧金山大学的 David Galles 编写， 是他的 数据结构可视化 套件的一部分。
