我们如果键的插入顺序是随机的。对这个模型的分析而言，二叉查找树和高速排序差点儿就是“双胞胎”。树的根结点就是高速排序中的第一个切分元素（左側的键都比它小。右側的键都比它大），而这对于全部的子树相同适用，这和高速排序中对于子数组的递归排序全然相应。
【在由N个随机键构造的二叉查找树中，查找命中平均所需的比較次数为~2lgN。 N越大这个公式越准确】
平衡查找树
在一颗含有N个结点的树中，我们希望树高为~lgN。这样我们就能保证全部查找都能在~lgN此比較内结束，就和二分查找一样。
不幸的是，在动态插入中保证树的完美平衡的代价太高了。我们放松对完美平衡的要求，使符号表API中全部操作均可以在对数时间内完毕。
2-3查找树
为了保证查找树的平衡性，我们须要一些灵活性。因此在这里我们同意树中的一个结点保存多个键。
2-结点：含有一个键(及值)和两条链接。左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
3-结点：含有两个键(及值)和三条链接。左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
（2-3指的是2叉-3叉的意思）
一颗完美平衡的2-3查找树中的全部空链接到根结点的距离都是同样的。
查找
要推断一个键是否在树中，我们先将它和根结点中的键比較。
假设它和当中的不论什么一个相等，查找命中。否则我们就依据比較的结果找到指向对应区间的链接。并在其指向的子树中递归地继续查找。假设这是个空链接。查找未命中。
插入
要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找。然后把新结点挂在树的底部。
但这种话树无法保持完美平衡性。
我们使用2-3树的主要原因就在于它可以在插入之后继续保持平衡。
假设未命中的查找结束于一个2-结点，我们仅仅要把这个2-结点替换为一个3-结点，将要插入的键保存在当中就可以。假设未命中的查找结束于一个3-结点，事情就要麻烦一些。
热身：
先考虑最简单的样例：仅仅有一个3-结点的树。向其插入一个新键。
这棵树唯一的结点中已经没有可插入的空间了。我们又不能把新键插在其空结点上（破坏了完美平衡）。为了将新键插入，我们先暂时将新键存入该结点中。使之成为一个4-结点。创建一个4-结点非常方便，由于非常easy将它转换为一颗由3个2-结点组成的2-3树（如图所看到的），这棵树既是一颗含有3个结点的二叉查找树，同一时候也是一颗完美平衡的2-3树。当中全部空链接到根结点的距离都相等。
向一个父结点为2-结点的3-结点中插入新键
如果未命中的查找结束于一个3-结点。而它的父结点是一个2-结点。
在这样的情况下我们须要在维持树的完美平衡的前提下为新键腾出空间。
我们先像刚才一样构造一个暂时的4-结点并将其分解，但此时我们不会为中键创建一个新结点。而是将其移动至原来的父结点中。（如图所看到的）
这次转换也并不影响（完美平衡的）2-3树的主要性质。
树仍然是有序的。由于中键被移动到父结点中去了，树仍然是完美平衡的。插入后全部的空链接到根结点的距离仍然同样。
向一个父结点为3-结点的3-结点中插入新键
如果未命中的查找结束于一个3-结点。而它的父结点是一个3-结点。