红黑树插入操作详解 红黑树是一种自平衡二叉搜索树，通过约束节点颜色和旋转操作维持平衡，确保最坏情况下基本操作（插入、删除、查询）的时间复杂度为O(log n)。以下是插入操作的详细步骤： 1. 红黑树的基本性质 插入前需确保树满足以下性质： 颜色属性 ：每个节点是红色或黑色。 根属性 ：根节点必须是黑色。 叶子属性 ：所有叶子节点（NIL节点，空节点）为黑色。 红色节点属性 ：红色节点的子节点必须为黑色（即不能有连续红色节点）。 路径属性 ：从任意节点到其所有叶子节点的路径包含相同数量的黑色节点（黑高一致）。 2. 插入操作步骤 步骤1：标准二叉搜索树插入 新节点初始颜色设为 红色 （避免破坏黑高，但可能违反红色节点属性）。 按二叉搜索树规则插入：比较键值大小，递归找到空位（NIL节点位置）插入新节点。 示例：插入节点 Z ，其父节点为 P ，祖父节点为 G ，叔节点为 U 。 步骤2：检查并修复红黑树性质 插入后可能违反性质2或4，需按以下情况修复： 情况1：Z是根节点 若Z是根（无父节点），直接将其染黑（满足性质2）。 修复结束。 情况2：Z的父节点P是黑色 插入红色节点Z后，未产生连续红色节点（性质4未破坏），黑高不变（性质5保持）。 无需修复。 情况3：P是红色（需进一步分类） 此时P和Z均为红色，违反性质4。根据叔节点U的颜色分情况处理： 情况3.1：U是红色 操作 ： 将P和U染黑。 将G染红。 将G视为新插入的红色节点，递归向上修复（可能需处理G的父节点）。 原理 ：通过颜色翻转保持黑高，但G变红后可能与其父节点冲突，需递归处理。 情况3.2：U是黑色或NIL（需考虑Z和P的相对位置） 进一步分两种子情况： 情况3.2.1：Z是P的右孩子，且P是G的左孩子（或对称情况：Z是P的左孩子，P是G的右孩子） 操作 ： 以P为支点左旋（若Z是右孩子）或右旋（若Z是左孩子）。 旋转后Z和P角色互换，转为情况3.2.2。 目的 ：将树结构调整为线性链，便于后续旋转。 情况3.2.2：Z是P的左孩子，且P是G的左孩子（或对称情况：Z是P的右孩子，P是G的右孩子） 操作 ： 将P染黑，G染红。 以G为支点右旋（若P是左孩子）或左旋（若P是右孩子）。 结果 ：旋转后子树根变为黑色，黑高恢复，且消除连续红色节点。 3. 示例演示 插入序列： [10, 5, 15, 3] （初始为空树）： 插入10（根节点，染黑）。 插入5（作为10的左孩子，红色，无冲突）。 插入15（作为10的右孩子，红色）： 父节点10为黑色，无需修复。 插入3（作为5的左孩子，红色）： 父节点5为红色，叔节点15为红色（情况3.1）： 将5和15染黑，10染红。 10变为根节点，染黑（情况1）。最终树平衡。 4. 时间复杂度分析 插入位置查找：O(log n)。 修复操作最多旋转2次（情况3.2.1需1次旋转，情况3.2.2需1次旋转），递归深度O(log n)。 总时间复杂度：O(log n) 。 5. 关键点总结 新节点总为红色，最小化对黑高的破坏。 修复的核心是 旋转+颜色调整 ，通过局部调整传递冲突至上层。 情况3.1通过颜色翻转向上递归，情况3.2通过旋转终止递归。