我们再次和刚才一样构造一个暂时的4-结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3-结点。因此我们再用这个中键构造一个新的暂时4-结点，然后在这个结点上进行同样的变换。即分解这个父结点并将它的中键插入到它的父结点中去。
我们就这样一直向上不断分解暂时的4-结点并将中键插入更高的父结点，直至遇到一个2-结点并将它替换为一个不须要继续分解的3-结点。或者是到达3-结点的根。
总结：
先找插入结点，若结点有空(即2-结点)，则直接插入。如结点没空(即3-结点)，则插入使其暂时容纳这个元素，然后分裂此结点。把中间元素移到其父结点中。对父结点亦如此处理。
（中键一直往上移。直到找到空位。在此过程中没有空位就先搞个暂时的，再分裂。
）
★2-3树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必改动或者检查树的其它部分。每次变换中，变更的链接数量不会超过一个非常小的常数。全部局部变换都不会影响整棵树的有序性和平衡性。
{你确定理解了2-3树的插入过程了吗？ 假设你理解了，那么你也就基本理解了红黑树的插入}
构造
和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的。
长处
2-3树在最坏情况下仍有较好的性能。每一个操作中处理每一个结点的时间都不会超过一个非常小的常数，且这两个操作都仅仅会訪问一条路径上的结点，所以不论什么查找或者插入的成本都肯定不会超过对数级别。
完美平衡的2-3树要平展的多。比如，含有10亿个结点的一颗2-3树的高度仅在19到30之间。我们最多仅仅须要訪问30个结点就能在10亿个键中进行随意查找和插入操作。
缺点
我们须要维护两种不同类型的结点，查找和插入操作的实现须要大量的代码。并且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
平衡一棵树的初衷是为了消除最坏情况，但我们希望这样的保障所需的代码可以越少越好。
【前言：本文所讨论的红黑树之目的在于使读者能更简单清晰地了解红黑树的构造，使读者能在纸上清晰高速地画出红黑树。而不是为了写出红黑树的实现代码。
若是要在代码级理解红黑树。则势必须要记住其复杂的插入和旋转的各种情况。我觉得那仅仅有助于添加大家对红黑树的恐惧，实际面试和工作中差点儿不会遇到须要自己动手实现红黑树的情况(非常多语言的标准库中就有红黑树的实现)。 若对于红黑树的C代码实现有兴趣的，可移步至July的博客。
】
（理解红黑树一句话就够了：红黑树就是用红链接表示3-结点的2-3树。那么红黑树的插入、构造就可转化为2-3树的问题，即：在脑中用2-3树来操作，得到结果。再把结果中的3-结点转化为红链接就可以。而2-3树的插入。前面已有具体图文，实际也非常easy：有空则插，没空硬插，再分裂。 这样，我们就不用记那么复杂且让人头疼的红黑树插入旋转的各种情况了。
仅仅要清楚2-3树的插入方式就可以。 以下图文具体演示。）
红黑树的本质：
红黑树是对2-3查找树的改进，它能用一种统一的方式完毕全部变换。
替换3-结点
★红黑树背后的思想是用标准的二叉查找树（全然由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。