1 2-3树

1.1 定义

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

树结点由2-结点或者3-结点组成且所有叶子结点处于同一高度的树（允许是空树）即为2-3树。

1.2 性质

1. 结点只能为2-结点或者3-结点
2. 对于2-结点其有一个数据，两个指针结点
3. 对于3-结点其有两个数据，三个指针结点
4. 所有叶子结点的高度保持一只高度

1.3 查找

查找过程与二叉搜索树相类似。

1.4 插入

遍历查找结点：

• 查找到则不进行插入
• 未查找到，则记录查找结束的最后结点

插入操作可以分为四种类型：

1. 向2-结点插入新结点
2. 向仅有一个3-结点的树中插入新结点
3. 向一个父结点为2-结点的3-结点中插入新结点
4. 向一个父结点为3-结点的3-结点插入新结点

示例：将5,10,15,20,25,30,35,40,45,50依次放入2-3树

树-23树插入.drawio.png

1.5 删除

删除操作也要先进行元素的查找，找到才继续进行删除操作。

1.5.1 删除叶子结点

1.5.1.1 位于三结点叶子结点

删除的元素位于三结点的叶子结点上，直接删除改元素即可，不会影响整个树的其他结点。

叶子结点1.png

1.5.1.2 位于二结点叶子结点

A. 父结点是二结点，右孩子是三结点

直接删除元素后，会导致树不满足定义，此时进行左旋。

叶子结点2.png

B.父结点是二结点，右孩子也是二结点

通过中序遍历，使用前驱或后继节点补位。

如示例先将结点【20】移到结点【15】中形成三结点，再将【25】移到原有【20】结点位置。此时【30 40】、【35】和【45 50】结点形成"C.父结点是三结点"类型的删除。

叶子结点3.png

C.父结点是三结点

删除节点，意味父节点不能成为三结点，需要降为二结点。

如示例将【30】与【35】合并为三结点，作为【40】节点的左孩子。

叶子结点4.png

D.满二叉树

需要减少层数。

如示例结点【10】和【15】合并为三结点作为结点【20】左孩子，结点【30】与【20】合并为三结点作为根节点。

叶子结点5.png

1.5.2 删除非叶子结点

通过中序遍历得到节点的前驱或后继节点，进行补位。

2 2-3-4树

2-3-4树其实是2-3树的扩展，包含四结点的使用。

• 4-结点：含有三个键和四条链接（或没有），左链接指向的2-3-4树中的键都小于该结点，第二条链接指向的2-3-4树中的键都位于该结点的第一和第二个键之间，第三条链接指向的2-3-4树中的键都位于该结点的第二和第三个键之间，右链接指向的2-3-4树中的键都大于该结点。

由于2-3-4树整体与2-3树类似，故只以示例方式演示其构造和删除。

示例：将5,10,15,20,25,30,35,40,45,50依次放入2-3-4树

树-2-3-4树插入.drawio.png

3 红黑树

2-3-4树与红黑树保持平衡的规则是一致的，并且可以通过一些规则进行转换。它们是同构关系。

2-3-4树转换红黑树.png

红黑树的结构与2-3-4树对应，而且两种树操作也一样。

2-3-4树用结点分裂保持平衡，红-黑树用颜色变换和旋转保持平衡。

3.1 定义

1.每个结点要么是红的，要么是黑的。
2.根结点是黑的。
3.每个叶结点，即空结点（NIL）是黑的。
4.如果一个结点是红的，那么它的俩个儿子都是黑的。
5.对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

3.2 插入

基本流程:

1. 将红黑树当作一颗二叉查找树，将结点插入
2. 将插入的结点着色为红色
3. 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树

其中旋转着色根据插入的结点父结点情况分为以下三种类型：

3.2.1 插入根结点

直接改为黑色

3.2.2 插入结点的父结点是黑色

红黑树插入1.png

3.2.3 插入结点的父结点是红色

处理思路：将红色的结点移到根结点，再将根结点设为黑色。

实际又可以细化如下几种情况：

3.2.3.1 叔叔结点为红色

处理步骤：

1. 父结点设置为黑色
2. 叔叔结点设置为黑色
3. 祖父结点设为红色
4. 祖父结点设为“当前结点”，继续向上遍历

3.2.3.2 父结点是左结点，叔叔结点是黑色

处理步骤：

1. 对祖父节点右旋
2. 父结点设为黑色
3. 祖父节点设为红色

3.2.3.3 父结点是右结点，叔叔结点是黑色

处理步骤：

1. 对父结点左旋
2. 按照步骤二处理

详细图解：

红黑树插入2.png

3.3 删除

3.3.1 叶子结点

3.3.1.1 叶子结点是红色

无需处理

3.3.1.2 叶子结点是黑色

当前结点是左结点：

左结点1.png

左结点2.png

左结点3.png

左结点4.png

E. 兄弟结点设为红色，父结点设为递归结点递归，指导根节点或红色节点

左结点5.png

当前结点是右结点：

右结点1.png

右结点2.png

右结点3.png

右结点4.png

E. 兄弟结点设为红色，父结点设为递归结点递归，指导根节点或红色节点

右结点5.png

3.3.2 非叶子结点，只有一个结点

父结点P下面只有一个子节点C，则可以将结点P和节点C交换，则可以转换成【3.3.1 叶子结点】情景。

3.3.3 非叶子结点，有两个子结点

删除的结点有两个子节点，通过交换结点P和后继节点N的方式，将删除结点P转化为结点N。

后继结点N分为两种情况：

• 是叶子结点【3.3.1 叶子结点】
• 有一个子结点【3.3.2 非叶子结点，只有一个结点】