红黑树
红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 ("RED" or "BLACK"),用于确保树在插入和删除时保持平衡。
性质
一棵合法的红黑树必须遵循以下四条性质:
- 节点为红色或黑色
- NIL 节点(空叶子节点)为黑色
- 红色节点的子节点为黑色
- 从根节点到 NIL 节点的每条路径上的黑色节点数量相同
下图为一棵合法的红黑树:
Note
部分资料中还加入了第五条性质,即根节点必须为黑色,这条性质要求完成插入操作后若根节点为红色则将其染黑,但由于将根节点染黑的操作也可以延迟至删除操作时进行,因此,该条性质并非必须满足(本文给出的代码实现中满足该性质)。为严谨起见,这里同时引用 维基百科原文 进行说明:
Some authors, e.g. Cormen & al.,2claim "the root is black" as fifth requirement; but not Mehlhorn & Sanders3or Sedgewick & Wayne.4Since the root can always be changed from red to black, this rule has little effect on analysis. This article also omits it, because it slightly disturbs the recursive algorithms and proofs.
红黑树类的定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|
Note
在红黑树节点的存储中,用数组来存储子节点指针可以提高代码复用率。
操作
Note
红黑树的插入/删除有多种实现方式,本文采用《算法导论》的实现方式,将插入后的平衡维护分为 3 种情况,删除后的平衡维护分为 4 种情况。
红黑树的遍历、查找最小/最大值、搜索元素、求元素的排名、根据排名反查元素、查找前驱/后继等操作和 二叉搜索树 一致,此处不再赘述。
另外,在下文插入/删除平衡维护的代码注释中,我们作如下约定:
- 用
p
表示节点p
为黑色; - 用
[p]
表示节点p
为红色; - 用
{p}
表示节点p
为红色或黑色; - 用
|p|
表示节点p
为 NIL 节点或颜色为黑色。
旋转
旋转操作是多数平衡树能够维持平衡的关键,它能在不改变一棵合法 BST 中序遍历结果的情况下改变局部节点的深度。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
插入
红黑树的插入操作与普通的 BST 类似,对于红黑树来说,新插入的节点初始为红色,完成插入后需根据插入节点及相关节点的状态进行修正以满足上文提到的四条性质。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
|
插入后的平衡维护
Note
为加深理解,请读者自行验证平衡维护后是否满足性质 4。
由于插入的节点若不为根节点则必为红色,所以插入后可能违反性质 3,需要维护平衡性。
令插入的节点为
我们从插入的位置开始向上递归维护,若
1 2 3 4 5 |
|
Insert case 1
实现
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Insert case 2
此时我们需要旋转
实现
1 2 3 4 5 6 7 8 |
|
Insert case 3
此时我们需要旋转
实现
1 2 3 4 5 6 7 8 |
|
删除
红黑树的删除操作与普通的 BST 相比要多一些步骤。具体而言:
- 若待删除的节点
有两个子节点,则交换 和左子树中最大节点 的数据,并将 设为 。此时 不可能有两个子节点。 - 若待删除的节点
有一个子节点 。由性质 4 可知 必为红色,再由性质 3 可知 必为黑色。所以只需将 在父节点 中对应的指针替换为 的地址,以及将 的父节点指针替换为 的地址,之后再将 染黑即可。 - 若待删除的节点
没有子节点。若 是根节点或 是红色节点,则直接删除即可,否则直接删除会违反性质 4,需要维护平衡性。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
|
删除后的平衡维护
Note
为加深理解,请读者自行验证平衡维护后是否满足性质 4。
由上文讨论可知
删除的维护也是从
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Delete case 1
此时我们旋转
实现
1 2 3 4 5 6 7 8 9 10 11 |
|
Delete case 2
此时只需将
需要注意的是,若
实现
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Delete case 3
此时需要旋转
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Delete case 4
此时需要旋转
实现
1 2 3 4 5 6 7 8 |
|
参考代码
下面的代码是用红黑树实现的 set:
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 |
|
例题:Luogu P3369【模板】普通平衡树 与 Luogu P6136【模板】普通平衡树(数据加强版)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 |
|
实际工程项目中的使用
由于红黑树是目前主流工业界综合效率最高的内存型平衡树,其在实际的工程项目中有着广泛的使用,这里列举几个实际的使用案例并给出相应的源码链接,以便读者进行对比学习。
Linux
源码:
Linux 中的红黑树所有操作均使用循环迭代进行实现,保证效率的同时又增加了大量的注释来保证代码可读性,十分建议读者阅读学习。Linux 内核中的红黑树使用非常广泛,这里仅列举几个经典案例。
-
Linux 的稳定内核版本在 2.6.24 之后,使用了新的调度程序 CFS,所有非实时可运行进程都以虚拟运行时间为键值用一棵红黑树进行维护,以完成更公平高效地调度所有任务。CFS 弃用 active/expired 数组和动态计算优先级,不再跟踪任务的睡眠时间和区别是否交互任务,而是在调度中采用基于时间计算键值的红黑树来选取下一个任务,根据所有任务占用 CPU 时间的状态来确定调度任务优先级。
-
epoll 全称 event poll,是 Linux 内核实现 IO 多路复用 (IO multiplexing) 的一个实现,是原先 poll/select 的改进版。Linux 中 epoll 的实现选择使用红黑树来储存文件描述符。
Nginx
源码:
nginx 中的用户态定时器是通过红黑树实现的。在 nginx 中,所有 timer 节点都由一棵红黑树进行维护,在 worker 进程的每一次循环中都会调用 ngx_process_events_and_timers
函数,在该函数中就会调用处理定时器的函数 ngx_event_expire_timers
,每次该函数都不断的从红黑树中取出时间值最小的,查看他们是否已经超时,然后执行他们的函数,直到取出的节点的时间没有超时为止。
关于 nginx 中红黑树的源码分析公开资源很多,读者可以自行查找学习。
C++
源码:
GNU libstdc++
另外,
libstdc++
在<ext/rb_tree>
中提供了__gnu_cxx::rb_tree
,其继承了std::_Rb_tree
,可以认为是供外部使用的类型别名。需要注意的是,该头文件 不是 C++ 标准的一部分,所以非必要不推荐使用。libstdc++
的pb_ds
中也提供了红黑树。LLVM libcxx
Microsoft STL
大多数 STL 中的 std::set
和 std::map
的内部数据结构就是红黑树(例如上面提到的这些)。不过值得注意的是,C++ 标准并未规定必须以红黑树实现 std::set
和 std::map
,所以不应该在工程项目中直接使用 std::set
和 std::map
的内部数据结构。
OpenJDK
源码:
JDK 中的 TreeMap
和 TreeSet
都是使用红黑树作为底层数据结构的。同时在 JDK 1.8 之后 HashMap
内部哈希表中每个表项的链表长度超过 8 时也会自动转变为红黑树以提升查找效率。
参考资料
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022).Introduction to algorithms. MIT press.
- Red-Black Tree - Wikipedia
- Red-Black Tree Visualization
L. J. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees,"19th Annual Symposium on Foundations of Computer Science (sfcs 1978), Ann Arbor, MI, USA, 1978, pp. 8-21, doi:10.1109/SFCS.1978.3. ↩
https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Cormen2009-18 ↩
https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Mehlhorn2008-17 ↩
https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Algs4-16: 432–447 ↩
本页面最近更新:2025/5/21 14:42:25,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:0x03A6, abc1763613206, auuuu4, CCXXXI, Conless, Enter-tainer, fanenr, happyZYM, hsfzLZH1, iamtwz, LeverImmy, leverimmy, Lhcfl, Marcythm, RIvance, Tiphereth-A, trudbot, Xeniume, Xeonacid, yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用