2-3树

定义

2-3树是一种搜索树，其节点有三种可能：

• 空节点：null
• 2-节点：有一个键值和两个指针，左指针指向键值较小的子2-3树，右指针指向键值较大的子2-3树。（同BST的内部节点）
• 3-节点：有两个键值和三个指针，左指针指向键值较小的子2-3树，中间指针指向键值在当前节点两键值之间的子2-3树，右指针指向键值较大的子2-3树。

（放个2-节点和3-节点的图）

搜索

由上图可知，搜索过程与BST类似，只是遇到3-节点时需要多些条件判断，在此不再赘述。

插入

在搜索失败时，我们需要插入一个新节点。与BST不同，2-3树不会直接在null的位置加入一个新节点，而是尝试融入进搜索过程最后的叶子节点。根据叶子节点键值的个数，我们有两种情况：

1. 叶子节点是2-节点。那么我们只需将新节点的值加入进去，变为3-节点即可。
2. 叶子节点是3-节点。同上，我们先暂时将该节点变为4-节点。由于其不符合规则，我们再将其分裂为三个2-节点——以中值为键的节点作为父节点，较小值的为左子树，较大值的为右子树。注意：若该节点的父节点已经是3-节点，那么提出来的父节点会再融入进去，重复这一过程，以此类推。

（放出三个情况的图）

特性

• 树是保持平衡且有序的
• 根节点到任一空节点的链接（links）数相同

红黑树

由于需要在一个节点内维护可变个数的键值，以及分裂节点的可能情况较多，我们并不直接实现2-3树。1979年Guibas和Sedgewick（Algorithms的作者）提出了左倾红黑树（left-leaning red-black tree），将2-3树表示为BST，较易实现。

红与黑

为了将2-3树映射为BST，红黑树的链接（links）用红与黑两种颜色表示不同的情况。红链接连接的节点融合起来就是2-3树的3-节点，黑链接是2-3树的普通链接。

（给出映射图）

红黑树简化了树的结构，当然会有一定的约束：

1. 不能存在节点有两个红链接。因为在这种时候，对应到2-3树就是一个4-节点，不符合规则。
2. 根节点必须为黑色。原因见：Why is the root in a red-black tree always black?

搜索

由上述可知，红黑树的表现就是BST，因此搜索过程与BST完全一致。

插入

插入新节点可能会破坏原树的定义与平衡性，所以我们需要旋转和翻转颜色等操作来修复。

左旋

右旋

翻转颜色

参考

Red black tree over avl tree