定义
left、middle、right 为 2-3 树结点的孩子指针；dl, dr为 2-3 树结点元素）：
- 每个内部结点或者是一个2结点，或者是一个3结点。一个2结点存放一个元素，而一个3结点存放两个元素。
- 每个结点的 dl 值大于 left 指向子树所有结点内元素的值 且 小于 middle 指向子树所有结点的元素值。
- 每个结点的 dr 值大于 middle 指向子树所有结点的元素值 且 小于 right 指向子树的所有结点的元素值。
- 所有外部结点都在同一层。
h - 1 到 3h - 1 之间。一棵包含 n 个结点的 2-3 树，其高度在 log2(n+1 和 log3(n + 1 之间。
类型定义
Java 定义
1 public class TwoThreeNode<T extends Comparable<T>> { 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 }
比较函数
- 1 为左子树方向
- 2 为中子树方向
- 3 为右子树方向
- 4 为等于左元素
- 8 为等于右元素
查找函数
Java 定义
1 public TwoThreeNode<T> search(T data { 2 TwoThreeNode<T> 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 < n.dl 则 qq.left = n.middle | qq.middle = n.right | n.middle = q
- 如果 n.dl < e < n.dr 则 qq.left = q | qq.middle = n.right
- 如果 n.dr < e 则 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结点，兄弟结点得到释放。
- 如果 父节点处理后，结点元素为空（零元素），则继续向上回溯；否则退出。