红黑树 (二): 过渡 ---- 2-3 查找树
前言
上一篇中我们着重介绍了二叉查找树 (BST)，其是一种较为简单的符号表同时也是红黑树的基础，因此理解其特性与基本操作是非常有必要的。这一篇我们来讲一下从 BST 到 红黑树当中的一种过渡结构 2-3 查找树理解它能够极大的减小我们理解红黑树的难度，但要实现 2-3 查找树比起红黑树而言却更麻烦一下，因此本篇不会涉及代码我们从图文的角度出发来讲解这种过渡的数据结构。
笔者水平有限，文中如有错误请不吝指出。
BST 的问题
BST 虽然能够提供非常良好的查询性能，但前提是 key 值的插入是随机的，但如果在使用中插入的数据是部分有序的甚至完全有序的那么 BST 就会退化为一个链表(见下图)其优越的查询性能也就消失了。
上图中我们的原数据为 6,5,4,3,2,1 按照这样的顺序向 BST 中插入就会形成一颗非常高的树，而 BST 查询性能的好坏正取决于树的高度此时我们的性能就从对数级别降低到了线性级别。解决的方法就是通过树的平衡来降低树的高度使其保持在 lgN。而本篇的主角 2-3 查找树就能做到这一点。
2-3 查找树
结点定义
为了达到平衡的效果，我们在原来的 BST 结点的基础上引入一些灵活性，我们允许一个结点可以同时存放 2 个 key 值并拥有 三条子链接并将这种新的结点称为 3-结点，而原来 BST 中的结点我们就将它称为 2-结点，具体可看下面的定义:
- 2-结点：结点中含有一个键 (以及其对应的值) 和两条链接，左链接指向的 2-3 树中的所有的键都小于当前结点的键，右链接指向的 2-3 树中的所有的键都大于当前结点的键
- 3-结点：结点中含有两个键 (以及其对应的值) 和三条链接，左链接指向的 2-3 树中的所有的键都小于当前结点较小的键，中链接指向的 2-3 树中所有的键都大于当前结点较小的键而小于当前结点较大的键，右链接指向的 2-3 树中的所有的键都大与当前结点较大的键
- 与 BST 一样结点允许指向空链接且所有结点的 key 值不重复
上一节我们讨论了一下 BST 的问题主要来源于其无法在修改的过程中达到完美的平衡，而 2-3 查找树恰恰能做到这一点，因此 2-3 查找树从根结点到叶结点的距离都是相同的 (当然存在不平衡的 2-3 查找树但是本文重点讲述的完美平衡的 2-3 查找树，因此文中所提及的 2-3 查找树都是完美平衡的) 从而能够解决 BST 的问题提供稳定高效的查询操作，接下来就来看一下 2-3 查找树的具体工作流程。
查找
作为 BST 的扩展 2-3 从查找树的查找和 BST 几乎是同样的，唯一的同在于在 3-结点上我们的比较还会出现处于两个 key 之间的情况，但结合下图这依然非常好理解:
- 查找命中的情况
- 查找未命中的情况
插入
2-3 查找树的插入操作比起 BST 来的就要更复杂一些，因为其涉及到自平衡的问题，我会循序渐进的来讲述以帮助理解。
插入一个 2-结点的子节点
我们先来一个简单的情况，和 BST 的插入一样在 2-3 查找树中我们在插入之前需要先进行一轮查找以找到待插入的空结点的位置，而如果这次未命中的查找结束于一个 2-结点那么就很好处理，见下图:
向只含有一个 3-结点的树中插入新键
为了理解更普遍的插入情况，我们先来看一个特殊的简单情况向只含有一个 3-结点的树中插入新键，由于我们只有一个 3-结点，因此为了平衡我们没有空间在插入 2-结点了，因此我们只能将新的键插入到这个 3-结点中从而形成了形成了一个 4-结点，不过这时我们就可以进行操作让树变得重新平衡具体来说，我们将这个 4-结点分解为 3 个 2-结点，中间的结点变为根节点左边的变为左子结点而右边的则变为右子结点，在这个过程之后树的高度便增加了 1，具体见下图：
上图很直观的展示了向一个 3-结点插入 key 的过程，需要注意的是这不仅展示了 3-结点如何再平衡，也展示了 2-3 查找树的生长过程。
向一个父节点是 2-结点的 3-结点中插入新键
理解了上一节的情况我们再接着前进，这次我们不仅仅局限于根节点，我们想向叶子结点的 3-结点也插入一个新键，但前提条件的其父节点是 2-结点。在理解了上一节所述情况的基础上这个过程也非常好理解，我们将新键插入 3-结点之后会得到一个临时的 4-结点因此我们需要分解它，而其父节点正好是一个 2-结点，因此我们可以将 4-结点中间的键并入其父结点，而其余两个结点则变成俩个 2-结点，具体情况可见下图:
向父结点为 3-结点的 3-结点插入新键已经分解根节点
OK，经过前面两轮热身我们现在可以来看看更普遍的情况了，将本节的情况与 插入 2-结点的情况相结合就能得到完整的 2-3 查找树的插入操作。在上一节中我们看到在父节点为 2-结点的 3-结点中插入新键我们可以通过分解并将中间键并入 2-结点形成 3-结点来达到平衡，而如果父节点是 3-结点的情况又如何呢？其实本质来说是一样的，我们在分解了子 4-结点后父结点成为了 4-结点那么我们就继续将其分解，这样一路向上最后会到达根结点，如果根结点也成为了 4-结点那么我们就将其分解为 3 个 2-结点这样我们就保持了树的完美平衡，由于过程较长因此此处之间引用《算法》中的图来展示这个过程，左图中 4-结点一路向上分解直到遇到一个 2-结点停止，右图中根节点被分解为 3 个 2-结点从而让树的高度增加了1。
可以看到我们在 2-3 查找树中所做的所有插入操作所引起的结点变化都是局部的，而其不会影响整颗树的平衡，因此再变换完成后我们的 2-3查找树依然是完美平衡的，因此其能够提供非常良好的查询性能，我们的复杂度必然稳定在 O(lgN)。最后再引用《算法》中的原图来更完整的展现一些插入的过程以帮助理解：
结语
OK，作为红黑树的过渡 2-3 查找树的内容就差不多到这里了，这一篇中我们介绍了一种能够完美自平衡的查找树，通过引入 3-结点与结点分解的机制让我们能在插入过程中保存完美的平衡，如果能理解本篇所说的内容那么其实相当于就离完全理解红黑树不远了，因为我们可以将 2-3 查找树中的 3-结点替换为红黑树中的红结点(见下图)，而结点的分解操作可以替换为红黑树中让人一下摸不着头脑的旋转操作，具体内容请看下篇。
参考
《算法》第四版