2-3树

定义

一棵 2-3 树是一棵查找树，该查找树要么为空要么满足以下性质（令 left、middle、right 为 2-3 树结点的孩子指针；dl, dr为 2-3 树结点元素）：

1. 每个内部结点或者是一个2结点，或者是一个3结点。一个2结点存放一个元素，而一个3结点存放两个元素。
2. 每个结点的 dl 值大于 left 指向子树所有结点内元素的值 且 小于 middle 指向子树所有结点的元素值。
3. 每个结点的 dr 值大于 middle 指向子树所有结点的元素值 且 小于 right 指向子树的所有结点的元素值。
4. 所有外部结点都在同一层。

根据定义，可以看出，2-3 树本身就是一个自平衡树。对于高度为 h 的一棵 2-3 树，其上的元素个数介于 2^h - 1 到 3^h - 1 之间。一棵包含 n 个结点的 2-3 树，其高度在 log₂(n+1) 和 log₃(n + 1) 之间。

类型定义

Java 定义

1 public class TwoThreeNodeextends Comparable> {
2     private T dataLeft;
3     private T dataRight;
4     private TwoThreeNode left;
5     private TwoThreeNode middle;
6     private TwoThreeNode right;
7     private TwoThreeNode parent;
8 }

比较函数

结点有2个元素，定义一个比较函数，返回值含义：

• 1 为左子树方向
• 2 为中子树方向
• 3 为右子树方向
• 4 为等于左元素
• 8 为等于右元素

查找函数

Java 定义

 1     public TwoThreeNode search(T data) {
 2         TwoThreeNode node = head;
 3         while (node != null) {
 4             int r = compare(node, data);
 5             switch (r) {
 6                 case 1: node = node.getLeft(); break;
 7                 case 2: node = node.getMiddle(); break;
 8                 case 3: node = node.getRight(); break;
 9                 case 4:
10                 case 8: return node;
11             }
12         }
13         return null;
14     }

插入

插入新元素，必然是插入到叶子结点中，如果是 2 结点的话，直接插入就结束了，但如果是3结点的话，如果向下溢出，则破坏了 2-3 树的平衡，因此需要拆分当前的结点然后向上合并，直到树根，以此保持 2-3 树自身的平衡。

• 如果是空树，则插入一个结点，设置结点为树根。
• 查找插入的结点位置，如果发现元素在树中，则插入失败，否则 定位插入的叶子结点 n 。
• n 结点是 2 结点时，直接插入 e 即可。
• n  结点是 3 结点时，由于插入 e 后，结点变为 4 结点，这时需要对结点 n 进行分裂，定义一个结点变量 q，初始化值为空，具体过程如下：
• 将 4 结点的三个元素的最小值存入 n 的左元素位置
• 以 4 结点的三个元素的最大值构建一个新的 2 结点 qq
• 根据 e 的位置设置 qq 的 left 和 middle 指针：
  • 如果 e 则 qq.left = n.middle | qq.middle = n.right |  n.middle = q
    
  • 如果 n.dl 则 qq.left = q | qq.middle = n.right 
  • 如果 n.dr 则 qq.left = n.right | qq.middle = q 
• 将 qq 赋值给 q，将 n 的父结点 赋值给 n，将 4 结点中中间值赋给 e 继续向上回溯

删除

找到待删除元素所在结点 n，如果 n 不是叶子结点，用它的直接前驱（左子树的最大元素）或者直接后继（右子树的最小元素）替换，进而转换为对叶子结点的删除。

• 如果被删除的是 3结点，直接删除即可。
• 如果被删除的是 2结点，删除后，结点元素为空（零元素）。如果删除结点，则2-3树自身平衡被破坏，因此需要从父节点 parent 和 兄弟节点 sibling 进行借元素进行合并：

• • 如果 兄弟结点 sibling 为 3结点时，需要从父结点借一个元素过来，填充当前结点，而父结点的被借的元素位置需要从 sibling 的借一个元素过来。
  • 如果 兄弟节点 sibling 为 2结点时，需要从父节点借一个元素过来 和 兄弟结点的的元素合并，组成一个3结点，兄弟结点得到释放。
  • 如果 父节点处理后，结点元素为空（零元素），则继续向上回溯；否则退出。