小引——2-3树

二叉查找树中，每个结点上有一个键和两个链接，我们称这种结点为2-结点。所以，有着两个键和三个链接的结点我们称之为3-结点。由2-结点和3-结点构成的树称为2-3树。

2-3树和上一篇说的普通二叉查找树最大的不同就是，它可以保持树的平衡，从而避免了二叉查找树的最坏情况的出现，守住了对数级别操作的底线，通过的办法就是自下向上生长。

查找

查找很简单，跟二叉查找树是类似的，以上图为例，查找8的话，首先跟根节点13比较，8小于小于13，于是去左子树中查找，8又大于6而小于9于是去这个结点的中子树中查找，命中。

插入

插入是非常重要的一步，正是在插入上边体现了2-3树的自下向上生长，保持了树的平衡。也因此，插入要复杂一点点，我们分情况讨论：

  • 向2-结点中插入新键
    跟二叉查找树中的插入一样，在插入之前，先要进行一次未命中的查找（如果命中就不需要新键结点了，直接进行值的覆盖），如果这次未命中的查找结束于一个2-结点，那就很容易了，我们直接将这个2-结点变成一个3-结点，将新键插入其中。比如我们插入一个7，上图将变为
  • 向一颗只含有一个3-结点的树中插入新键
    一个3-结点中含有两个键和三个链接，正常来说作为一个2-3树中的结点，已经没有位置在插入新键了。我们采取的办法就是将新键插入这个结点中，使之临时成为一个4-结点，于是这个结点中含有三个键和四个链接。当然了我们还需要将这个4-结点转换为2-结点或者3-结点，不然怎么能叫做2-3树？很简单，我们直接将这个4-结点分解成为三个2-结点，一个结点含有中间那个键，成为新的根节点，另外两个结点作为子树结点。如图：

    原本只有一个根结点，其中存了两个键2和9，插入5之后最终有了三个结点，并且树的高度增长了1，新插入的5成为了新的根节点，自下向上的生长使得新树任然保持了平衡。
  • 向一个父结点为2-结点的3-结点中插入新键
    这一种情况与上一中情况有相同的地方，未命中的查找结束与一个3-结点。同样，我们需要构造一个临时的4-结点，然后进行2-结点的转换，只不过“生长”出去的键（如上一幅图中的5），不需要新建一个结点来保存，而是放入父结点中，使得父结点成为一个3-结点。如图：
  • 向一个父结点为3-结点的3-结点中插入新键
    同样，先临时构造4-结点，并进行分解，向上生长，增加父结点中的键的数量，不过此时父结点也是3-结点，增加之后成为了新的4-结点，我们只能够再次分解向上生长，直到遇到一个2-结点，或者生长到了根部，只能进行根的分解。
  • 分解根节点
    如果插入结点的父结点的父结点…都是3-结点，并且最终蔓延到了根节点，我们就需要进行根结点的分解了，分解根结点之后，树的高度加一，平衡性不变。

红黑树

2-3树作为一种概念，而红黑树便是它的实现。2-3树为了保持树的平衡性出现了三种结点，而红黑树中只有一种结点，看起来就是普通的二叉查找树。只不过通过对红黑结点进行变色，旋转来使得每一个红黑树都可以有一个与之对应的2-3树，从而拥有2-3树的性质。总之，红黑树的基本思想就是用标准的二叉查找树来表示2-3树，这样我们不需要定义各种不同的结点，只需要给每个结点增加颜色的属性以及旋转变色的动作就可以实现一种高效的二叉查找树。如图2-3树和与之对应的红黑树：

将红线拉平是为了更清楚的看出二者的对应关系，其实红黑树就是一个有颜色的二叉树，将拉平的红线还原：

颜色

红黑树中的结点有两种颜色，红色和黑色。由红色链接指向的结点是红结点，黑色链接指向的结点是黑结点。结点了有了颜色之分，为什么链接也有颜色呢？着实还是为了模拟2-3树，2-3树中的3-结点就是通过红色链接在红黑树中实现的。由红色链接连起来的两个2-结点，构成一个3-结点。

旋转

为了减少可能出现的情况，我们只允许出现红色左链接，而不允许红色右链接以及连续红色链接的出现。但是当我们进行某些操作之后，这两种我们不允许的状况就会出现，我们就需要进行旋转操作。

左旋转红连接，6和9的结点颜色发生变化，>6&&<9这个子树的父结点发生变化，从而红色右链接转换为红色左链接。

颜色变换

如果出现如图情况就需要进行颜色变换，将自己的两个红色链接变为黑色链接，并将自己由黑变红也就是将指向自己的链接由黑变红。

查找

红黑树的查找就是二叉查找树中的查找，完全类似。

插入

为了保证树的平衡，总是用红色的链接指向新增的结点，对应到2-3树里边就是总是在结点内部新加键而不是新增一个结点。

  • 向单个2-结点中插入新键

    如果新键小于这个2-结点的键，只需要新增一个红色的结点就可以了，如果大于，就会产生一个红色的右连接，不过也只需要进行一个左旋转，将它变成红色左链接并修正根节点的链接就可以了。
    左插入

    右插入

  • 向一个3-结点中插入新键
    这种情况又可以分为三种子情况，新插入的键小于两个键，处于两个键之间或大于两个键。任何一种情况都会造成连续的两条红链接，为了修正这个情况，需要我们配合使用旋转和变色。
    新键最大

    新键最小（先右旋上层红链接，再变***r>
    新键介于两者之间（先左旋下层红链接，再右旋上层红链接，再变***r>

  • 将红链接进行向上传递
    在颜色变换的过程中，中间节点颜色会被我们变成红色，对于中间结点的父结点来说，相当于重新插入了一个结点，然后继续刚才的步骤，直到遇到了一个2-结点或者根结点。
    总之，通过使用左旋转和右旋转以及变色，我们可以保证插入后的红黑树和2-3树的一一对应关系，从而避免树的极度不平衡状态，实现高效插入操作。

红黑树是第一种能够同时实现高效的查找、插入和删除操作的数据结构。今天我们介绍了最简单易懂的部分，并且规定了不准出现右红色链接，也就是对应的2-3树中不会出现4-结点，而现实中这种情况是可以存在的，只不过代码实现要更复杂一些。还有红黑树的删除，以及每种操作的代码实现，都留给未来的那篇文吧。