您现在的位置是：主页 > news > 做兼职网站哪个靠谱吗/sem账户托管公司
做兼职网站哪个靠谱吗/sem账户托管公司
admin2025/7/5 13:04:17【news】
简介做兼职网站哪个靠谱吗,sem账户托管公司,切图做网站过时了吗,百度百科官网目录 0. 节点结构与哨兵节点1. 什么是红黑树？2. 红黑树的五个核心性质3. 为什么需要红黑树？4. 红黑树的基本操作 a. 查找 (Search)b. 插入 (Insert)c. 删除 (Delete) 5. 维护平衡的关键操作 a. 变色 (Recoloring)b. 旋转 (Rotations) 6. 红黑树的优缺点…
做兼职网站哪个靠谱吗,sem账户托管公司,切图做网站过时了吗,百度百科官网目录
0. 节点结构与哨兵节点1. 什么是红黑树？2. 红黑树的五个核心性质3. 为什么需要红黑树？4. 红黑树的基本操作 a. 查找 (Search)b. 插入 (Insert)c. 删除 (Delete) 5. 维护平衡的关键操作 a. 变色 (Recoloring)b. 旋转 (Rotations) 6. 红黑树的优缺点…
目录
- 0. 节点结构与哨兵节点
- 1. 什么是红黑树？
- 2. 红黑树的五个核心性质
- 3. 为什么需要红黑树？
- 4. 红黑树的基本操作
- a. 查找 (Search)
- b. 插入 (Insert)
- c. 删除 (Delete)
- 5. 维护平衡的关键操作
- a. 变色 (Recoloring)
- b. 旋转 (Rotations)
- 6. 红黑树的优缺点
- 7. 应用场景
- 8. 性能对比
- 9. 完整代码实现
0. 节点结构与哨兵节点
在深入之前，我们先定义红黑树的节点结构，并引入一个重要的概念：哨兵节点 (Sentinel Node)。
- 颜色 (Color):
RED或BLACK - 键 (Key): 节点存储的值
- 左孩子 (Left): 指向左子节点
- 右孩子 (Right): 指向右子节点
- 父节点 (Parent): 指向父节点
哨兵节点 (NIL):
为了简化红黑树操作的边界条件处理，我们通常使用一个特殊的哨兵节点 NIL 来代表所有的叶子节点（外部节点）以及根节点的父节点。
NIL节点的颜色总是 黑色。NIL节点的key,left,right,parent字段可以不关心或指向自身。- 所有"真正的"叶子节点的
left和right指针都指向这个唯一的NIL哨兵节点。
enum Color { RED, BLACK };struct Node {int key;Color color;Node *parent;Node *left;Node *right;// 构造函数（新节点通常为红色）Node(int k, Color c = RED, Node* p = nullptr, Node* l = nullptr, Node* r = nullptr): key(k), color(c), parent(p), left(l), right(r) {}
};// 全局哨兵节点
Node* NIL; // 应该在红黑树类的构造函数中初始化一次，例如：// NIL = new Node(0, BLACK); NIL->parent = NIL; NIL->left = NIL; NIL->right = NIL;// 或者作为红黑树类的静态成员。
在后续伪代码中，当提到叶节点或空指针时，通常指的就是这个 NIL 哨兵节点。
1. 什么是红黑树？
红黑树是一种自平衡的二叉查找树（Self-Balancing Binary Search Tree）。它通过在每个节点上增加一个额外的颜色属性（红色或黑色）并遵循一组特定的规则来确保树在插入和删除操作后保持大致平衡，从而保证了在最坏情况下的操作时间复杂度为 O(log N)，其中 N 是树中节点的数量。这种平衡不是绝对的（像 AVL 树那样左右子树高度差最多为1），而是通过性质保证最长路径不超过最短路径的两倍。
2. 红黑树的五个核心性质
红黑树必须始终满足以下五个性质：
- 性质1 (颜色)： 每个节点要么是红色，要么是黑色。
- 性质2 (根节点)： 根节点是黑色的。
- 性质3 (叶节点)： 所有叶节点（NIL 节点，即空节点或外部节点）都是黑色的。在实现中，这些通常是哨兵节点
NIL。 - 性质4 (红色节点)： 如果一个节点是红色的，则它的两个子节点都是黑色的。（即，不能有两个连续的红色节点，从根到叶的路径上红色节点不相邻）。
- 性质5 (黑色高度)： 对每个节点，从该节点到其所有后代叶节点（NIL节点）的简单路径上，均包含相同数目的黑色节点。这个数目被称为节点的"黑色高度 (black-height)"。
推论：
- 从根到叶子的最长路径（红黑交替）最多是最短路径（全黑）的两倍长。
- 一棵有
n个内部节点的红黑树的高度h <= 2 * log2(n+1)。
3. 为什么需要红黑树？
- 普通二叉查找树 (BST) 的问题： 在极端情况下（例如，按顺序插入已排序的数据），BST 可能退化成链表，导致查找、插入、删除操作的时间复杂度变为 O(N)。这使得 BST 在动态数据集上的性能不可靠。
- 红黑树的保证： 红黑树通过上述五个性质，确保树的高度始终保持在对数级别，即
O(log N)。这使得即使在最坏情况下，其各项操作（查找、插入、删除）也能保持高效。 - 与 AVL 树的比较：
- 平衡性： AVL 树是更严格平衡的（左右子树高度差不超过1），红黑树则相对宽松（最长路径不超过最短路径两倍）。
- 操作效率：
- 查找： AVL 树通常更快，因为它更平衡，树高更低。
- 插入/删除： 红黑树通常更快。AVL 树为了维持严格平衡可能需要进行多次旋转（最多
O(log N)次），而红黑树的插入/删除操作中，旋转次数是常数级的（插入最多2次，删除最多3次），变色操作可能是O(log N)次。因此，在写操作频繁的场景下，红黑树可能更有优势。
- 实现复杂度： 两者都比较复杂。红黑树的修复情况（cases）比 AVL 树多，但每次修复涉及的旋转次数少。
4. 红黑树的基本操作
a. 查找 (Search)
与普通二叉查找树的查找操作完全相同。从根节点开始，比较目标值与当前节点键值，决定向左子树还是右子树继续查找，直到找到目标节点或到达 NIL 节点。
时间复杂度：O(log N)，因为树高是对数级别的。
Node* search(Node* root, int key) {Node* current = root;while (current != NIL && current->key != key) {if (key < current->key) {current = current->left;} else {current = current->right;}}return current; // 如果未找到则返回NIL
}
b. 插入 (Insert)
插入操作分为两步：
- 标准 BST 插入： 像在普通二叉查找树中一样找到新节点的插入位置，并插入新节点。
- 着色和修复：
- 着色： 新插入的节点
z总是被初始化为 红色。- 原因：
- 如果设为黑色，几乎肯定会违反性质5 (黑色高度)，因为会增加一条路径上的黑色节点数，而其他路径不变。修复性质5通常比修复性质4复杂。
- 设为红色，性质5天然满足（新红节点不改变任何路径的黑色节点数）。可能违反的性质是：
- 性质2：如果
z是根节点且为红色 (简单修复：将其变黑)。 - 性质4：如果
z的父节点z->parent也是红色 (需要更复杂的修复)。
- 性质2：如果
- 原因：
- 修复 (Fixup)： 调用一个修复过程
insert_fixup(z)，通过一系列的变色 (Recoloring) 和 旋转 (Rotations) 操作来恢复红黑树的性质。修复过程从新插入的节点z开始，向上回溯，直到所有性质都满足。
- 着色： 新插入的节点
插入修复 (insert_fixup(z)) 逻辑：
循环条件：只要 z 不是根节点，且 z 的颜色是红色，并且 z->parent 的颜色也是红色 (违反性质4)。
令 p = z->parent (父节点)，g = p->parent (祖父节点，此时 p 为红色，g 必然存在且为黑色，否则在 p 插入时就已违反性质4)。
令 u 为 z 的叔叔节点 (u = (p == g->left) ? g->right : g->left)。
-
情况1:
z的叔叔u是红色。- 动作：
- 将
p(父) 设为黑色。 - 将
u(叔) 设为黑色。 - 将
g(祖父) 设为红色。 - 将当前节点
z设为g(z = g)。
- 将
- 解释： 通过将
p和u变黑，g变红，我们将问题向上推移了两层。g变成红色可能会与g的父节点形成新的红-红冲突，所以需要继续对g进行检查。这条路径的黑色高度不变。
G(B) G(R) <-- z移至此处进行下一次迭代/ \ / \P(R) U(R) ---> P(B) U(B)/ /z(R) z(R) (原z) - 动作：
-
情况2:
z的叔叔u是黑色 (或 NIL)，且z是p的内侧孩子 (Zig-Zag 情况)。
(例如,p是g的左孩子,z是p的右孩子；或者p是g的右孩子,z是p的左孩子)- 动作：
- 如果
z == p->right且p == g->left(左-右情况): 对p左旋。然后z变成原来的p，原来的p变成z的左孩子。 - 如果
z == p->left且p == g->right(右-左情况): 对p右旋。然后z变成原来的p，原来的p变成z的右孩子。 - 在旋转后，
z和p交换了角色。将z指向新的父节点 (原来的p)。
- 如果
- 解释： 这一步是为了将 Zig-Zag 情况转换为 Zig-Zig 情况 (情况3)，方便后续处理。旋转后，新的
z(原来的p) 和其父节点 (原来的z) 以及祖父节点g会形成一条直线。 - 现在
z是外侧孩子，进入情况3。
(例如：p是左子节点，z是p的右子节点)G(B) G(B)/ \ / \P(R) U(B) --左旋(P)--> z(R) U(B) <-- 旧p成为z的子节点/ \ / \ <-- z成为情况3的新pz(R) P(R)/(旧z的左子节点，如果有) - 动作：
-
情况3:
z的叔叔u是黑色 (或 NIL)，且z是p的外侧孩子 (Zig-Zig 情况)。
(例如,p是g的左孩子,z是p的左孩子；或者p是g的右孩子,z是p的右孩子)- 动作：
- 将
p(父) 设为黑色。 - 将
g(祖父) 设为红色。 - 如果
z == p->left(左-左情况): 对g右旋。 - 如果
z == p->right(右-右情况): 对g左旋。
- 将
- 解释： 通过变色和一次旋转，红-红冲突被解决。旋转后，原来的
p成为子树的根，颜色为黑，其子节点z(原当前节点) 和g(原祖父) 均为红色，满足性质4。由于p替代了原来黑色的g的位置，路径的黑色高度也得以保持。调整完成。
(例如：p是左子节点，z是p的左子节点 - 左-左)G(B) P(B)/ \ / \P(R) U(B) --右旋(G)--> z(R) G(R)/ \z(R) U(B) - 动作：
循环结束后：
最后，无论如何，将根节点 root 设为黑色 (满足性质2)。
// 在红黑树类中
// Node* root; (在构造函数中初始化为NIL)
// Node* NIL; (全局或静态成员，已初始化)void left_rotate(Node* x); // 见第5节
void right_rotate(Node* x); // 见第5节void insert_fixup(Node* z) {// 如果z是根节点，将其着色为黑色并退出if (z == root) {z->color = BLACK;return;}// 如果父节点是黑色，不需要修复if (z->parent->color == BLACK) {return;}// 当z不是根节点且父节点为红色时（违反性质4）while (z != root && z->parent->color == RED) {if (z->parent == z->parent->parent->left) { // 父节点是祖父节点的左子节点Node* y = z->parent->parent->right; // 叔叔节点if (y->color == RED) { // 情况1：叔叔节点是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent; // 将z移动到祖父节点} else { // 叔叔节点是黑色if (z == z->parent->right) { // 情况2：z是右子节点（左-右情况）z = z->parent;left_rotate(z);}// 情况3：z是左子节点（左-左情况，或情况2变换后）z->parent->color = BLACK;z->parent->parent->color = RED;right_rotate(z->parent->parent);}} else { // 父节点是祖父节点的右子节点（对称情况）Node* y = z->parent->parent->left; // 叔叔节点if (y->color == RED) { // 情况1：叔叔节点是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else { // 叔叔节点是黑色if (z == z->parent->left) { // 情况2：z是左子节点（右-左情况）z = z->parent;right_rotate(z);}// 情况3：z是右子节点（右-右情况，或情况2变换后）z->parent->color = BLACK;z->parent->parent->color = RED;left_rotate(z->parent->parent);}}}root->color = BLACK; // 确保根节点是黑色
}void insert_node(int key) {Node* z = new Node(key, RED, NIL, NIL, NIL); // 新节点为红色Node* y = NIL; // 追踪指针Node* x = root; // 当前指针while (x != NIL) {y = x;if (z->key < x->key) {x = x->left;} else {x = x->right;}}z->parent = y;if (y == NIL) { // 树为空root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}// z->left和z->right已在构造函数中设为NILinsert_fixup(z);
}
c. 删除 (Delete)
删除操作是红黑树中最复杂的操作。
- 标准 BST 删除：
- 首先找到要删除的节点
z。 - 如果
z最多只有一个孩子：直接删除z，用其唯一的孩子（或NIL）替换它。 - 如果
z有两个孩子：找到z的中序后继y(即z右子树中的最小节点)。用y的键值替换z的键值，然后问题转化为删除节点y。此时y最多只有一个右孩子 (因为y是其子树中最小的，所以它没有左孩子)。
- 首先找到要删除的节点
- 实际被物理删除的节点
y和其替代者x：- 经过上述步骤，我们总能确定一个节点
y，它是实际要从树中物理移除的节点。y最多只有一个非NIL的子节点。 - 令
x为y的那个唯一的孩子（如果存在），或者NIL（如果y没有孩子）。x将会取代y在树中的位置。
- 经过上述步骤，我们总能确定一个节点
- 修复 (
delete_fixup(x)):- 如果被删除的节点
y的颜色是 红色：- 删除红色节点
y不会违反任何红黑树性质。红色节点不影响黑色高度，删除它也不会造成红-红冲突（因为它的子节点x必然是黑色，根据性质4）。所以操作完成。
- 删除红色节点
- 如果被删除的节点
y的颜色是 黑色：- 删除黑色节点
y会导致经过y的路径上的黑色节点数量减少1，从而违反性质5 (黑色高度)。 - 同时，如果
x(替代者) 是红色且x的父节点 (原来y的父节点) 也是红色，则会违反性质4。 - 为了修复，我们视
x为一个"额外"的黑色。如果x原本是红色，它现在就变成了"红加黑"，即一个普通的黑色节点，修复完成。 - 如果
x原本是黑色 (包括NIL节点)，它现在就变成了"双重黑色 (doubly black)"。这意味着x所在位置需要一个额外的黑色来弥补被删除的y的黑色。这时就需要调用delete_fixup(x)。
- 删除黑色节点
- 如果被删除的节点
删除修复 (delete_fixup(x)) 逻辑：
循环条件：只要 x 不是根节点，并且 x 的颜色是黑色 (表示它仍带有"双黑"属性)。
令 p = x->parent。令 s 为 x 的兄弟节点。
-
情况1:
x的兄弟s是红色。- 动作：
- 将
s设为黑色。 - 将
p(父) 设为红色。 - 如果
x是p的左孩子，对p左旋；否则对p右旋。 - 更新
s为x的新兄弟节点 (它现在是原来s的一个孩子，并且是黑色的)。
- 将
- 解释： 这个操作将情况1转换为情况2、3或4中的一种，即
x的兄弟是黑色的情况。旋转后x的新兄弟是黑色的，并且x的父节点p变成了红色。路径的黑色高度不变。
(x是左子节点，s是红色右子节点)P(B/R) S(B)/ \ / \x(DB) S(R) --左旋(P)--> P(R) S_子右(B/R)/ \ / \S左(B) S右(B) x(DB) S左(B) <-- s现在是S左 - 动作：
-
情况2:
x的兄弟s是黑色，且s的两个孩子都是黑色。- 动作：
- 将
s(兄弟) 设为红色。 - 将当前节点
x设为p(父) (x = p)。
- 将
- 解释： 将
s变红，这样x和s子树的黑色高度都减少了1。这个"双黑"问题就被推给了父节点p。如果p原本是红色，现在变黑，问题解决。如果p原本是黑色，它现在变成了新的"双黑"节点，继续循环。
P(B/R) P(原B->DB, 原R->B)/ \ / \x(DB) S(B) ---> x(B) S(R)/ \ / \S左(B) S右(B) S左(B) S右(B) - 动作：
-
情况3:
x的兄弟s是黑色，s的靠近x的孩子是红色，s的远离x的孩子是黑色。
(例如,x是左孩子,s->left是红色,s->right是黑色)- 动作：
- 将
s->left(或s->right，如果x是右孩子) 设为黑色。 - 将
s设为红色。 - 如果
x是p的左孩子，对s右旋；否则对s左旋。 - 更新
s为x的新兄弟节点 (它现在是原来s->left或s->right，并且是黑色的)。
- 将
- 解释： 这个操作将情况3转换为情况4。旋转后，
x的新兄弟节点是黑色的，并且其远离x的孩子是红色的。
(x是左子节点)P(B/R) P(B/R)/ \ / \x(DB) S(B) ---> x(DB) S左(B) <-- 新S/ \ \S左(R) S右(B) S(R)\S右(B) - 动作：
-
情况4:
x的兄弟s是黑色，且s的远离x的孩子是红色。
(例如,x是左孩子,s->right是红色)- 动作：
- 将
s的颜色设为p(父) 的颜色。 - 将
p(父) 设为黑色。 - 将
s的远离x的孩子 (例如s->right) 设为黑色。 - 如果
x是p的左孩子，对p左旋；否则对p右旋。 - 将
x设为根节点 (这会终止循环)。
- 将
- 解释： 这是最终解决"双黑"问题的步骤。通过旋转和变色，额外的黑色被消除，并且所有红黑树性质都得到恢复。
p的旋转将兄弟s提升，其红色子节点用于平衡黑色高度。
(x是左子节点，s->right是红色)P(颜色P) S(颜色P)/ \ / \x(DB) S(B) --左旋(P)--> P(B) S右(B)/ \ / \S左(B/R) S右(R) x(B) S左(B/R) - 动作：
循环结束后：
如果 x 不是 NIL，将 x 的颜色设为黑色。这可以安全地吸收任何剩余的"双黑" (如果 x 是根) 或确保性质。
辅助函数 transplant(u, v):
用节点 v 替换子树 u。它负责更新 u 的父节点指向 v，以及 v 的父节点指向 u 的父节点。
void transplant(Node* u, Node* v) {if (u->parent == NIL) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}v->parent = u->parent; // 即使v是NIL，NIL->parent也应被设置
}Node* tree_minimum(Node* node) {while (node->left != NIL) {node = node->left;}return node;
}void delete_fixup(Node* x) {Node* s; // 兄弟节点while (x != root && x->color == BLACK) {if (x == x->parent->left) { // x是左子节点s = x->parent->right;if (s->color == RED) { // 情况1：兄弟节点s是红色s->color = BLACK;x->parent->color = RED;left_rotate(x->parent);s = x->parent->right; // 更新兄弟节点}// s现在必定是黑色if (s->left->color == BLACK && s->right->color == BLACK) { // 情况2：兄弟节点的两个子节点都是黑色s->color = RED;x = x->parent; // 将双黑问题上移} else {if (s->right->color == BLACK) { // 情况3：兄弟节点的近子节点红色，远子节点黑色s->left->color = BLACK;s->color = RED;right_rotate(s);s = x->parent->right; // 更新兄弟节点}// 情况4：兄弟节点的远子节点是红色s->color = x->parent->color;x->parent->color = BLACK;s->right->color = BLACK;left_rotate(x->parent);x = root; // 问题解决，退出循环}} else { // x是右子节点（对称情况）s = x->parent->left;if (s->color == RED) { // 情况1s->color = BLACK;x->parent->color = RED;right_rotate(x->parent);s = x->parent->left;}if (s->right->color == BLACK && s->left->color == BLACK) { // 情况2s->color = RED;x = x->parent;} else {if (s->left->color == BLACK) { // 情况3s->right->color = BLACK;s->color = RED;left_rotate(s);s = x->parent->left;}// 情况4s->color = x->parent->color;x->parent->color = BLACK;s->left->color = BLACK;right_rotate(x->parent);x = root;}}}x->color = BLACK; // 确保x是黑色（例如，如果它成为根节点并且原本是红色）
}void delete_node_val(int key) {Node* z = search(root, key);if (z == NIL) return; // 节点未找到Node* y = z; // y是要被物理移除或移动的节点Node* x; // x是替换y的子节点Color y_original_color = y->color;if (z->left == NIL) {x = z->right;transplant(z, z->right);} else if (z->right == NIL) {x = z->left;transplant(z, z->left);} else {y = tree_minimum(z->right); // y是z的后继y_original_color = y->color;x = y->right; // x是y的右子节点（y的左子节点为NIL）if (y->parent == z) {x->parent = y; // 重要，如果x是NIL} else {transplant(y, y->right);y->right = z->right;y->right->parent = y;}transplant(z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}// 删除z节点（内存释放）if (y != z) {// 如果y是z的后继，实际上z的内容已被y的内容替换，并且y节点位置已被调整// 此时z指向原来的y节点位置，应该删除zdelete z;} else {// 如果y就是z（z至多只有一个子节点），直接删除zdelete z;}if (y_original_color == BLACK) {delete_fixup(x);}
}
5. 维护平衡的关键操作
a. 变色 (Recoloring)
改变节点的颜色（红色变黑色，黑色变红色）。这是最简单的操作，用于调整节点颜色以满足红黑树的性质，通常不改变树的结构，或者作为旋转操作的一部分。变色本身非常快，是 O(1) 操作。
b. 旋转 (Rotations)
旋转操作用于改变树的局部结构，重新组织节点间的父子关系，同时保持二叉查找树的性质（即中序遍历顺序不变）。旋转的目的是在不破坏 BST 性质的前提下，调整节点间的父子关系，以帮助恢复红黑树的性质（特别是性质4 - 无连续红节点，和性质5 - 黑色高度）。旋转是 O(1) 操作。
-
左旋 (Left Rotation) on node
x:
假设x有一个右孩子y(y 不能是NIL)。左旋使y成为新的子树根，x成为y的左孩子。y原来的左孩子B成为x的右孩子。父节点 父节点| |x y/ \ / \A y --左旋(x)--> x C/ \ / \B C A B步骤：
y = x->rightx->right = y->left(将B过继给x)- 如果
y->left != NIL, 则y->left->parent = x y->parent = x->parent(y连接到x的原父节点)- 如果
x->parent == NIL(x是根), 则root = y - 否则，如果
x == x->parent->left, 则x->parent->left = y - 否则 (
x == x->parent->right), 则x->parent->right = y y->left = xx->parent = y
-
右旋 (Right Rotation) on node
x:
假设x有一个左孩子y(y 不能是NIL)。右旋使y成为新的子树根，x成为y的右孩子。y原来的右孩子B成为x的左孩子。父节点 父节点| |x y/ \ / \y C --右旋(x)--> A x/ \ / \A B B C步骤 (对称于左旋)：
y = x->leftx->left = y->right(将B过继给x)- 如果
y->right != NIL, 则y->right->parent = x y->parent = x->parent- 如果
x->parent == NIL, 则root = y - 否则，如果
x == x->parent->right, 则x->parent->right = y - 否则 (
x == x->parent->left), 则x->parent->left = y y->right = xx->parent = y
// 在红黑树类中
// Node* root;
// Node* NIL;void left_rotate(Node* x) {Node* y = x->right; // 设置yx->right = y->left; // 将y的左子树变为x的右子树if (y->left != NIL) {y->left->parent = x;}y->parent = x->parent; // 将x的父节点链接到yif (x->parent == NIL) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x; // 将x放到y的左侧x->parent = y;
}void right_rotate(Node* x) {Node* y = x->left; // 设置yx->left = y->right; // 将y的右子树变为x的左子树if (y->right != NIL) {y->right->parent = x;}y->parent = x->parent; // 将x的父节点链接到yif (x->parent == NIL) {root = y;} else if (x == x->parent->right) {x->parent->right = y;} else {x->parent->left = y;}y->right = x; // 将x放到y的右侧x->parent = y;
}
6. 红黑树的优缺点
优点：
- 性能保证： 所有基本操作（查找、插入、删除）在最坏情况下的时间复杂度都是 O(log N)。这是其最重要的特性。
- 相对高效的插入/删除： 相较于 AVL 树（另一种自平衡 BST），红黑树在插入和删除时需要的旋转次数较少（AVL 树可能需要
O(log N)次旋转，红黑树插入最多2次，删除最多3次旋转）。变色操作虽然可能沿着路径向上传播，但总体上写操作的平均常量因子较低。 - 广泛应用： 由于其稳定的性能和相对 AVL 树更优的写操作效率，许多标准库和系统组件都采用红黑树。
- 空间开销小： 每个节点只需要额外存储一位颜色信息（1 bit）。
缺点：
- 实现复杂： 相较于普通 BST，红黑树的插入和删除操作涉及到多种情况的判断、变色和旋转，实现起来要复杂得多，容易出错。删除操作尤其复杂。
- 查找性能略逊于 AVL 树： 由于红黑树的平衡性不如 AVL 树严格（红黑树的最长路径可以是最短路径的2倍，AVL树是高度差最多1），其树高可能略大于 AVL 树。因此，在纯查找密集型应用中，AVL 树理论上可能略快一点（但两者都是 O(log N) 级别，实际差异通常不大）。
- 理解难度： 各种修复情况的逻辑和它们如何维持红黑性质的证明比较微妙，学习曲线较陡峭。
7. 应用场景
跳表的性能和红黑树接近，但是实现较为简单，这也是redis使用跳表而不是红黑树的原因之一。
红黑树因其高效和稳定的性能，在需要频繁进行查找、插入和删除操作的动态数据集合中得到广泛应用：
- 关联数组/映射表 (Associative Arrays/Maps)：
- C++ STL:
std::map,std::multimap,std::set,std::multiset。 - Java:
java.util.TreeMap,java.util.TreeSet。
- C++ STL:
- 进程调度：
- Linux 内核的 Completely Fair Scheduler (CFS) 使用红黑树来管理任务队列，确保进程按虚拟运行时间公平地获得 CPU。
- 内存管理：
- 在某些操作系统的内核或用户态内存分配器中，用于管理空闲内存块，可以快速找到合适大小的块或合并相邻块。
- IO 多路复用：
- 如 Linux 的
epoll在内核中可能使用红黑树来管理被监控的文件描述符集合，以便高效地添加、删除和查找事件。
- 如 Linux 的
- 数据库索引：
- 虽然 B树及其变种在磁盘存储的数据库中更常见，但某些内存数据库或特定类型的索引可能会使用红黑树或其变种。
- 几何计算：
- 例如，计算几何中的区间树 (Interval Tree) 可以基于红黑树构建。
8. 简单性能对比
- 插入操作
- 查找
- 删除
9. 完整代码实现
以下是红黑树的完整C++实现，包含了所有基本操作和辅助方法：
#include <iostream>// 颜色定义
enum Color { RED, BLACK };// 节点结构体
struct Node {int key;Color color;Node *parent;Node *left;Node *right;// 构造函数 (新节点通常为红色)Node(int k, Color c = RED, Node* p = nullptr, Node* l = nullptr, Node* r = nullptr): key(k), color(c), parent(p), left(l), right(r) {}
};// 红黑树类
class RedBlackTree {
private:Node* root; // 根节点Node* NIL; // 哨兵节点，表示所有叶子节点// 左旋操作void left_rotate(Node* x) {Node* y = x->right; // 设置y为x的右子节点x->right = y->left; // 将y的左子树变为x的右子树if (y->left != NIL) {y->left->parent = x;}y->parent = x->parent; // 连接x的父节点到yif (x->parent == NIL) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x; // 将x放到y的左侧x->parent = y;}// 右旋操作void right_rotate(Node* x) {Node* y = x->left; // 设置y为x的左子节点x->left = y->right; // 将y的右子树变为x的左子树if (y->right != NIL) {y->right->parent = x;}y->parent = x->parent; // 连接x的父节点到yif (x->parent == NIL) {root = y;} else if (x == x->parent->right) {x->parent->right = y;} else {x->parent->left = y;}y->right = x; // 将x放到y的右侧x->parent = y;}// 插入后修复红黑树属性void insert_fixup(Node* z) {// 如果z是根节点，将其着色为黑色并退出if (z == root) {z->color = BLACK;return;}// 如果父节点是黑色，不需要修复if (z->parent->color == BLACK) {return;}// 当父节点是红色时（违反性质4）while (z != root && z->parent->color == RED) {if (z->parent == z->parent->parent->left) { // 父节点是祖父节点的左子节点Node* y = z->parent->parent->right; // 叔叔节点if (y->color == RED) { // 情况1：叔叔节点是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent; // 将z移动到祖父节点} else { // 叔叔节点是黑色if (z == z->parent->right) { // 情况2：z是右子节点（左-右情况）z = z->parent;left_rotate(z);}// 情况3：z是左子节点（左-左情况，或情况2变换后）z->parent->color = BLACK;z->parent->parent->color = RED;right_rotate(z->parent->parent);}} else { // 父节点是祖父节点的右子节点（对称情况）Node* y = z->parent->parent->left; // 叔叔节点if (y->color == RED) { // 情况1：叔叔节点是红色z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else { // 叔叔节点是黑色if (z == z->parent->left) { // 情况2：z是左子节点（右-左情况）z = z->parent;right_rotate(z);}// 情况3：z是右子节点（右-右情况，或情况2变换后）z->parent->color = BLACK;z->parent->parent->color = RED;left_rotate(z->parent->parent);}}}root->color = BLACK; // 确保根节点是黑色}// 替换子树void transplant(Node* u, Node* v) {if (u->parent == NIL) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}v->parent = u->parent; // 即使v是NIL，也设置NIL->parent}// 找到树中最小键值的节点Node* tree_minimum(Node* node) {while (node->left != NIL) {node = node->left;}return node;}// 删除后修复红黑树属性void delete_fixup(Node* x) {Node* s; // 兄弟节点while (x != root && x->color == BLACK) {if (x == x->parent->left) { // x是左子节点s = x->parent->right;if (s->color == RED) { // 情况1：兄弟节点s是红色s->color = BLACK;x->parent->color = RED;left_rotate(x->parent);s = x->parent->right; // 更新兄弟节点}// s现在必定是黑色if (s->left->color == BLACK && s->right->color == BLACK) { // 情况2：兄弟节点的两个子节点都是黑色s->color = RED;x = x->parent; // 将双黑问题上移} else {if (s->right->color == BLACK) { // 情况3：兄弟节点的近子节点为红色，远子节点为黑色s->left->color = BLACK;s->color = RED;right_rotate(s);s = x->parent->right; // 更新兄弟节点}// 情况4：兄弟节点的远子节点是红色s->color = x->parent->color;x->parent->color = BLACK;s->right->color = BLACK;left_rotate(x->parent);x = root; // 问题解决，退出循环}} else { // x是右子节点（对称情况）s = x->parent->left;if (s->color == RED) { // 情况1s->color = BLACK;x->parent->color = RED;right_rotate(x->parent);s = x->parent->left;}if (s->right->color == BLACK && s->left->color == BLACK) { // 情况2s->color = RED;x = x->parent;} else {if (s->left->color == BLACK) { // 情况3s->right->color = BLACK;s->color = RED;left_rotate(s);s = x->parent->left;}// 情况4s->color = x->parent->color;x->parent->color = BLACK;s->left->color = BLACK;right_rotate(x->parent);x = root;}}}x->color = BLACK; // 确保x是黑色（例如，如果它成为根节点并且原本是红色）}// 中序遍历辅助函数void inorder_helper(Node* node) {if (node != NIL) {inorder_helper(node->left);std::cout << node->key << "(" << (node->color == RED ? "红" : "黑") << ") ";inorder_helper(node->right);}}// 打印辅助函数void print_helper(Node* node, int indent) {if (node != NIL) {print_helper(node->right, indent + 4);for (int i = 0; i < indent; i++) {std::cout << " ";}std::cout << node->key << "(" << (node->color == RED ? "红" : "黑") << ")" << std::endl;print_helper(node->left, indent + 4);}}// 递归清理节点void clear(Node* node) {if (node != NIL) {clear(node->left);clear(node->right);delete node;}}public:// 构造函数RedBlackTree() {NIL = new Node(0, BLACK);NIL->parent = NIL;NIL->left = NIL;NIL->right = NIL;root = NIL;}// 析构函数~RedBlackTree() {clear(root);delete NIL;}// 查找节点Node* search(int key) {Node* current = root;while (current != NIL && current->key != key) {if (key < current->key) {current = current->left;} else {current = current->right;}}return current; // 如果未找到则返回NIL}// 插入节点void insert(int key) {Node* z = new Node(key, RED, NIL, NIL, NIL); // 新节点为红色Node* y = NIL; // 追踪指针Node* x = root; // 当前指针// 找到插入位置while (x != NIL) {y = x;if (z->key < x->key) {x = x->left;} else {x = x->right;}}z->parent = y;if (y == NIL) { // 树为空root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}// z->left和z->right已在构造函数中设为NIL// 修复红黑树属性insert_fixup(z);}// 删除节点void remove(int key) {Node* z = search(key);if (z == NIL) return; // 节点未找到Node* y = z; // y是将被物理移除或移动的节点Node* x; // x是替换y的子节点Color y_original_color = y->color;if (z->left == NIL) {x = z->right;transplant(z, z->right);} else if (z->right == NIL) {x = z->left;transplant(z, z->left);} else {y = tree_minimum(z->right); // y是z的后继y_original_color = y->color;x = y->right; // x是y的右子节点（y的左子节点为NIL）if (y->parent == z) {x->parent = y; // 重要，如果x是NIL} else {transplant(y, y->right);y->right = z->right;y->right->parent = y;}transplant(z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}// 删除z节点（内存释放）if (y != z) {// 如果y是z的后继，实际上z的内容已被y的内容替换，并且y节点位置已被调整// 此时z指向原来的y节点位置，应该删除zdelete z;} else {// 如果y就是z（z至多只有一个子节点），直接删除zdelete z;}if (y_original_color == BLACK) {delete_fixup(x);}}// 中序遍历（用于验证）void inorder() {std::cout << "中序遍历：";inorder_helper(root);std::cout << std::endl;}// 打印红黑树（简化版，实际应用需要更复杂的显示逻辑）void print() {std::cout << "红黑树结构：" << std::endl;print_helper(root, 0);std::cout << std::endl;}// 检查是否为空bool isEmpty() {return root == NIL;}// 获取树的大小int size() {return size_helper(root);}// 计算树大小的辅助函数int size_helper(Node* node) {if (node == NIL) {return 0;}return 1 + size_helper(node->left) + size_helper(node->right);}// 检查树是否包含特定键值bool contains(int key) {return search(key) != NIL;}// 清空树void clear() {clear(root);root = NIL;}
};// 主函数示例
int main() {RedBlackTree rbt;// 插入一些值std::cout << "插入节点: 10, 20, 30, 15, 5, 25, 40, 18, 22" << std::endl;rbt.insert(10);rbt.insert(20);rbt.insert(30);rbt.insert(15);rbt.insert(5);rbt.insert(25);rbt.insert(40);rbt.insert(18);rbt.insert(22);// 打印树结构rbt.print();// 中序遍历rbt.inorder();// 查找操作演示std::cout << "\n查找操作:" << std::endl;std::cout << "树中包含15: " << (rbt.contains(15) ? "是" : "否") << std::endl;std::cout << "树中包含100: " << (rbt.contains(100) ? "是" : "否") << std::endl;// 删除操作演示std::cout << "\n删除值 15:" << std::endl;rbt.remove(15);rbt.print();rbt.inorder();std::cout << "\n删除值 10 (根节点):" << std::endl;rbt.remove(10);rbt.print();rbt.inorder();// 树的统计信息std::cout << "\n树的节点数量: " << rbt.size() << std::endl;std::cout << "树是否为空: " << (rbt.isEmpty() ? "是" : "否") << std::endl;// 清空树std::cout << "\n清空树后:" << std::endl;rbt.clear();std::cout << "树的节点数量: " << rbt.size() << std::endl;std::cout << "树是否为空: " << (rbt.isEmpty() ? "是" : "否") << std::endl;return 0;
}
