2-3树

定义

一棵2-3查找树或为一棵空树，或由以下结点组成：

• 2-结点，含有一个键（及其对应的值）和两条链接。
• 3-结点，含有两个键（及其对应的值）和三条链接。

2-结点、3-结点的性质均与BST相同或相似。

搜索

与二叉搜索树类似。

插入

• 向2-结点中插入新键

  只需要将键插入2-结点，使之变成3-结点。

  

• 向一颗只含有3-结点的树中插入新键

  在考虑一般情况之前，先假设我们需要向一棵只含有一个3-结点的树中插入一个新键。这棵树中由两个键，所以在它唯一的结点中已经没有可插入新键的空间了。为了将新键插入，我们先临时将新键存入该结点中，使之成为一个4-结点。它很自然地拓展了以前的结点并含有3个键和4条链接。然后将4-结点转换为由3个2-结点组成的2-3树，其中中间的键所在2-结点成为了其他两个键所在结点的父结点。这是2-3树生长的基本方式。

  

• 向一个父结点为2-结点的3-结点插入新键

  首先，向刚才一样，构造一个临时的4-结点并将其分解，然后将中键移动至原来的父结点中。此时树仍然是有序的，因为中键被移动到父结点中去了。同时，树仍然是完美平衡的，插入后所有的空链接到根节点的距离仍然相同。

  

• 向一个父结点为3-结点的3-结点中插入新键

  我们再次和刚才一样构造一个临时的4-结点并分解它，然后将它的中键插入到它的父结点中。但父结点也是一个3-结点，因此我们再用这个中键构造一个新的临时4-结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父节点中去。推广至一般情况，我们就这样一直向上不断分解临时的4-结点并将中键插入到更高层的父节点，直到遇到一个2-结点并将它替换为一个不需要继续分解的3-结点，或者是到达3-结点的根。

  

• 分解根结点

  如果从插入结点到根结点的路径上全部都是3-结点，我们的根结点最终变成一个临时的4-结点，此时我们将临时的4-结点分解为3个2-结点，使得树高加1。

  

  ​

局部变换和全局性质

• 2-3树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或检查树的其他部分。

• 这些局部变换不会影响到树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的。

• 插入情况汇总：