234树和红黑树

首先，把目光聚集在234树中

以下是234的三种节点（可以有更多这里使用以下的三个）：

右侧是节点转换成红黑树节点的样子。

接下来会用以下序列进行1234树的搭建和红黑树的搭建：

首先是234树

2-3-4树（234树）是一种多路搜索树，它的每个节点最多可以有 4 个子节点和 3 个键值。以下是 2-3-4 树的搭建过程：

1. 创建根节点： 最开始，2-3-4 树为空树。创建一个空的根节点，此时根节点没有键值和子节点。这是整棵树的起始点。

2. 插入第一个键值： 向空树中插入第一个键值。将这个键值放入根节点中，此时根节点就变成了一个包含一个键值的节点，并且该节点没有子节点，因为这是树中唯一的元素。

3. 继续插入键值：

   • 插入到 2-节点（包含 1 个键值的节点）：如果要插入的节点是一个 2-节点（只有一个键值且有两个子节点位置，当前为空），将新键值插入到该节点中。插入后，该节点会根据键值大小调整键值的顺序（小的在左，大的在右），同时该节点变为一个 3-节点（包含 2 个键值）。

   • 插入到 3-节点（包含 2 个键值的节点）：当要插入到一个 3-节点时，因为 3-节点已经有 2 个键值，再插入一个新键值后，该节点会有 3 个键值。此时需要进行节点分裂操作。将 3 个键值中中间大小的键值提升到父节点（如果没有父节点，则创建一个新的根节点），较小的键值和较大的键值分别形成两个新的子节点。这样就将一个 3-节点分裂成了一个 2-节点（包含较小键值）、一个 2-节点（包含较大键值）以及父节点中提升的键值，从而保持了树的结构特性。

   • 插入到 4-节点（包含 3 个键值的节点）：当插入到 4-节点（已经有 3 个键值）时，同样需要进行分裂。将 4 个键值（包括新插入的键值）中中间的键值提升到父节点，较小的两个键值形成一个新的子节点，较大的两个键值形成另一个新的子节点。这就将一个 4-节点分裂成了两个 2-节点（分别包含较小和较大的两个键值）以及父节点中提升的键值。

4. 处理根节点分裂： 如果在插入过程中，根节点发生分裂（例如插入到根节点的 4-节点中），那么需要创建一个新的根节点，将中间的键值提升到这个新的根节点，原来根节点分裂出的子节点作为新根节点的子节点。这样树的高度就会增加 1。

5. 重复插入操作： 不断重复上述插入和节点分裂的过程，直到所有需要插入的键值都插入到树中。在整个过程中，2-3-4 树始终保持其特性，即所有叶子节点都在同一层，并且每个节点的键值和子节点数量都符合 2-3-4 树的规则。

通过以上步骤，就可以逐步搭建起一棵 2-3-4 树，实现数据的有效存储和组织，以便后续进行查找、删除等操作。

在我们获得的234基础上按照咱们之前的这个图来进行构建：

呈现结果：

我们得到的红黑树有以下的几个特征：

红黑树是一种自平衡的二叉搜索树，具有以下几大特征：

1. 节点颜色：每个节点要么是红色，要么是黑色。

2. 根节点：根节点是黑色的。

3. 叶子节点：所有叶子节点（NIL节点，即空节点）都是黑色的。

4. 红色节点的子节点：如果一个节点是红色的，那么它的两个子节点都是黑色的，也就是说，不能有两个连续的红色节点。

5. 路径上的黑色节点数量：从任意一个节点到其叶子节点的所有路径上，包含相同数量的黑色节点，这也被称为黑高（black - height）属性。

这些特征保证了红黑树在进行插入、删除和查找等操作时，能够保持较好的平衡性和时间复杂度。平均情况下，红黑树的查找、插入和删除操作的时间复杂度都是$O(log n)$，其中$n$是树中节点的数量。