红黑树（Red-Black Tree）原理与实现 红黑树是一种自平衡的二叉搜索树，它在每个节点上增加一个存储位表示颜色（红或黑），通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长出两倍，从而近似实现平衡。 一、红黑树的基本性质 红黑树必须满足以下五个性质： 每个节点是红色或黑色 根节点是黑色 每个叶子节点（NIL节点，空节点）是黑色 如果一个节点是红色，则它的两个子节点都是黑色（即不能有相邻的红色节点） 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑色高度相同） 二、红黑树的基本操作 1. 节点结构 每个节点包含：键值(key)、颜色(color)、左子节点(left)、右子节点(right)、父节点(parent) 2. 旋转操作 旋转是维护平衡的基础操作： 左旋：以某个节点为支点，其右子节点成为新的父节点 右旋：以某个节点为支点，其左子节点成为新的父节点 三、插入操作详解 步骤1：普通二叉搜索树插入 首先按照二叉搜索树的规则插入新节点，新插入的节点初始颜色设为红色（这不会违反黑色高度性质，但可能违反红色节点不能相邻的性质）。 步骤2：颜色调整与旋转 插入后检查是否违反红黑树性质，主要处理以下情况： 情况1：插入节点是根节点 直接将颜色改为黑色即可。 情况2：父节点是黑色 没有违反任何性质，不需要调整。 情况3：父节点是红色（需要调整） 这种情况下需要进一步分情况处理： 情况3.1：叔叔节点是红色 将父节点和叔叔节点变为黑色 祖父节点变为红色 将祖父节点作为新的当前节点继续调整 情况3.2：叔叔节点是黑色，且当前节点是父节点的右子节点 以父节点为支点进行左旋 将原父节点作为新的当前节点，转为情况3.3 情况3.3：叔叔节点是黑色，且当前节点是父节点的左子节点 将父节点变为黑色 祖父节点变为红色 以祖父节点为支点进行右旋 四、删除操作详解 步骤1：普通二叉搜索树删除 先执行标准二叉搜索树删除操作，如果删除的节点是红色，通常不需要调整；如果是黑色，则需要重新平衡。 步骤2：删除后的平衡调整 主要处理以下情况： 情况1：兄弟节点是红色 将兄弟节点变为黑色 父节点变为红色 对父节点进行左旋/右旋 重新确定兄弟节点，继续处理 情况2：兄弟节点是黑色，且兄弟节点的两个子节点都是黑色 将兄弟节点变为红色 将父节点作为新的当前节点继续调整 情况3：兄弟节点是黑色，且兄弟节点的近侄子节点是红色，远侄子节点是黑色 将兄弟节点变为红色 近侄子节点变为黑色 对兄弟节点进行右旋/左旋 重新确定兄弟节点，转为情况4 情况4：兄弟节点是黑色，且兄弟节点的远侄子节点是红色 将兄弟节点的颜色设为父节点的颜色 将父节点和远侄子节点变为黑色 对父节点进行左旋/右旋 调整完成 五、红黑树的时间复杂度 搜索、插入、删除：O(log n) 旋转操作：每次插入最多2次旋转，每次删除最多3次旋转 六、红黑树的应用场景 C++ STL中的map、multimap、set、multiset Java中的TreeMap、TreeSet Linux内核中的进程调度 文件系统目录结构 数据库索引结构 红黑树通过相对简单的规则和操作，实现了较好的平衡性能，在实际应用中比AVL树等其他平衡树更加高效。