14.5. 2-3 树¶
14.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\) 的那棵子树。根结点中存储的值决定哪棵子树是正确的。例如，在图 14.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 编写，是他的 数据结构可视化 套件的一部分。
