登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›红黑树及C++代码实现

红黑树及C++代码实现

碛物 2025-5-31 23:58:54
红黑树及C++代码实现

红黑树是二叉搜索树的一种，单次插入、删除、查询的时间复杂度都是\(O(log(n))\)。红黑树的应用广泛，STL的set和map、Java的TreeSet和TreeMap等都是使用红黑树实现的
哨兵节点

在红黑树中，所有的叶子节点、根节点的父节点都是一个名为哨兵节点的节点。哨兵节点用于处理边界条件，可以很方便的识别树的边缘，用NIL来表示。哨兵节点替代的是原来空指针的作用，哨兵节点可以降低访问空指针的风险，同时也可以简化代码中的逻辑判断
性质

一颗红黑树必须满足下面五条性质：

  • 节点为红色或黑色
  • 根节点为黑色
  • NIL节点为黑色
  • 红色节点的子节点为黑色
  • 从根节点到NIL节点的简单路径上的黑色节点数量相同（又或者说从任意一个节点出发到达NIL节点的所有简单路径所经过的黑色节点数量相同）
思考下面的二叉树是否为红黑树
  1.         root(B)
  2.           \
  3.           N(R)
  4.           / \
  5.       NL(B) NR(B)
复制代码
乍一看好像是红黑树，因为根节点到NL和NR的路径上的黑色节点数相同。但实际上这颗树并不是红黑树，将NIL节点画出来一目了然
  1.         root(B)
  2.         / \
  3.       NIL  N(R)
  4.           / \
  5.       NL(B) NR(B)
  6.       / \    / \
  7.     NIL NIL NIL NIL
复制代码
注意到根节点到达NIL节点有5条路径，经过的黑色节点（NIL算作黑色节点）数量分别为2、3、3、3、3，并不是全相等的，所以这颗二叉树不是红黑树
同时这也解释了为什么要使用哨兵节点
为什么红黑树效率高

从红黑树的性质出发，在不考虑NIL节点的情况下，假设根节点到叶节点的路径上经过的黑色节点数为\(r\)，假设树的高度为\(h\)，那么有

\[r \le h \le 2r\]
其实很好理解，在没有红色节点的情况下，路径上至少都会有\(r\)个黑色节点。有红色节点的情况下，路径节点最多的情况应该是黑红相间
假设红黑树中有\(n\)个节点（不包含NIL节点）那么有

\[n \ge 2^r - 1\]
节点最少的情况下，节点应该全为黑色，此时红黑树是一颗满二叉树（红黑树的性质决定）
  1.              root(B)
  2.               / \
  3.       N(R)           S(B)
  4.       / \            / \
  5.   NL(B) NR(B)     SL(B) SR(B)
  6.   / \    / \      / \    / \
  7. NIL NIL NIL NIL NIL NIL NIL NIL
复制代码
上面的红黑树的高度为3（不计NIL节点），其节点数为\(2^3-1\)，对于全黑的红黑树，其节点数为\(2^r - 1\)
而在全黑的情况下，我们还可以加上一些红色节点，也不会破坏红黑树的性质5，所以有\(n \ge 2^r - 1\)
做一个变形

\[r \le log_2(n + 1)\]
又因为\(r\le h \le 2r\)
所以可以得到树高\(h\)，与节点数\(n\)的关系

\[log_2(n + 1) \le h \le 2log_2(n + 1)\]
红黑树又是一颗二叉搜索树，二叉搜索树进行插入、删除、查找的复杂度取决于树的最大高度，于是我们就可以知道红黑树进行插入、删除、查找的复杂度为\(O(log(n))\)
为什么使用红黑树而不是AVL树

AVL树的最大高度大约为\(\lfloor log_2(n) \rfloor + 1\)，比红黑树少一个常数，那为什么STL和Java使用红黑树而不使用AVL树呢？
AVL树的高度小于红黑树，这让它在查询操作的表现比红黑树更加优秀，因为查询操作并不会改变树的结构。但是在面对大量数据写入和删除的情况，AVL树为了保持平衡性，会经常进行旋转，以保证AVL树的左子树和右子树的高度差不超过1。而红黑树对树结构的要求并不像AVL树那么严格，旋转的次数会少于AVL树。这就导致红黑树的整体性能比AVL树更加优秀
旋转

旋转操作用于调整树的结构，很常用
左旋

假如对P点左旋，那么将P的右节点B变为P的父节点，将P变为其左节点A的父节点，将P的右节点B的左节点BL变为P的右节点
  1.        P                                                 B
  2.       / \                     P点左旋                    / \
  3.    A       B                  ----->                  P    BR
  4.   / \     / \                                        / \
  5. AL AR   BL BR                                      A   BL
  6.                                                    / \
  7.                                                   AL AR
复制代码
右旋

与左旋完全反过来
假如对P点右旋，那么将P的左节点A变为P的父节点，将P变为其右节点B的父节点，将P的左节点A的右节点AR变为P的左节点
  1.        P                                                 A
  2.       / \                     P点右旋                    / \
  3.    A       B                  ----->                   AL  P
  4.   / \     / \                                             / \
  5. AL AR   BL BR                                           AR  B
  6.                                                             / \
  7.                                                            BL BR
复制代码
插入

插入节点颜色选取

根据红黑树的性质，节点必须为红色或者黑色中的一种。那么对于插入操作，插入的节点应该是什么颜色呢？
如果插入节点为黑色，那么我们将节点插入以后，红黑树的性质5一定会被打破，有一条路径上的黑色节点数会增加1，好像并不好调整，如果要调整，我们就需要将路径上的一个节点变为红色，以保证性质5成立，但是一个节点变为红色又可能会打破性质4
如果插入节点为红色，那么我们将节点插入以后，红黑树的性质5不会被打破，但性质4却也有可能会被打破
而在后面可以知道，连续两个红色节点是可以调整的
插入红色节点可以省去变红的操作，更加方便。因此选择红色作为插入节点的颜色
Case 1：树为空

直接插入节点，并将节点的颜色变为黑色
Case 2：父节点为黑色节点

直接插入，不需要额外操作
Case 3：父节点为红色节点


  • 叔叔节点为红色节点
    将父节点以及叔叔节点变为黑色，将祖先节点变为红色。但是调整后祖先节点的父节点可能为红色，违反了性质4，因此我们需要递归的去调整祖先节点，直到没有冲突出现
    1.         G(B)                  G(R)
    2.        /   \                 /   \
    3.      P(R) U(R)   ----->   P(B)   U(B)
    4.      /                   /
    5.    N(R)               N(R)
    复制代码
  • 叔叔节点为黑色，且插入节点与父节点同为左节点或右节点
    这种情况可以直接调整，将祖先节点G旋转，方向与父节点P方向相反，旋转后将父节点变成黑色，祖先节点变为红色
    1.      G(B)                 P(B)
    2.      / \         G左旋    /   \
    3.    U(B) P(R)    ----->  G(R)   N(R)
    4.          \             /
    5.           N(R)       U(B)
    复制代码
  • 叔叔节点为黑色，且插入节点与父节点方向相反
    这种情况可以转换为上面一种情况，从而直接进行调整。先将父节点P旋转，旋转方向与插入节点的方向相反，旋转后即可按照上面一种情况调整
    1.      G(B)                G(B)                 N(B)
    2.     /  \       P右旋     /  \       G左旋     /   \
    3.   U(B) P(R)   -----> U(B)   N(R)   ----->  G(R)   P(R)
    4.        /                     \
    5.      N(R)                    P(R)
    复制代码
删除

双黑节点

在进行删除操作之前，有必要先了解一下双黑节点是什么
在红黑树中，双黑节点（Double Black Node） 是一个逻辑标记，用于表示在删除操作后某个位置需要“补足”一个额外的黑色节点，以维护红黑树的黑高一致性（所有路径的黑色节点数量相同）。它本身不是一种真实的颜色，而是修复红黑树性质时的一种临时状态。
从上面的解释中可以知道，如果某节点被打上双黑节点标记，就意味着这个节点会额外算作一个黑色节点，以保证红黑树的性质。但一个节点不能扮演两个角色，我们需要通过旋转、变色等操作将双黑节点标记消除（注意双黑节点是一个逻辑标记），消除后整棵树仍然是红黑树。
在删除操作时，如果出现了双黑节点，不会立即调整树的结构，而是在之后的删除调整操作进行统一的操作
近侄节点与远侄节点


  • 近侄节点：兄弟节点靠近删除节点的子节点
  • 远侄节点：兄弟节点远离删除节点的子节点
  1.       P
  2.      / \
  3.     N   S
  4.        / \
  5.       SL SR
复制代码
现在有上面一棵树，对于节点N来说，S为N的兄弟节点，SL则为N的近侄节点，SR则为N的远侄节点
Case 1：删除节点为树中唯一节点

若删除节点为树中的唯一节点，直接删除即可
Case 2：删除节点没有非NIL的子节点


  • 删除节点为红色节点
    如果删除的节点为红色，直接删除即可，删除后的树依旧是一颗红黑树，满足红黑树的五条性质
    1.              P(?)                                         P(?)
    2.          / \               删除后                      / \
    3.     N(R)     S(?)         ------>                   NIL S(?)
    4.     / \      / \                                        / \
    5.   NIL NIL SL(?) SR(?)                                SL(?) SR(?)
    复制代码
  • 删除的节点为黑色节点
    1.              P(?)
    2.          / \
    3.     N(B)     S(?)
    4.     / \      / \
    5.   NIL NIL SL(?) SR(?)
    复制代码
    我们首先删除需要删除的节点N，补上一个NIL节点，所补的NIL节点会被打上双黑节点标记，我们用C来表示这个NIL节点
    如果C节点只算做一个黑色节点，那么肯定是不满足性质5的，但是如果C节点算作两个黑色节点，那么就满足性质5了。在后面的删除调整操作我们考虑如何将双黑节点标记去除掉
    1.              P(?)                                     P(?)
    2.          / \                                      / \
    3.     N(B)     S(?)            ------>           C(DB) S(?)
    4.     / \      / \                                     / \
    5.   NIL NIL SL(?) SR(?)                            SL(?)  SR(?)
    复制代码
Case 3：删除节点有且仅有一个非NIL的子节点

这种情况下删除节点只能是黑色，并且删除节点的非NIL子节点只能是红色

  • 如果删除节点是红色，那么删除节点的非NIL子节点一定为黑色，只有这样才能满足性质4。但是注意，从删除节点出发，如果直接走NIL子节点方向，那么路径上经过的黑色节点数为1，但走非NIL子节点方向，路径上经过的黑色节点数是大于1的，至少有非NIL子节点和非NIL子节点下面的NIL子节点两个黑色节点，因此该情况不满足红黑树的性质。
    1.     N(R)   
    2.     / \   
    3.   NIL NR(B)
    4.             / \
    5.     NIL NIL
    复制代码
  • 如果删除节点是黑色，删除节点的非NIL节点也为黑色，如同第一种情况，从删除节点出发，走NIL节点方向，路径上经过2个黑色节点，而走非NIL节点方向，路径上至少经过3个黑色节点，因此该情况也不满足红黑树的性质
    1.     N(B)   
    2.     / \   
    3.   NIL NR(B)
    4.             / \
    5.     NIL NIL
    复制代码
因此删除节点只能是黑色，删除节点的非NIL子节点只能是红色
对于这种情况，可以直接调整。删除节点，用非NIL子节点代替该节点，并将节点颜色变成黑色
  1.              P(?)                           P(?)
  2.          /                              /
  3.     N(B)                              NR(B)
  4.     / \                               / \
  5.   NIL NR(R)         ----->          NIL NIL
  6.        / \
  7.      NIL NIL
复制代码
Case 4：删除节点有两个非NIL的子节点

这种情况我们需要找到删除节点的后继节点，即右子树中最小的节点，然后交换两个节点，颜色不交换，然后继续删除需要删除的节点
此时会发现，删除的情况变成了Case 2或者Case 3
这是因为二叉搜索树的后继节点没有左节点，因此后继节点最多只有一个非NIL节点
删除调整

删除调整操作的目的是为了去除在删除过程中出现的双黑节点标记，下面会分成几种情况进行讨论
Case 1: 兄弟节点为黑色且兄弟节点的两个子节点为黑色


  • 如果父节点为红色
    只需要将兄弟节点S变成红色，父节点P变成黑色就可以直接去掉双黑节点
    1.     P(R)                        P(B)
    2.      / \                        / \
    3. C(DB)  S(B)      ----->      C(B) S(R)
    4.           / \                      / \
    5.        SL(B) SR(B)              SL(B) SR(B)
    复制代码
    调整前后，根节点经过P点到达NIL节点的所有简单路径经过的黑色节点数量是相同的
  • 如果父节点为黑色
    还是先将兄弟节点S变成红色
    但是注意这里并不能像上面那样，直接将S变成红色然后去掉双黑节点就完了，虽然调整后在这颗子树上满足了性质5，但是在整棵树上，经过P节点的路径的黑色节点数会减少一个，与其他路径的黑色节点数量不同，不满足性质5
    因此我们需要为父节点打上双黑节点标记，如果P节点算作两个黑色节点，那么就满足性质5了，然后继续调整父节点P，直到没有双黑节点出现
    1.      P(B)                       P(DB)
    2.      / \                        / \
    3. C(DB)  S(B)       ----->    C(B) S(R)
    4.           / \                      / \
    5.       SL(B)  SR(B)             SL(B) SR(B)
    复制代码
Case 2：兄弟节点为黑色并且远侄节点为红色

这种情况可以直接进行调整
这里以删除节点为父节点的左节点为例，将父节点P进行旋转（删除节点在哪边就往哪边旋转），将兄弟节点S的颜色变为父节点P的颜色，父节点P和远侄节点SR的颜色变为黑色，去掉双黑标记
  1.         P(?)                           S(?)
  2.         / \                            / \
  3.      C(DB) S(B)        左旋          P(B)  SR(B)
  4.           / \         ----->        / \   
  5.       SL(?) SR(R)                 C(B) SL(?)
复制代码
可以看到调整后无论是在局部，还是在整体都是满足红黑树的性质的
Case 3：兄弟节点为黑色并且近侄节点为红色，远侄点为黑色

这种情况需要转换为 Case 2 状态，进而进行调整
这里以删除节点为父节点的左节点为例，将兄弟节点S进行旋转（删除节点在哪边，往反方向旋转），将S的颜色变为红色，将SL的颜色变为黑色，调整后按照 Case 2 继续调整
  1.       P(?)                                 P(?)
  2.       / \                                  / \
  3.    C(DB) S(B)          右旋             C(DB) SL(B)
  4.          / \          ----->                   \
  5.      SL(R)  SR(B)                              S(R)
  6.                                                         \
  7.                                                        SR(B)
复制代码
Case 4：兄弟节点为红色

根据性质4，父节点一定为黑色，兄弟节点的两个子节点一定是黑色
策略是将兄弟节点变成黑色，然后继续调整。
将父节点P进行旋转（删除节点在哪边就往哪边旋转），将兄弟节点S变成黑色，将父节点P变为红色。之后就可以按照前面的情况进行处理了
  1.         P(B)                     S(B)
  2.         / \                      / \
  3.      C(DB) S(R)  ----->       P(R) SR(B)
  4.            / \                / \
  5.        SL(B) SR(B)         C(DB) SL(B)
复制代码
此时SL作为新的兄弟节点，继续调整C(DB)节点
测试

正确性测试

<ul>插入
我们使用洛谷P3879来验证我们的插入是否有问题。经过测试可以AC这道题，通过代码放在最后面（有点长）
1.png

<ul>删除
删除没有找到什么简单的题目，于是就造了一个简单的数据，数据规模为\(10^7\)
下面为生成数据的python代码
  1. import random
  3. in_path = "./data.in"
  4. out_path = "./data.out"
  5. # 数据大小
  6. N = int(1e7)
  7. # 数据范围
  8. minNum = 0
  9. # 最大范围我们取节点数的十倍
  10. maxNum = int(N * 10)
  11. # 删除节点为一般节点
  12. erase_num = N // 2
  14. if __name__ == '__main__':
  15.     # 生成N个区间内不重复的随机数
  16.     x = random.sample(range(minNum, maxNum), N)
  17.     # 获取删除的下标
  18.     idxs = random.sample(range(0, len(x)), erase_num)
  19.     # 获取到需要删除的数
  20.     y = [x[idx] for idx in idxs]
  21.     # 我们要算出哪些还存在，需要进行集合运算
  22.     set_y = set(y)
  23.     set_x = set(x)
  24.     # 计算出最终的答案
  25.     set_y = list(set_x - set_y)
  26.     # 输入
  27.     with open(in_path, mode='w', encoding='utf-8') as f:
  28.         f.write(f"{N}\n")
  29.         for each in x:
  30.             f.write(f"{each}\n")
  31.         f.write(f"{erase_num}\n")
  32.         for each in y:
  33.             f.write(f"{each}\n")
  34.     # 输出
  35.     with open(out_path, mode='w', encoding='utf-8') as f:
  36.         f.write(f"{len(set_y)}\n")
  37.         for each in set_y:
  38.             f.write(f"{each}\n")
复制代码
下面为验证的python代码
  1. import subprocess
  2. import time
  3. from subprocess import *
  5. cpp_path = "./RBTree.cpp"
  6. exe_path = "./RBTree.exe"
  7. test_cpp_path = "./test.cpp"
  8. test_exe_path = "./test.exe"
  9. out_path = "./out.out"
  10. data_path = "./data.out"
  11. in_path = "./data.in"
  13. with open(in_path,"r",encoding="utf-8") as f :
  14.     stdin = f.read()
  16. compile_res = subprocess.run(["g++",cpp_path,"-o",exe_path],capture_output=True,text=True,timeout=5)
  17. # 编译成功
  18. if compile_res.returncode == 0:
  19.     st = time.time()
  20.     run_res = subprocess.run([exe_path],input=stdin,capture_output=True,text=True,timeout=100)
  21.     ed = time.time()
  22.     print(f"running time: {(ed - st) * 1000.0}ms")
  23.     out = run_res.stdout
  24.     with open(out_path, "w", encoding="utf-8") as f:
  25.         f.write(out)
  26.         
  27. with open(data_path,"r",encoding="utf-8") as f1,open(out_path,"r",encoding="utf-8") as f2:
  28.     N1 = int(f1.readline().strip())
  29.     N2 = int(f2.readline().strip())
  30.     if(N1 != N2) :
  31.         print("Wrong Answer!")
  32.     else:
  33.         # 由于数据是不重复的且输出顺序并不固定，直接用集合判断
  34.         data1 = set([int(x.strip()) for x in f1.readlines()])
  35.         data2 = set([int(x.strip()) for x in f2.readlines()])
  36.         if data1 == data2:
  37.             print("Accept!")
  38.         else :
  39.             print("Wrong Answer!")
复制代码
下面为测试结果，没问题
2.png

黑高检验
我们还是来检测一下整颗红黑树的黑高是否正确，检测代码如下
  1. void checkBlackHeight()
  2. {
  3.     bool flag = true;
  4.     checkBlackHeightHelp(root, flag);
  5.     if (flag)
  6.         cout << "right!" << endl;
  7.     else
  8.         cout << "error!" << endl;
  9. }
  11. int checkBlackHeightHelp(Node *N, bool &flag)
  12. {
  13.     // NIL节点为黑色
  14.     if (N == NIL)
  15.         return 1;
  16.     int left = checkBlackHeightHelp(N->left, flag);
  17.     int right = checkBlackHeightHelp(N->right, flag);
  18.     if (left != right)
  19.         flag = false;
  20.     return left + (N->color == Color::BLACK ? 1 : 0);
  21. }
复制代码
右旋
  1. ios::sync_with_stdio(false);
  2. cin.tie(0);
  3. cout.tie(0);
复制代码
插入调整
  1. #include <iostream>
  2. using namespace std;
  3. #include <set>
  4. int main()
  5. {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(0);
  8.     cout.tie(0);
  10.     set<int> s;
  11.     int n;
  12.     cin >> n;
  13.     for (int i = 0; i < n; i++)
  14.     {
  15.         int x;
  16.         cin >> x;
  17.         s.insert(x);
  18.     }
  19.     int m;
  20.     cin >> m;
  21.     for (int i = 0; i < m; i++)
  22.     {
  23.         int x;
  24.         cin >> x;
  25.         s.erase(x);
  26.     }
  27.     cout << s.size() << endl;
  28.     for (auto x : s)
  29.         cout << x << endl;
  30. }
复制代码
插入节点
  1. enum Color
  2. {
  3.     RED,
  4.     BLACK
  5. };
复制代码
节点替换

在删除操作中，我们会经常将一个节点替换为另外一个节点。为了方便，我们封装一个函数用于节点替换
注意在这个替换函数中，只是更新了父节点与替换节点的关系，子节点并没有更新
  1. template <typename Key, typename Value>
  2. struct RBTreeNode
  3. {
  4.     // 按照key值进行插入删除等操作
  5.     Key key;
  6.     // value为存储的数据
  7.     Value value;
  8.     // 左节点指针
  9.     RBTreeNode<Key, Value> *left;
  10.     // 右节点指针
  11.     RBTreeNode<Key, Value> *right;
  12.     // 父节点指针
  13.     RBTreeNode<Key, Value> *parent;
  14.     // 节点颜色
  15.     Color color;
  16.     RBTreeNode(Color c, RBTreeNode<Key, Value> *l = nullptr, RBTreeNode<Key, Value> *r = nullptr, RBTreeNode<Key, Value> *p = nullptr)
  17.     {
  18.         color = c, left = l, right = r, parent = p;
  19.     }
  20.     RBTreeNode(Key k, Value v, Color c, RBTreeNode<Key, Value> *l = nullptr, RBTreeNode<Key, Value> *r = nullptr, RBTreeNode<Key, Value> *p = nullptr)
  21.     {
  22.         key = k, value = v, color = c, left = l, right = r, parent = p;
  23.     }
  24. };
复制代码
查询后继节点

在删除操作中，有些情况需要找到删除节点的后继节点，为了方便，依旧是封装一个函数来查询后继节点
后继节点为右子树中最小的一个节点
  1. typedef RBTreeNode<Key, Value> Node;
复制代码
删除调整
  1. // 创建一个空的红色节点
  2. Node *createEmptyRedNode(Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
  3. {
  4.     return new Node(Color::RED, l, r, p);
  5. }
复制代码
删除节点

注意在删除节点有两个非NIL的子节点的情况下，需要交换节点，这里为了方便是直接交换的键和值的，但是如果键和值对象比较大，那么这样效率就很慢，最好还是通过指针交换来达到节点交换的目的
  1. // 创建一个非空红色节点
  2. Node *createRedNode(Key key, Value value, Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
  3. {
  4.     return new Node(key, value, Color::RED, l, r, p);
  5. }
复制代码
查询

查询操作也是很基本也很常用的操作，红黑树的查询操作与其他的二叉搜索树基本一样：比节点小就去左子树查，比节点大就去右子树查，和节点一样大说明查询到了
  1. // 创建一个空的黑色节点
  2. Node *createEmptyBlackNode(Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
  3. {
  4.     return new Node(Color::BLACK, l, r, p);
  5. }
复制代码
注意这个版本的查询返回的value与红黑树中的并不是同一个，而是一个拷贝。如果想通过返回的value操作树内的value，可以返回引用类型
  1. // 创建一个非空黑色节点
  2. Node *createBlackNode(Key key, Value value, Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
  3. {
  4.     return new Node(key, value, Color::BLACK, l, r, p);
  5. }
复制代码
遍历数据

这里使用中序遍历整个红黑树，并统计红节点和黑节点个数
[code]void print(){    int red = 0, black = 0;    printOperation(root, red, black);    cout left->parent = p;        rightSon->parent = grandParent;        rightSon->left = p;        // 更新祖先节点        // 如果p为根节点        if (grandParent == NIL)            root = rightSon;        // 如果p为左节点        else if (grandParent->left == p)            grandParent->left = rightSon;        // 如果p为右节点        else            grandParent->right = rightSon;    }    // 右旋操作    void rightRotate(Node *p)    {        // 获取旋转节点的左儿子        Node *leftSon = p->left;        // 获取祖先节点        Node *grandParent = p->parent;        // 更新旋转节点        p->left = leftSon->right;        p->parent = leftSon;        // 更新左节点        // 如果左儿子的右节点不为NIL，则将左儿子的右节点的父节点设置为p        if (leftSon->right != NIL)            leftSon->right->parent = p;        leftSon->parent = grandParent;        leftSon->right = p;        // 更新祖先节点        // 如果p为根节点        if (grandParent == NIL)            root = leftSon;        // 如果p为左节点        else if (grandParent->left == p)            grandParent->left = leftSon;        // 如果p为右节点        else            grandParent->right = leftSon;    }    // 插入调整    void insertFixup(Node *N)    {        // 一直向上调整，直到父节点不是红色，或者父节点为根节点        // 注意这里的N节点一定为红色        while (N->parent->color == Color::RED && N->parent != root)        {            // 如果父节点为左子节点            if (N->parent == N->parent->parent->left)            {                // 获取叔叔节点                Node *U = N->parent->parent->right;                // 如果叔叔节点的颜色也为红色，则将父节点和叔叔节点都变为黑色，祖先节点变为红色，继续向上调整祖先节点                if (U->color == Color::RED)                {                    U->color = Color::BLACK;                    N->parent->color = Color::BLACK;                    N->parent->parent->color = Color::RED;                    // 继续调整祖先节点                    N = N->parent->parent;                }                else                {                    // 调整节点与父节点不同向，需旋转为同向                    if (N == N->parent->right)                    {                        // 旋转N的父节点                        N = N->parent;                        // 旋转父节点                        leftRotate(N);                    }                    // 调整节点与父节点同向                    // 注意要先变色再旋转，旋转之后会改变父子关系，到时候很混乱                    // 父节点设置为黑色                    N->parent->color = Color::BLACK;                    // 祖先节点设置为红色                    N->parent->parent->color = Color::RED;                    // 旋转祖先节点                    rightRotate(N->parent->parent);                }            }            // 如果父节点为右子节点            else            {                // 获取叔叔节点                Node *U = N->parent->parent->left;                // 如果叔叔节点的颜色也为红色，则将父节点和叔叔节点都变为黑色，祖先节点变为红色，继续向上调整祖先节点                if (U->color == Color::RED)                {                    U->color = Color::BLACK;                    N->parent->color = Color::BLACK;                    N->parent->parent->color = Color::RED;                    // 继续调整祖先节点                    N = N->parent->parent;                }                else                {                    // 调整节点与父节点不同向，需旋转为同向                    if (N == N->parent->left)                    {                        // 旋转N的父节点                        N = N->parent;                        // 旋转父节点                        rightRotate(N);                    }                    // 调整节点与父节点同向                    // 注意要先变色再旋转，旋转之后会改变父子关系，到时候很混乱                    // 父节点设置为红色                    N->parent->color = Color::BLACK;                    // 祖先节点设置为红色                    N->parent->parent->color = Color::RED;                    // 旋转祖先节点                    leftRotate(N->parent->parent);                }            }        }        // 根节点可以无责任变成黑色        root->color = Color::BLACK;    }    // 用v替换u，只更换父节点关系    void replace(Node *u, Node *v)    {        // 如果u为root        if (u->parent == NIL)            root = v;        // u为左子节点        else if (u->parent->left == u)            u->parent->left = v;        // u为右子节点        else            u->parent->right = v;        v->parent = u->parent;    }    // 获取最小节点    Node *getMinNode(Node *p)    {        while (p->left != NIL)            p = p->left;        return p;    }    // 查询全部元素辅助函数    void queryAllHelp(Node *N, vector &v)    {        if (N == NIL)            return;        queryAllHelp(N->left, v);        v.push_back(N->value);        queryAllHelp(N->right, v);    }public:    RBTree(/* args */)    {        NIL = createEmptyBlackNode();        NIL->left = NIL, NIL->right = NIL, NIL->parent = NIL;        root = NIL;        size = 0;    }    // 创建一个非空黑色节点
Node *createBlackNode(Key key, Value value, Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
{
    return new Node(key, value, Color::BLACK, l, r, p);
} query(Key key)    {        Value v;        if (root == NIL)            return {false, v};        Node *temp = root;        while (temp != NIL)        {            if (key < temp->key)                temp = temp->left;            else if (key > temp->key)                temp = temp->right;            else                return {true, temp->value};        }        return {false, v};    }    void insert(Key key, Value value)    {        Node *N = createRedNode(key, value, NIL, NIL, NIL);        // 查询节点的父节点        Node *p = NIL;        // 迭代查找临时节点        Node *temp = root;        // 树为空，直接插入        if (root == NIL)        {            N->color = BLACK;            root = N;            size++;            return;        }        while (temp != NIL)        {            p = temp;            // 往左查找            if (N->key < temp->key)                temp = temp->left;            // 往右查找            else if (N->key > temp->key)                temp = temp->right;            // key值已经存在，则替换数据            else            {                temp->value = value;                return;            }        }        size++;        N->parent = p;        // 如果key值比父节点小，则作为左子节点        if (N->key < p->key)            p->left = N;        // 如果key值比父节点大，则作为右子节点        else            p->right = N;        insertFixup(N);    }    int getSize()    {        return size;    }    vector queryAll()    {        vector temp;        queryAllHelp(root, temp);        return temp;    }    ~RBTree()    {    }};int main(){    RBTree tr;    int n;    cin >> n;    for (int i = 1; i > l;        for (int j = 0; j < l; j++)        {            string s;            cin >> s;            // 创建一个非空黑色节点
Node *createBlackNode(Key key, Value value, Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
{
    return new Node(key, value, Color::BLACK, l, r, p);
} q = tr.query(s);            if (q.first == false)            {                RBTree temp;                temp.insert(i, i);                tr.insert(s, temp);            }            else                q.second.insert(i, i);        }    }    int m;    cin >> m;    for (int i = 0; i < m; i++)    {        string s;        cin >> s;        // 创建一个非空黑色节点
Node *createBlackNode(Key key, Value value, Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
{
    return new Node(key, value, Color::BLACK, l, r, p);
} q = tr.query(s);        if (q.first == false)            cout left;        p->parent = rightSon;        // 更新右节点        // 如果右儿子的左节点不为NIL，则将右儿子的左节点的父节点设置为p        if (rightSon->left != NIL)            rightSon->left->parent = p;        rightSon->parent = grandParent;        rightSon->left = p;        // 更新祖先节点        // 如果p为根节点        if (grandParent == NIL)            root = rightSon;        // 如果p为左节点        else if (grandParent->left == p)            grandParent->left = rightSon;        // 如果p为右节点        else            grandParent->right = rightSon;    }    // 右旋操作    void rightRotate(Node *p)    {        // 获取旋转节点的左儿子        Node *leftSon = p->left;        // 获取祖先节点        Node *grandParent = p->parent;        // 更新旋转节点        p->left = leftSon->right;        p->parent = leftSon;        // 更新左节点        // 如果左儿子的右节点不为NIL，则将左儿子的右节点的父节点设置为p        if (leftSon->right != NIL)            leftSon->right->parent = p;        leftSon->parent = grandParent;        leftSon->right = p;        // 更新祖先节点        // 如果p为根节点        if (grandParent == NIL)            root = leftSon;        // 如果p为左节点        else if (grandParent->left == p)            grandParent->left = leftSon;        // 如果p为右节点        else            grandParent->right = leftSon;    }    // 插入调整    void insertFixup(Node *N)    {        // 一直向上调整，直到父节点不是红色，或者父节点为根节点        // 注意这里的N节点一定为红色        while (N->parent->color == Color::RED && N->parent != root)        {            // 如果父节点为左子节点            if (N->parent == N->parent->parent->left)            {                // 获取叔叔节点                Node *U = N->parent->parent->right;                // 如果叔叔节点的颜色也为红色，则将父节点和叔叔节点都变为黑色，祖先节点变为红色，继续向上调整祖先节点                if (U->color == Color::RED)                {                    U->color = Color::BLACK;                    N->parent->color = Color::BLACK;                    N->parent->parent->color = Color::RED;                    // 继续调整祖先节点                    N = N->parent->parent;                }                else                {                    // 调整节点与父节点不同向，需旋转为同向                    if (N == N->parent->right)                    {                        // 旋转N的父节点                        N = N->parent;                        // 旋转父节点                        leftRotate(N);                    }                    // 调整节点与父节点同向                    // 注意要先变色再旋转，旋转之后会改变父子关系，到时候很混乱                    // 父节点设置为黑色                    N->parent->color = Color::BLACK;                    // 祖先节点设置为红色                    N->parent->parent->color = Color::RED;                    // 旋转祖先节点                    rightRotate(N->parent->parent);                }            }            // 如果父节点为右子节点            else            {                // 获取叔叔节点                Node *U = N->parent->parent->left;                // 如果叔叔节点的颜色也为红色，则将父节点和叔叔节点都变为黑色，祖先节点变为红色，继续向上调整祖先节点                if (U->color == Color::RED)                {                    U->color = Color::BLACK;                    N->parent->color = Color::BLACK;                    N->parent->parent->color = Color::RED;                    // 继续调整祖先节点                    N = N->parent->parent;                }                else                {                    // 调整节点与父节点不同向，需旋转为同向                    if (N == N->parent->left)                    {                        // 旋转N的父节点                        N = N->parent;                        // 旋转父节点                        rightRotate(N);                    }                    // 调整节点与父节点同向                    // 注意要先变色再旋转，旋转之后会改变父子关系，到时候很混乱                    // 父节点设置为红色                    N->parent->color = Color::BLACK;                    // 祖先节点设置为红色                    N->parent->parent->color = Color::RED;                    // 旋转祖先节点                    leftRotate(N->parent->parent);                }            }        }        // 根节点可以无责任变成黑色        root->color = Color::BLACK;    }    // 删除调整    void removeFixup(Node *C)    {        while (C != root && C->color == BLACK)        {            // 如果C为左子节点            if (C == C->parent->left)            {                // 获取兄弟节点                Node *S = C->parent->right;                // 如果兄弟节点为红色，我们需要通过旋转将兄弟节点变为黑色                if (S->color == Color::RED)                {                    // 先变色再旋转                    S->color = Color::BLACK;                    C->parent->color = Color::RED;                    leftRotate(C->parent);                    // 获取新的兄弟节点                    S = C->parent->right;                }                // 兄弟节点的左儿子和右儿子都为黑色                if (S->left->color == Color::BLACK && S->right->color == Color::BLACK)                {                    // 父节点为红色                    if (C->parent->color == Color::RED)                    {                        C->parent->color = Color::BLACK;                        S->color = Color::RED;                        // 已经调整完毕，不需要再进行调整就将C设置为根节点                        C = root;                    }                    // 父节点为黑色                    else                    {                        S->color = Color::RED;                        // 父节点成为双黑节点，继续调整父节点                        C = C->parent;                    }                }                else                {                    // 近侄节点为红色，远侄子节点为黑色，需要调整为远侄节点为红色                    if (S->right->color == Color::BLACK)                    {                        // 先变色再旋转                        S->color = Color::RED;                        S->left->color = Color::BLACK;                        rightRotate(S);                        // 由于旋转改变了父子关系，所以重新获取一下兄弟节点                        S = C->parent->right;                    }                    // 调整后远侄节点为红色                    S->color = C->parent->color;                    C->parent->color = Color::BLACK;                    S->right->color = Color::BLACK;                    leftRotate(C->parent);                    // 已经调整完毕，不需要再进行调整就将C设置为根节点                    C = root;                }            }            // 如果C为右子节点            else            {                // 获取兄弟节点                Node *S = C->parent->left;                // 如果兄弟节点为红色，我们需要通过旋转将兄弟节点变为黑色                if (S->color == Color::RED)                {                    // 先变色再旋转                    S->color = Color::BLACK;                    C->parent->color = Color::RED;                    rightRotate(C->parent);                    // 获取新的兄弟节点                    S = C->parent->left;                }                // 兄弟节点的左儿子和右儿子都为黑色                if (S->left->color == Color::BLACK && S->right->color == Color::BLACK)                {                    // 父节点为红色                    if (C->parent->color == Color::RED)                    {                        C->parent->color = Color::BLACK;                        S->color = Color::RED;                        // 已经调整完毕，不需要再进行调整就将C设置为根节点                        C = root;                    }                    // 父节点为黑色                    else                    {                        S->color = Color::RED;                        // 父节点成为双黑节点，继续调整父节点                        C = C->parent;                    }                }                else                {                    // 近侄节点为红色，远侄子节点为黑色，需要调整为远侄节点为红色                    if (S->left->color == Color::BLACK)                    {                        // 先变色再旋转                        S->color = Color::RED;                        S->right->color = Color::BLACK;                        leftRotate(S);                        // 由于旋转改变了父子关系，所以重新获取一下兄弟节点                        S = C->parent->left;                    }                    // 调整后远侄节点为红色                    S->color = C->parent->color;                    C->parent->color = Color::BLACK;                    S->left->color = Color::BLACK;                    rightRotate(C->parent);                    // 已经调整完毕，不需要再进行调整就将C设置为根节点                    C = root;                }            }        }        // 根节点可以无责任变成黑色        root->color = Color::BLACK;    }    // 用v替换u，只更换父节点关系    void replace(Node *u, Node *v)    {        // 如果u为root        if (u->parent == NIL)            root = v;        // u为左子节点        else if (u->parent->left == u)            u->parent->left = v;        // u为右子节点        else            u->parent->right = v;        v->parent = u->parent;    }    // 获取最小节点    Node *getMinNode(Node *p)    {        while (p->left != NIL)            p = p->left;        return p;    }    // 打印辅助函数    void printHelp(Node *p, int &red, int &black)    {        if (p == NIL)            return;        cout left, v);        v.push_back(N->value);        queryAllHelp(N->right, v);    }    int checkBlackHeightHelp(Node *N, bool &flag)    {        if (N == NIL)            return 1;        int left = checkBlackHeightHelp(N->left, flag);        int right = checkBlackHeightHelp(N->right, flag);        if (left != right)            flag = false;        return left + (N->color == Color::BLACK ? 1 : 0);    }public:    RBTree(/* args */)    {        NIL = createEmptyBlackNode();        NIL->left = NIL, NIL->right = NIL, NIL->parent = NIL;        root = NIL;        size = 0;    }    // 创建一个非空黑色节点
Node *createBlackNode(Key key, Value value, Node *l = nullptr, Node *r = nullptr, Node *p = nullptr)
{
    return new Node(key, value, Color::BLACK, l, r, p);
} query(Key key)    {        if (root == NIL)            return {false, Value()};        Node *temp = root;        while (temp != NIL)        {            if (key < temp->key)                temp = temp->left;            else if (key > temp->key)                temp = temp->right;            else                return {true, temp->value};        }        return {false, Value()};    }    void insert(Key key, Value value)    {        Node *N = createRedNode(key, value, NIL, NIL, NIL);        // 查询节点的父节点        Node *p = NIL;        // 迭代查找临时节点        Node *temp = root;        // 树为空，直接插入        if (root == NIL)        {            N->color = BLACK;            root = N;            size++;            return;        }        while (temp != NIL)        {            p = temp;            // 往左查找            if (N->key < temp->key)                temp = temp->left;            // 往右查找            else if (N->key > temp->key)                temp = temp->right;            // key值已经存在，则替换数据            else            {                temp->value = value;                return;            }        }        size++;        N->parent = p;        // 如果key值比父节点小，则作为左子节点        if (N->key < p->key)            p->left = N;        // 如果key值比父节点大，则作为右子节点        else            p->right = N;        insertFixup(N);    }    void remove(Key key)    {        Node *N = root;        while (N != NIL)        {            if (N->key == key)                break;            if (key < N->key)                N = N->left;            else                N = N->right;        }        // 树中没有删除的key        if (N == NIL)            return;        // 删除节点为树中唯一节点        // Case 1        if (size == 1)        {            if (root != NIL)                destroyNode(root);            root = NIL;            size--;            return;        }        // Case 4        // 删除节点有两个非NIL的子节点        if (N->left != NIL && N->right != NIL)        {            // 获得后继节点            Node *minNode = getMinNode(N->right);            // 我们这里直接交换键值，方便，但如果键值都是比较大的对象就很慢了，最好还是交换指针            swap(minNode->key, N->key);            swap(minNode->value, N->value);            // 删除节点转换为后继节点，转移到case 2或 case 3            N = minNode;        }        // Case 3        if (N->left == NIL && N->right != NIL)        {            Node *rightSon = N->right;            rightSon->color = N->color;            // 用右子节点替换删除节点            replace(N, rightSon);            // 删除节点            destroyNode(N);        }        // Case 3        else if (N->left != NIL && N->right == NIL)        {            Node *leftSon = N->left;            leftSon->color = N->color;            // 用左子节点替换删除节点            replace(N, leftSon);            // 删除节点            destroyNode(N);        }        // Case 2        else        {            // 此情况为删除节点的两个儿子都为NIL节点            // 删除节点为红色，直接删除即可            if (N->color == Color::RED)            {                Node *parent = N->parent;                if (parent->left == N)                    parent->left = NIL;                else                    parent->right = NIL;                destroyNode(N);            }            // 删除节点为黑色，出现双黑节点，需要向上调整            else            {                removeFixup(N);                // 调整后删除该节点                Node *parent = N->parent;                if (parent->left == N)                    parent->left = NIL;                else                    parent->right = NIL;                destroyNode(N);            }        }        size--;    }    int getSize()    {        return size;    }    void print()    {        int red = 0, black = 0;        printHelp(root, red, black);        cout

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
碛物
2025-5-31 23:58:54

0

粉丝关注

23

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫