算法—2

1.基本思想

为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切地说，我们将一棵标准的二叉查找树中的结点称为2-结点（含有一个键和两条链接），而现在我们引入3-结点，它含有两个键和三条链接。2-结点和3-结点中的每条链接都对应着其中保存的键所分割产生的一个区间。

一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。简洁起见，这里我们用2-3树指代一棵完美平衡的2-3查找树（在其他情况下这个词应该表示一种更一般的结构）。现在先假设我们已经能够自如地操作它们并来看看应该如何将它们用作查找树。

1.1 查找

将二叉查找树的查找算法一般化我们就能够直接得到2-3树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。具体查找过程如下图所示。

1.2 向2-结点中插入新键

要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用2-3树的主要原因就在于它能够在插入后继续保持平衡。如果未命中的查找结束于一个2-结点，事情就好办了：我们只要把这个2-结点替换为一个3-结点，将要插入的键保存在其中即可（如下图所示）。如果未命中的查找结束于一个3-结点，事情就要麻烦一些。

1.3 向一棵只含有一个3-结点的树中插入新键

在考虑一般情况之前，先假设我们需要向一棵只含有一个3-结点的树中插入一个新键。这棵树中有两个键，所以在它唯一的结点中已经没有可插入新键的空间了。为了将新键插入，我们先临时将新键存入该结点中，使之成为一个4-结点。它很自然地扩展了以前的结点并含有3个键和4条链接。创建一个4-结点很方便，因为很容易将它转换为一棵由3个2-结点组成的2-3树，其中一个结点（根）含有中键，一个结点含有3个键中的最小者（和根结点的左链接相连），一个结点含有3个键中的最大者（和根结点的右链接相连）。这棵树既是一棵含有3个结点的二叉查找树，同时也是一棵完美平衡的2-3树，因为其中所有的空链接到根结点的距离都相等。插入前树的高度为0，插入后树的高度为1。如下图所示。

1.4 向一个父结点为2-结点的3-结点中插入新键

假设未命中的查找结束于一个3-结点，而它的父结点是一个2-结点。在这种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。我们先像刚才一样构造一个临时的4-结点并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动至原来的父结点中。你可以将这次转换看成将指向原3-结点的一条链接替换为新父结点中的原中键左右两边的两条链接，并分别指向两个新的2-结点。根据我们的假设，父结点中是有空间的：父结点是一个2-结点（一个键两条链接），插入之后变为了一个3-结点（两个键3条链接）。另外，这次转换也并不影响（完美平衡的）2-3树的主要性质。树仍然是有序的，因为中键被移动到父结点中去了；树仍然是完美平衡的，插入后所有的空链接到根结点的距离仍然相同。请确认你完全理解了这次转换——它是2-3树的动态变化的核心，其过程如下图所示。

1.5 向一个父结点为3-结点的3-结点中插入新键

现在假设未命中的查找结束于一个父结点为3-结点的结点。我们再次和刚才一样构造一个临时的4-结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3-结点，因此我们再用这个中键构造一个新的临时4-结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父结点中去。推广到一般情况，我们就这样一直向上不断分解临时的4-结点并将中键插入更高层的父结点，直至遇到一个2-结点并将它替换为一个不需要继续分解的3-结点，或者是到达3-结点的根。该过程如下图所示。

1.6 分解根结点

如果从插入结点到根结点的路径上全都是3-结点，我们的根结点最终变成一个临时的4-结点。此时我们可以按照向一棵只有一个3-结点的树中插入新键的方法处理这个问题。我们将临时的4-结点分解为3个2-结点，使得树高加1，如下图所示。请注意，这次最后的变换仍然保持了树的完美平衡性，因为它变换的是根结点。

1.7 局部变换

1.8 全局性质

原标题：算法—2

关键词：