红黑树是一种自平衡二叉搜索树,其中每个节点都有一个额外属性,通常称为颜色,取值为红色或黑色。颜色排列所遵循的规则使树在插入和删除键时保持近似平衡。对于包含 个元素的树,查找、插入和删除操作在最坏情况下的时间复杂度均为 。
这种结构兼具按序访问的能力和可预测的更新开销。与普通二叉搜索树不同,即使插入顺序不利,红黑树也不会退化为线性链。与哈希表不同,它直接支持基于键顺序的操作,包括前驱和后继查询、有序遍历以及范围查找。这些性质使其成为实现有序字典、集合及各种增强索引的重要数据结构。
红黑树于20世纪70年代从平衡多路搜索树发展而来。其二叉表示形式、较少的平衡维护信息,以及常规更新过程中有界的旋转次数,使其在程序库和系统软件中得到广泛应用。要理解红黑树的运行机制,最好从颜色不变式、局部结构变换,以及这些颜色所编码的多路树之间的关系入手。
结构不变量与高度上界
红黑树首先遵循普通二叉搜索树的有序性规则:节点左子树中的键排在该节点的键之前,右子树中的键排在其后。对于键唯一的字典,比较关系是严格的。允许存在等价键的容器,则需要额外约定这些条目的表示方式或排列顺序。平衡规则并不决定如何处理重复键。
通常的定义还规定了以下五条颜色性质:
- 每个节点不是红色就是黑色。
- 根节点为黑色。
- 每个缺失的子节点在概念上都用一个 NIL 叶节点表示,且为黑色。
- 红色节点不能有红色子节点。
- 从任一节点到其后代 NIL 叶节点的每条路径,都包含相同数量的黑色节点。
NIL 叶节点是概念上的外部节点,而不是实际存储的元素。实现时可以用空指针、共享的哨兵对象或其他约定来表示。将它们统一视为黑色,既能简化证明,也能简化更新操作中的各种情形。有些等价定义省略了根节点必须为黑色的性质,因为总可以将红色根节点重新着为黑色,而不破坏其他性质。
第五条性质定义了节点的黑高。本文采用一种常见约定:将 定义为从 向下的一条路径上黑色节点的数量,不计入 本身,但计入路径末端的 NIL 叶节点。NIL 节点的黑高为零。黑高相等并不意味着普通高度也相等:黑色节点之间可以出现红色节点,使某些路径变长,却不增加路径上黑色节点的数量。
以下两点可以确立对数级的高度上界。首先,以 为根的子树至少包含
个内部节点。这可以通过归纳法证明:每个子节点的黑高至少为 ,因此子树的最小规模至少与相应黑高的满二叉树规模增长得一样快。其次,由于不允许连续出现红色节点,在任意一条从根节点到 NIL 节点的路径上,根节点以下至少有一半节点为黑色。若 为这类路径上的最大边数,则有
例如,根据这一上界,存储一百万个元素时,从根节点到 NIL 节点的路径高度小于 40 条边。实际高度取决于更新操作的顺序和所采用的平衡算法变体。这一保证针对的是最坏情况下可能出现的树形,而不是以输入随机为前提。
因此,红黑树的平衡是指高度受到约束,而不一定意味着左右子树的规模相等。即使某个节点一侧的后代数量远多于另一侧,所有颜色不变量仍然可能成立。这一区别既解释了红黑树为何具有可靠的渐近性能,也解释了为什么与平衡要求更严格的搜索树相比,红黑树对高度的限制通常更宽松。
有序操作与旋转
在红黑树中查找的过程与在非平衡二叉搜索树中完全相同。在每个节点处,将待查找的键与该节点存储的键进行比较;若匹配则停止,否则进入相应的子树继续查找。颜色不影响比较的顺序,其作用是确保查找过程中访问的节点数保持在对数级。
这种结构直接支持多种有序操作。最小值位于沿最左侧路径向下走到的末端,最大值则位于最右侧路径的末端。如果一个节点有右子树,其后继就是右子树中的最小节点;否则,从该节点向上回溯,第一个从其左孩子回到的祖先节点就是后继。查找前驱的过程与此对称。父指针使向上遍历十分直接;没有父指针时,实现中可以用栈保存查找路径。
下界查找用于寻找第一个不小于查询键的键。每当当前节点可能是答案时,就记录该节点,并继续向左查找更靠前的候选节点;否则,继续向右查找。从下界开始,反复访问后继,可以在 时间内列出连续的 个条目。完整的中序遍历耗时 ,因为每条边只会被遍历常数次。
维持平衡依赖于树旋转,这是一种只涉及常数个节点、且保持中序次序不变的局部结构调整。对节点 进行左旋时,其右孩子 移到 原来的位置。节点 成为 的左孩子,而 原来的左子树成为 的右子树。其逆操作是右旋。对于左旋,各部分之间的大小关系为
其中,、 和 表示参与旋转的三棵子树。旋转后,这些大小关系保持不变。
无论子树有多大,一次旋转都只会修改固定数量的孩子指针和父指针。如果被旋转的节点原本是根节点,还必须更新树的根指针。颜色并不是旋转操作本身的一部分:平衡算法会将旋转与特定的重新着色操作配合使用。如果相应的颜色修改有误,即使旋转后的结构正确,红黑树仍可能不满足其约束条件。
分析这些操作的时间复杂度时,通常假定键的比较耗时为常数。对于长字符串、复合键或用户定义的比较器,比较的开销可能大得多。如果一次比较的成本为 ,那么一次查找中比较部分的成本就是 。缓存未命中和沿指针遍历还会带来额外开销,而抽象的比较次数并未反映这些成本。
插入与红红冲突的修复
传统的自底向上插入算法首先执行普通的二叉搜索树插入操作。一个新的内部节点取代某个 NIL 位置,获得两个黑色 NIL 子节点,并在初始时被设为红色。将其设为红色,可以保持每条受影响路径上的黑色节点数不变:新的内部节点不会增加黑色节点数,而末端的 NIL 仍计为一个黑色节点。
此时,唯一可能出现的颜色违规情况是根节点为红色,或某个红色节点的父节点也为红色。如果新节点就是根节点,将其设为黑色即可完成操作。如果它的父节点为黑色,则无须修复。否则,算法会检查新节点、其父节点、祖父节点以及叔节点,也就是父节点的兄弟节点。在传统的修复循环中,红色父节点必然有祖父节点,因为插入前根节点为黑色。
如果叔节点为红色,就将父节点和叔节点重新着为黑色,并将祖父节点重新着为红色。经过祖父节点的各条路径,其黑色节点数保持不变:原来由祖父节点贡献的一个黑色节点,改由其某个子节点贡献。局部的红红冲突由此消除,但祖父节点与其父节点之间可能出现新的冲突。因此,修复过程以祖父节点为当前节点,继续向上进行。反复重新着色可能一直传递到根节点,而根节点会在操作结束时被设为黑色。
如果叔节点为黑色,包括叔节点为 NIL 的情况,则通过旋转在局部消除冲突。假设父节点是祖父节点的左子节点。如果当前节点是父节点的右子节点,这三个节点就形成内侧构型,也称三角形构型。对父节点进行一次左旋,可将其转换为外侧构型,也称直线构型。随后,将所得构型中的父节点设为黑色、祖父节点设为红色,并对祖父节点进行一次右旋。如果父节点是右子节点,则所有方向均反转。
一个简单的例子可以说明旋转与重新着色的区别。依次插入 、 和 ,首先得到黑色根节点 ,然后得到它的红色右子节点 。加入红色节点 后,就形成了一条红红相连的链,其叔节点为黑色 NIL。对 进行一次左旋,再配合重新着色,就会得到黑色根节点 ,以及两个红色子节点 和 。如果接着插入 ,其父节点 和叔节点 都为红色,因此在这一层通过重新着色来修复,而不是立即旋转。
这种传统的插入算法最多执行两次旋转。重新着色可能沿着 个祖先节点向上传递,但一旦执行叔节点为黑色时的旋转处理,修复就会结束。计入最初的查找过程,插入操作的最坏情况时间复杂度为 。最多两次旋转这一上界仅适用于这种特定的自底向上算法;其他红黑树算法可能以不同方式组织变换,旋转次数也可能不同。
删除与黑色亏缺的各种情形
删除操作更为复杂,因为移除黑色节点可能破坏各条路径黑高相等的性质。第一阶段是普通的二叉搜索树删除操作。对于最多只有一个非 NIL 子节点的节点,可以直接将其摘除。对于有两个非 NIL 子节点的节点,可以用其中序后继或中序前驱提供替换位置或替换值,从而将结构上的移除操作归结为移除一个最多只有一个非 NIL 子节点的节点。
在这一过程中,必须仔细区分两种颜色:移入被删除节点位置的节点所赋予的颜色,以及从原位置移除的节点原本的颜色。后者决定是否产生了黑高亏缺。如果只复制后继节点的键和值,目标节点在结构上的身份就保持不变;如果改为移植后继节点,则会改变对象身份,并需要更新更多指针。这两种策略都能正确实现删除,但对引用和迭代器的影响不同。
移除红色节点不会改变黑高。如果被移除的黑色节点有一个红色子节点接替它,将该子节点染黑就能补回失去的黑色贡献。困难的情况是:移除一个黑色节点,而接替它的是黑色节点或 NIL。算法常将这个替代节点描述为带有一重额外黑色,或处于双黑状态。这只是用来记录某一侧缺少一重黑色贡献的方式,并不一定意味着实际存储了第三种颜色。
设 带有这一亏缺,并假定 是其父节点的左子节点。那么,它的兄弟节点 就是右子节点。标准修复过程主要分为以下四种情形;当 是右子节点时,则采用相应的镜像操作:
- 兄弟节点为红色: 将兄弟节点染黑,将父节点染红,然后以父节点为轴左旋。这样就将当前情形转换为兄弟节点为黑色的情形。
- 兄弟节点为黑色,且其两个子节点均为黑色: 将兄弟节点染红,并把亏缺转移到父节点。如果父节点原本为红色,将其染黑即可消除亏缺;否则,可能需要继续向上修复。
- 兄弟节点为黑色,近侧子节点为红色,远侧子节点为黑色: 这里的近侧子节点是 的左子节点。通过重新着色并以兄弟节点为轴右旋,将其转换为最后一种情形。
- 兄弟节点为黑色,远侧子节点为红色: 将兄弟节点染成父节点的颜色,将父节点和远侧子节点染黑,然后以父节点为轴左旋。这样就恢复了各条路径黑高相等的性质,并结束修复。
这些情形要么将亏缺向上传递,要么通过局部调整将其消除。如果亏缺到达根节点,就可以舍弃这重额外黑色,因为从根到叶的所有路径都会减少同样的一重黑色贡献。
传统的自底向上删除算法最多需要三次旋转,不过重新着色和向上传递可能需要 步。实现时,仍须确定 NIL 替代节点的父节点。常见的解决方法是使用带有适当父指针的哨兵节点,或将父节点作为单独的参数传给修复例程。许多删除操作中的错误都源于父节点跟踪不正确、后继节点移植有误,或未能区分被移除节点原本的颜色与替代节点被赋予的颜色。
多路树视角、历史与变体
红黑树的概念基础在于它与 2–3–4 树的对应关系。2–3–4 树是一种平衡多路搜索树,每个内部节点包含一个、两个或三个键。如果将每个红色节点并入其黑色父节点,形成的每一组就对应一个多路树节点。没有红色子节点的黑色节点表示一个 2-节点;有一个红色子节点时表示一个 3-节点;有两个红色子节点时则表示一个 4-节点。
红色节点本身不能有红色子节点,因此这些节点组最多只包含三个键。黑高相等则保证了所得多路树的所有外部叶节点都位于同一深度。因此,颜色规则并非对二叉树施加的任意限制,而是对平衡多路树层次结构的一种编码。一个 3-节点既可以用左倾红链接表示,也可以用右倾红链接表示,因此这种对应关系并不唯一。
从这一角度看,插入就是向多路树节点添加一个键,并在必要时分裂已满的节点。对一个具有两个红色子节点的黑色节点进行重新着色,相当于将其所表示的多路树节点中的中间键向上传递。删除则对应于在节点缺少键时,向相邻节点借用键或合并节点。二叉树中的各种旋转操作实现了这些变换,而无须显式存储大小可变的节点。
鲁道夫·拜尔(Rudolf Bayer)于 1972 年提出了对称二叉 B 树,这是现代红黑树的主要前身。列奥尼达斯·J. 吉巴斯(Leonidas J. Guibas)和罗伯特·塞奇威克(Robert Sedgewick)在 1978 年发表的论文《平衡树的双色框架》(A Dichromatic Framework for Balanced Trees)中提出了红黑树的表述形式。该框架将二叉表示、基于颜色的不变式和平衡算法联系起来,推动确立了后续论述中采用的术语和分析方法。
有若干类算法满足相关的不变式。自底向上的算法先修改树,再向根节点移动,沿途修复违反不变式的情况。自顶向下的算法则在向下遍历的过程中变换节点,使最终的插入或删除无须采用同样的向上修复方式即可完成。两者的区别影响的是控制流程、临时状态和实现复杂度,而非树高为对数级这一根本保证。
左倾红黑树进一步限制红链接的方向,以减少可能出现的结构。一种常见版本表示的是 2–3 树:在操作完成后的结构中,只允许左倾红链接,并且不允许任何节点有两个红色子节点。另一些版本则兼容 2–3–4 树,并采用不同的变换规则。不同变体的插入和删除过程不能直接互换使用。
函数式表述是另一类重要变体。克里斯·冈崎(Chris Okasaki)在 1999 年的论述中,用一组精简的平衡模式表达了适用于不可变树的插入操作。这类算法很自然地支持结构共享,但其各种情形的组织方式不同于传统的父指针实现。因此,不应将某一种表述中常见的旋转次数界限不加审视地套用到另一种表述上。
表示、正确性与验证
传统的可变红黑树节点存储一个键或键值对、左右子指针、父指针以及颜色。从逻辑上说,颜色只需要一个比特的信息,但由于内存对齐和对象布局的影响,独立的颜色字段在物理上可能占用更多空间。有些实现将颜色编码在已对齐指针未使用的低位中。这种紧凑存储依赖于对底层表示的假设,并非在所有平台上都可移植。
父指针可以简化插入修复、删除修复和迭代器移动,但这种数据结构并不一定需要父指针。递归实现可以通过调用栈获取祖先信息;迭代实现则可以显式保存路径。由于树高为对数级,递归版本使用 的栈空间。使用父指针的迭代版本可以用 的辅助空间完成常规更新,不计新分配的节点。
正确性包含几个相互独立的方面。树必须保持搜索次序,维持有效的链接和父子关系,满足颜色不变量,并维护所有相关元数据。一棵树即使已经违反黑高约束,仍可能在多次查找中返回正确结果。反过来,即使颜色完全符合要求,也无法弥补子树位置错误或比较器不一致的问题。
递归验证器可以同时检查这些性质。它将允许的键值边界传入各个子树,检查父指针和红色子节点限制,并获取左右子节点返回的黑高。如果验证器始终采用不将 NIL 计入黑高的约定,那么 NIL 子节点就返回零。对于内部节点,要求左右子节点返回的计数相等,并且仅当该节点为黑色时,返回的计数才加一。这种计数约定与某些教科书中的定义不同,但检验的是同一个相等性条件。
测试通常会在执行生成的操作序列后,将树中的内容与更简单的参考表示进行比较。重要的测试情形包括按升序和降序插入、反复删除根节点、交替删除最小值和最大值、删除有两个子节点的节点,以及持续删除直至树为空。小规模穷举测试尤其有效,因为许多缺陷只有在特定操作序列下才会出现,而不是由某个特殊的键单独触发。
形式验证将上述各项要求分别转化为明确的证明义务。旋转需要论证其保持搜索次序;插入的各个情形需要证明黑高保持不变,并证明红红冲突的转移受到控制;删除则需要用一个不变量描述黑色亏缺。对于基于指针的实现,证明还必须涵盖内存所有权以及不存在非预期环的问题。
比较器也是正确性假设的一部分。有序容器通常要求比较器满足严格弱序或与之兼容的全序。即使每一次旋转和重新着色都实现正确,可变的键、不一致的比较结果或未妥善处理的异常值,仍可能破坏搜索结构。
数据扩充与专门查询
红黑树的一大优势是,节点可以存储其子树的汇总信息。如果仅根据节点自身的数据项及其子节点的汇总信息,就能在常数时间内重新计算该信息,那么维护它通常不会改变更新操作的对数级时间复杂度。结构变化只会影响搜索路径,以及每次旋转涉及的少量节点。
典型的例子是顺序统计树。每个节点都存储其子树的大小:
要查找指定秩的键,可以将目标秩与左子树的大小进行比较。如果秩从 1 开始计数,当前节点的局部秩就是 。目标秩较小时,进入左子树;目标秩较大时,先减去当前节点的局部秩,再进入右子树。计算某个键的秩时,也类似地累加沿途跳过的左子树的大小。这两种操作的时间复杂度均为 。
旋转时的更新是局部的。左旋之后,原子树根节点的子节点发生了变化,因此必须先重新计算它的子树大小。随后,使用已更新的子节点重新计算被提升节点的子树大小。旋转后的子树包含的元素与旋转前相同,因此其总大小不变。即使没有发生旋转,插入和删除操作仍需要沿受影响的祖先路径更新子树大小。
区间树是另一个经典的数据扩充示例。节点存储按下端点排序的区间,同时记录其子树中最大的上端点。对于闭区间 和 ,两者重叠当且仅当
在查找重叠区间时,如果某棵左子树的最大上端点小于查询区间的下端点,就可以排除该子树。搜索过程结合这一汇总信息与下端点的排序关系,选择可能包含重叠区间的子树。在标准的扩充结构中,找到一个重叠区间需要 时间。报告所有重叠区间则需要采用适合该操作的遍历方式和复杂度分析,不能简单地重复单路径搜索的证明。
其他有用的汇总信息包括子树元素之和、最小优先级和序列聚合值。对于满足结合律的聚合运算,节点可以按顺序组合左子树的汇总值、自身的值和右子树的汇总值,并存储结果。该运算不必满足交换律,因为旋转不会改变中序遍历顺序。不过,查询复杂度仍取决于所支持的具体操作:有了聚合值,并不意味着所有可能的查询都能在对数时间内完成。
设计的核心要求是能够局部维护,而不只是增加额外字段。如果某个量在每次旋转后都需要检查整棵子树才能计算,就可能破坏预期的更新时间界限。因此,采用数据扩充的实现需要明确规定信息传播、节点替换以及旋转时重新计算的规则。这些规则与红黑树本身的修复操作同样重要。
应用及与其他结构的比较
红黑树常用于实现有序映射和有序集合。Java 的 TreeMap 和 TreeSet 就是典型例子。广泛使用的 C++ 标准库实现也采用红黑树来实现有序关联容器,不过 C++ 标准规定的是行为和复杂度要求,并不强制采用这种特定的内部表示。在讨论节点布局或平衡调整的各种情形等实现细节时,这一区别很重要。
Linux 内核提供了侵入式红黑树接口:用于链接树节点的对象直接嵌入应用自身的数据结构中,而不是另行分配一个通用包装对象。这样既能直接控制对象布局,也能避免树节点与其承载的数据之间多出一层间接访问。内核中使用该接口的代码需自行提供比较和查找逻辑。接口还支持增广,可在需要时维护额外的子树元数据。树接口本身并不提供并发访问所需的锁机制。
与AVL树相比,红黑树允许更宽松的高度上界。AVL树将同一节点左右子树的高度差限制为至多 1,因此最坏情况下的树高更小。不过,常规红黑树算法对每次插入或删除所需的旋转次数给出了较小的常数上界。这些理论差异并不能单独决定性能:查找频率、内存分配策略、键的大小以及处理器行为所带来的影响,都可能超过平衡调整的开销。
B树或 B+ 树在每个节点中存放多个键,从而减少节点访问次数,并改善面向页的存储中的局部性。因此,这些结构是许多数据库索引和存储引擎的核心。红黑树的每个元素都需要多个指针,而且各节点的内存分配可能较为分散,通常不太适合磁盘页的组织方式,在内存中也可能造成大量 CPU 缓存未命中。即使都能提供对数时间的查找,紧凑数组或高扇出树的性能也可能优于红黑树。
在满足适当散列假设的情况下,散列表通常能提供期望常数时间的查找,但它并不会自然地保持元素有序。红黑树无需依赖散列值的分布,就能保证最坏情况下的比较次数为对数级。树堆则利用随机优先级获得期望为对数级的树高,而伸展树通过围绕访问位置重组树结构,实现对数级的摊还操作开销。这两者都无法提供与常规红黑树完全相同的单次操作最坏情况保证。
在采用不可变数据的软件中,基于红黑树的可持久化数据结构只需复制从根到叶的路径中发生修改的部分,并共享未改变的子树,就能保留先前的版本。因此,单次更新通常会创建 个新节点。在使用可变数据的并发软件中,旋转和重新着色需要与读写操作协调;红黑树在顺序执行时的正确性并不意味着线程安全。专门的并发变体可能允许暂时失衡,或采用不同的同步协议,因此必须将其提供的保证与普通顺序红黑树的保证分开分析。