如果节点插入序列有序，构造出的二分查找树就只有左（或者右）子树，此时查找会退化为线性查找。为了使原本“瘦高”的树结构变得“矮胖”，在节点的插入、删除中保证树的结构尽量平衡些，就能保证所有查找都能在O(logn)左右结束。
平衡查找树常用算法有多种，下面通过阅读书籍和资料记录相关内容。
一. 2-3 查找树
1.1 定义
2-3 查找树是理解平衡查找树的基础。在标准二叉查找树中，树中的节点称为2-结点（含有一个键和两条孩子链接）。2-3 查找树在2-节点基础上又引入3-结点（含有两个键和三条链接）。
- 2-结点：左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
- 3-结点：左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树种的键都大于该结点。
一颗完美的2-3查找树中的所有空链接到根结点的距离都应该是相同的，而且在动态插入过程中，这条性质永远满足。
1.2 查找
这个比较简单。
1.3 插入
为了保持动态插入过程中保持完美平衡，所以在2-3查找树的插入算法稍微复杂些，需要分类来讨论。
- 向2-结点中插入新键
这是插入中最简单的情况，只需要将新插入的键保存在2-结点中，将2-结点替换为3-结点即可。
向3-结点插入新键，则要麻烦一些。
- 向一颗只含有一个3-结点的树中插入新键
我们临时先将新键存入3-结点，使其变为4-结点，然后将4-结点的中键向上浮动，转为一颗由3个2-结点组成的2-3树。
这个例子很简单，但说明了2-3树是如何生长的，它遵循一种由下向上的生成方式。之前已经说过，2-3树种所有空链接到根结点的距离都应该是相同的，这个距离只有在根节点被分解为3个2-节点时，距离才会加1，对应着树长高了。
- 向一个父结点为2-结点的3-结点插入新键
遵循刚才的原则，将新键暂存入3-结点构造出4-结点，然后将其分解。但此时我们不会为中键创建一个新结点，而且将其移动到父结点，使得父结点成为3-结点。
观察发现，这次转换并不影响2-3树的完美平衡，而且树仍然是有序的。插入后所有空连接到根结点的距离仍然相同。
- 向一个父结点为3-结点的3-结点中插入新键
还是和刚刚一样，构造临时的4-结点然后分解它，将它的中键插入父结点。父结点成为了4-结点，需要继续分解这个父结点将它的中键插入到它的父结点，直到遇到一个2-结点将其替换为一个不需要继续分解的3-结点或者是达到3-结点的根。
- 分解根结点
如果插入结点到根结点的路径上全是3-结点，我们的根结点最终变成一个临时的4-结点，之后将根4-结点分解为3个2-结点，树的高度相应加1。这次变换仍然保持了树的完美平衡性。
- 局部变换
2-3树的插入算法的根本在于上面的这些变换都是局部的，除了相关的结点和链接之外不必修改或者检查树的其他部分。
- 全局性质。
刚刚我们也说了，局部变换并不会影响树的全局有序性和平衡性：任何空链接到根结点的路径长度都是相等的。只有在根节点被分解为3个2-结点时，所有空链接到根结点的路径长度才会加1。
命题：在一颗大小为N的2-3树种，查找和插入操作访问的结点必然不超过logN个。
二. 总结
尽管我们可以用不同的数据类型表示2-结点和3-结点，但是离我们真正的实现2-3树还有一段距离，2-3树原理清晰但代码操作并不方便，需要处理的情况太多。平衡一棵树的目的是为了消除最坏情况，同时我们也希望所需的代码能够越少越好。
下面，我们将学习一种名为红黑树的简单数据结构来表达并实现2-3树。
References
- 《算法 4》