红黑树（Red-Black Tree）的性质与平衡操作 红黑树是一种自平衡的二叉搜索树，它通过维护额外的颜色属性（红色或黑色）和一组规则来确保树在插入和删除操作后保持近似平衡，从而保证最坏情况下的时间复杂度为O(log n)。 红黑树的五条性质 每个节点是红色或黑色 根节点是黑色 每个叶子节点（NIL节点）是黑色 红色节点的子节点必须是黑色（即不能有两个连续的红色节点） 从任意节点到其所有后代叶子节点的简单路径上，黑色节点的数量相同（称为黑高） 插入操作的核心步骤 当插入新节点时，我们首先按照二叉搜索树的规则找到插入位置，并将新节点着为红色（这有助于满足性质5）。插入后可能违反性质2或性质4，需要通过旋转和重新着色来修复。 插入后的修复情况分析 设新插入节点为N，其父节点为P，祖父节点为G，叔节点为U。 情况1：P是黑色 直接插入即可，不违反任何规则 情况2：P是红色 此时需要进一步分析： 情况2.1：U是红色 将P和U变为黑色，G变为红色 将G视为新插入的红色节点，递归向上处理 情况2.2：U是黑色或不存在 这分为两种子情况： 情况2.2.1：N是P的右孩子，P是G的左孩子（或对称情况） 对P进行左旋，转换为情况2.2.2 情况2.2.2：N是P的左孩子，P是G的左孩子（或对称情况） 将P变为黑色，G变为红色 对G进行右旋 实例演示插入过程 假设依次插入10, 20, 30： 插入10（根节点，着黑色） 插入20（作为10的右孩子，着红色） 插入30（作为20的右孩子，着红色） 此时20和30都是红色，违反性质4 检查：P=20（红），G=10（黑），U不存在（视为黑） 属于情况2.2，且30是20的右孩子，20是10的右孩子 对20左旋？不对，这是情况2.2.2的直接情况 将20变黑，10变红，然后对10左旋 最终得到：20（黑）为根，10（红）为左孩子，30（红）为右孩子。 删除操作的修复策略 删除操作更复杂，主要关注： 如果删除的是红色节点，通常不影响平衡 如果删除的是黑色节点，会破坏黑高，需要通过旋转和重新着色修复 修复时需要考虑兄弟节点的颜色和侄子节点的颜色组合 红黑树 vs AVL树 红黑树提供更松的平衡，插入删除更快，适合频繁修改的场景 AVL树更严格平衡，查询更快，适合读多写少的场景 红黑树通过巧妙的规则设计，在保持平衡的同时减少了旋转次数，是实践中广泛应用的高效数据结构。