红黑树 (Red-Black Tree) — 5W1H故事与需求定义063金发姑娘的平衡揭秘红黑树Who谁设计者Rudolf Bayer1972年提出对称二叉B树由 Leonidas Guibas 和 Robert Sedgewick 于1978年命名为红黑树并由 Thomas H. Cormen 等人在《算法导论》中系统化。引用者Donald E. Knuth 在 TAOCP 第3卷第6.2.3节中深入分析了自平衡二叉搜索树的理论基础。使用者操作系统Linux内核CFS调度器、epoll事件管理、C STLstd::map/std::set、JavaTreeMap/TreeSet凡需要动态有序集合且要求最坏情况对数时间复杂度的场景均适用。What什么红黑树是一种自平衡二叉搜索树每个节点标记为红色或黑色通过旋转左旋/右旋和变色保持以下不变量根黑根节点始终为黑色。红节点子黑红色节点的子节点必须是黑色不存在连续红节点。黑高一致从任意节点到所有后代叶节点NIL哨兵的路径上黑色节点数目相同。上述约束保证树的高度h ≤ 2·log₂(n1)从而所有基本操作搜索、插入、删除均在O(log n)时间内完成。When何时需要动态维护有序集合且同时要求插入、删除、搜索的**最坏情况O(log n)**时间保证时。需要在高并发环境操作系统内核、数据库索引中使用确定性性能的数据结构时。对比AVL树红黑树插入/删除旋转次数更少均摊更快适合写多读少场景。Where何处操作系统Linux内核用红黑树管理进程调度CFS、内存映射区域mm_struct、文件系统节点。标准库C STLstd::map、std::set、std::multimapJavaTreeMap、TreeSet。数据库部分数据库引擎的内存索引结构。网络epoll事件管理使用红黑树追踪文件描述符。Why为何BST退化问题普通BST在顺序插入时退化为链表操作退化为O(n)。AVL过于严格AVL树要求左右子树高度差不超过1插入/删除需更多旋转。红黑树平衡了代价以宽松平衡换取更少的旋转次数在频繁修改的场景下性能更优。最坏情况保证不同于哈希表红黑树在任意输入分布下均提供O(log n)保证无哈希碰撞退化风险。How如何核心操作操作时间复杂度说明搜索O(log n)标准BST搜索无需修复插入O(log n)BST插入 → 着红色 →RB-INSERT-FIXUP删除O(log n)BST删除 →RB-DELETE-FIXUP插入修复三情形以父节点是祖父左孩子为例情形叔节点颜色处理方式情形1红父、叔变黑祖父变红z上移至祖父情形2黑z是右孩子左旋父节点转为情形3情形3黑z是左孩子父变黑祖父变红右旋祖父哨兵NIL节点使用单一哨兵节点t-nil代替所有NULL叶节点颜色为黑色简化边界判断避免大量空指针检查。需求定义功能需求ID需求描述F1rb_insert(t, key)将整数 key 插入红黑树忽略重复键F2rb_search(t, key)搜索 key找到返回节点指针否则返回 NULLF3rb_delete(t, key)删除 key 对应节点若存在F4rb_inorder(t, size)中序遍历返回有序整数数组调用者释放F5rb_height(t)返回树的高度F6rb_create()/rb_destroy(t)创建和释放整棵树性质约束ID约束描述P1根节点始终为黑色P2无两个连续的红色节点P3任意路径上黑色节点数相同黑高一致P4树高度h ≤ 2·log₂(n1)非功能需求所有操作时间复杂度为 O(log n)最坏情况内存无泄漏rb_destroy释放所有节点和哨兵使用 C99 标准通过gcc -stdc99 -Wall无警告编译验收标准测试编号测试描述预期结果TC1插入键 1-10搜索所有 10 个键全部返回非 NULL 节点TC2搜索不存在的键0, 11, 100全部返回 NULLTC3以乱序插入 1-10执行中序遍历得到有序序列1,2,3,...,10TC4每次插入后检查根节点颜色根始终为黑色color BLACKTC5插入 10 个键后测量树高度h ≤ 2·log₂(11) ≈ 6.92即h ≤ 6TC6删除偶数键2,4,6,8,10后搜索奇数键可找到偶数键返回 NULL