一、基本概念

2-3树是最简单的 B 树结构，其每个非叶节点都有两个或三个子女，而且所有叶子结点都在同一层上。2-3树不是二叉树，其节点可拥有3个孩子。

在2-3树中包含2-结点和3-结点，下面分别对这两个结点进行解释：

  • 2-结点：含有一个键（及其对应的值）和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
  • 3-结点：含有两个键（及其对应的值）和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

1618815439532.png

二、查找

将二叉搜索树的查找算法一般化我们就能够直接得到2-3树的查找算法。 要判断一个键是否在树中，我们先将它和
根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的连
接，并在其指向的子树中递归地继续查找。如果这个是空链接，查找未命中。

例如在上图中的2-3树中查找结点28，下面给出查找过程：

1618817572384.png

1618817961773.png

1618818137391.png

三、插入

1、向2-结点插入新结点

往2-3树中插入元素和往二叉搜索树中插入元素一样，首先要进行查找，然后将节点挂到未找到的结点上。如果查找后未找到的结点是一个2-结点，那么我们只需要将新的元素放到这个2-结点中使其变成一个3-结点即可。

1618822990595.png

1618823266816.png

2、向一颗只有3-结点的树插入新结点

假设2-3树只包含一个3-结点，这个结点有两个键，没有空间来插入第三个键了，最自然的方式是我们假设这个结点能存放三个元素，暂时使其变成一个4-结点，同时他包含四条链接。然后,我们将这个4-结点的中间元素提升，左边的键作为其左子结点，右边的键作为其右子结点。插入完成，变为平衡2-3查找树，树的高度从0变为1。

1618823481882.png

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

和上面的情况一样，我们也可以将新的元素插入到3-结点中，使其成为一个临时的4-结点，然后将该结点中的中间元素提升到父结点即2-结点中，使父结点成为一个3-结点，然后将左右结点分别挂在这个3-结点的恰当位置。

1618823821539.png

1618824005815.png

1618824177746.png

4、向一个父结点为3-结点的3-结点插入新结点

当我们插入的结点是3-结点的时候，我们将该结点拆分，中间元素提升至父结点，但是此时父结点是一个3-结点，插入之后，父结点变成了4-结点，然后继续将中间元素提升至其父结点，直至遇到一个父结点是2-结点，然后将其为3-结点，不需要继续进行拆分。

1618824421287.png

1618827930560.png

1618828226504.png

1618829331362.png

5、分解根结点

当插入结点到根结点的路径上全部是3-结点的时候，最终我们的根结点会编程一个临时的4-结点，此时，就需要将根结点拆分为两个2-结点，树的高度加1。

1618830309708.png

1618830522165.png

1618830687703.png

四、二叉树的性质

通过对2-3树插入操作的分析，我们发现在插入的时候，2-3树需要做一些局部的变换来保持2-3树的平衡。一棵完全平衡的2-3树具有以下性质：

  1. 任意空链接到根结点的路径长度都是相等的。
  2. 4-结点变换为3-结点时,树的高度不会发生变化,只有当根结点是临时的4结点,分解根结点时,树高+1。
  3. 2-3树与普通二叉查找树最大的区别在于,普通的二叉查找树是自顶向下生长,而2-3树是自底向_性长。

2-3查找树实现起来比较复杂，在某些情况插入后的平衡操作可能会使得效率降低。但是2-3查找树作为一种比较重要的概念对于B树和B+树来说非常重要。