二叉搜索树(BST)是一种数据结构,它将键存储在二叉树中,并遵循以下排序规则:节点左子树中的每个键都排在该节点的键之前,右子树中的每个键都排在其后。这种递归组织方式使查找过程在每次比较后都能排除一棵子树。节点可以像集合那样只存储键,也可以像有序字典那样将键与值关联起来。
二叉搜索树既能高效查找,又能利用所存内容的顺序。它可以查找最小键和最大键,确定相邻的键,枚举某个范围内的条目,并按排序顺序输出所有条目,而无须重新排列。其主要局限在于,仅有有序性并不能保证效率:一棵包含 个键的树,其高度可能与 成正比,也可能退化为一条长度与 成正比的链。平衡、随机化和自调整等变体以不同方式应对这一局限。
二叉搜索树既是一类实用的数据结构,也是算法分析中的核心研究对象。对它的研究将树的几何形态、计算复杂性、概率、内存组织以及动态有序集合的设计联系起来。
排序规则与结构表示
二叉搜索树有一个根,每个节点可以有零个、一个或两个子树。节点通常包含一个键、一个关联值,以及指向左右子节点的引用。有些实现还会存储父节点引用或维持平衡所需的信息。空树没有根。叶节点没有子节点,而内部节点至少有一个子节点。与其他形式的树(数据结构)一样,二叉搜索树也具有层次结构,但搜索树的排序规则使这一层次结构与所存储的数据之间具有特定的关系。
对于互不相同的键,其定义性不变量可以写为
其中, 和 分别表示节点 的左子树和右子树中的所有节点。这一要求适用于整棵子树,而不只是直接相连的子节点。例如,若根节点的键为 ,其左子节点的键为 ,而该左子节点的右子节点的键为 ,那么即使每一对直接相连的父子节点之间的比较在局部看来都符合规则,整棵树仍然违反了这一不变量。
键不一定是整数。只要比较关系具备所需的一致性,字符串、日期、元组以及应用程序自定义的对象都可以用作键。许多程序库采用严格弱序:如果两个键都不排在对方之前,就将它们视为等价。这种等价关系不一定与对象同一性或单独定义的相等运算一致。如果没有额外的比较策略,涉及 NaN 的普通浮点数比较就不满足通常的排序假设。同样,即使没有改变任何指针,直接修改已存储的键也可能破坏树的结构约束。
对于重复键,必须明确其表示策略。树可以拒绝重复键,替换等价键所关联的值,存储出现次数,或在一个节点上附加一组记录。另一种方法是按复合键对记录排序,例如在用户提供的键后面加上一个唯一标识符。在非平衡树中,可以简单地将相等的键始终放在同一侧,但旋转操作可能破坏这一约定。因此,平衡多重集的实现需要采用与其结构调整操作相容的不变量。
树的高度通常定义为从根到叶节点的路径中,边数的最大值;按此定义,只有一个节点的树高度为零。有些描述则统计节点数,因此高度会相差一。两种约定都不会改变渐近分析的结果,但在实现和证明中,必须始终采用同一种约定。
查找、导航与有序遍历
查找从根节点开始,将目标键与当前节点的键进行比较。若两者相等,查找成功并结束;若目标键较小,则转向左子节点;若目标键较大,则转向右子节点。如果到达空的子节点位置,就能确定该键不存在。这种方法类似于在有序序列上进行二分查找,但树中的划分由树的形状决定,而不是通过反复选择数组的中间位置来实现。因此,在不平衡的树中,每一步不一定都能将剩余候选项减半。
查找过程中,可能包含目标键的区间不断缩小。从键为 的节点向左移动后,所有剩余候选键都必须小于 ;从键为 的节点向右移动后,所有剩余候选键都必须大于 。这些边界构成了一个实用的循环不变量,可用于证明算法的正确性。迭代实现只需保存当前节点的引用,辅助空间为常数。递归实现则直接表达了同样的推理过程,但消耗的栈空间与查找路径的长度成正比。
最小值和最大值查询只需沿一个方向前进:不断转向左子节点即可找到最小值,不断转向右子节点即可找到最大值。一个节点的后继是严格大于其键的最小键所在的节点。如果该节点有右子树,其后继就是右子树中的最小键节点。否则,沿父节点方向向上回溯,第一次从左子节点上行时到达的祖先就是后继。前驱的查找方式与之对称。如果没有父节点引用,实现时可以保留查找路径,或从根节点重新查找,并在途中记录候选祖先。
中序遍历依次访问左子树、当前节点和右子树。有序性不变量保证了这一过程会按排序顺序输出各个键。这是一种特定的深度优先搜索遍历方式,访问全部 个节点需要 时间。对于高度为 的树,递归遍历需要 的辅助栈空间;使用显式的栈也具有相同的空间界限,而且不依赖编程语言的调用栈。如果节点带有父节点引用,则完成整棵树的遍历时,只需维护常数大小的遍历状态。
有序导航还支持下界和上界查询。下界是第一个不小于目标值的键,上界则是第一个严格大于目标值的键。查找过程中,算法每次向左移动时都会记录当前最优的候选键。要输出某个区间内的键,可以先找到第一个符合条件的键,再按顺序继续访问,直到越过区间上端点。通过维护适当的遍历状态,输出 个结果只需 时间,而不必执行 次彼此独立、从根节点开始的查找。
插入、删除与构建
插入操作首先沿着一次查找失败时所经过的路径前进。在查找终止的空子节点位置,算法放入一个新的叶节点。例如,依次插入 ,会得到一棵以 为根的树,较小的键位于其左子树中,较大的键位于其右子树中。插入顺序决定了树的形状:若将同一组键按递增顺序插入一棵普通的非平衡树,就会形成一条向右延伸的链。在执行任何平衡调整之前,查找和建立链接需要 时间。
删除操作主要分为三种情况。叶节点可以直接移除。只有一个子节点的节点可以由其子节点替代,并相应调整父节点的引用。删除根节点时,需要更新树的根引用,而不是父节点的链接。这些情况都能保持键的有序性,因为替代节点的子树原本就处于同一个允许的键值区间内。操作过程中还必须更新父节点引用、子树节点数以及其他辅助字段。
对于有两个子节点的节点,一种标准方法是用其中序后继(即其右子树中键最小的节点)的条目替换该节点的条目,然后从原位置删除这个后继节点。后继节点不可能有左子节点,因此删除它就归结为较简单的情况。使用中序前驱也可以对称地完成这一操作。这一过程通常称为 Hibbard 删除法,名称源于 Thomas N. Hibbard 在 1962 年对树的插入和删除操作所作的论述。
在实现层面,替换条目与移动节点并不能等同视之。当记录体积较大、不可复制,或外部通过节点地址标识记录时,复制后继节点的键和值可能并不方便。另一种做法是直接将后继节点移植到被删除节点的位置。无论采用哪种方法,都必须维护所有相关链接和元数据。在平衡树中,删除还可能触发沿祖先路径进行的修复;仅仅完成普通搜索树的删除操作,并不能恢复平衡不变式。
构建树不一定要通过反复插入来完成。对于一个由互不相同的键组成的有序数组,选择中间元素作为根,再递归地用左右两半构建子树,即可在 时间内创建一棵高度平衡的树。相比之下,将同一个有序数组中的元素依次插入一棵非平衡树,需要 时间。如果已知长度,有序链表也可以在线性时间内转换为树:按中序遍历次序进行构建,在构建预定大小的子树时,依次读取链表中的条目。这些批量构建方法利用了通用在线插入操作无法预先获得的信息。
高度、平均表现与复杂度界限
搜索树基本操作的开销主要取决于树的高度。若以边数计高度,一棵高度为 的二叉树最多包含 个节点。因此,任何包含 个节点的二叉树都满足
平衡程度适当的树,其高度接近这一对数级下限。另一个极端是链状树,其高度为 。因此,查找、插入和常规删除操作的时间开销均为 :在平衡树中具有对数级性能,而在不加限制的树中,最坏情况下则为线性级性能。
讨论平均情况时,必须明确所采用的概率模型。如果将 个互不相同的键按均匀随机排列的顺序插入,得到的随机搜索树,其期望查找开销和期望高度均为对数级。这是两个不同的结论:平均深度反映的是典型已存储键的情况,而高度反映的是最深路径的情况。这里的假设针对插入的相对顺序,而不只是数值键的取值看起来是否杂乱无章。即使相邻数值之间的间隔变化不可预测,单调有序的输入序列仍可能生成一棵链状树。
在随机排列模型中,令 为所有节点的深度之和,其期望为
其中, 是第 个调和数。由于 ,忽略低阶项后,查找一个均匀随机选取的已存储键,平均约需进行 次节点比较。这约等于 ,说明随机搜索树虽然不像近乎完全的二叉树那样浅,仍然具有较高效率。这些结果依赖于概率假设,并不保证某一次具体操作的开销。
基于比较的查找还存在一个下界。在有序键及其可能的间隙中进行查找,需要区分与 成正比数量的结果。因此,二元比较过程在最坏情况下需要对数级深度。在比较模型中,平衡二叉搜索树的性能在渐近意义上达到了由此得到的 下界。这并不排除在更强假设下存在更快的数据结构,例如键为位宽有界的整数,且可以使用专门的机器操作。
常见的时间复杂度界限通常将每次键比较视为常数时间操作。比较长字符串或复合记录的开销可能更高,尤其是在许多键具有较长公共前缀的情况下。存储节点需要占用 空间,但其实际内存占用还包括子节点指针、可选的父节点指针、平衡信息字段、有效载荷以及内存分配器的开销。辅助空间复杂度取决于具体操作:迭代查找只需 额外空间,而递归操作可能需要 空间。
旋转与确定性平衡
树旋转只改变树的一小部分,而不改变其中序序列。在右旋中,具有左子节点 的节点 移到 下方; 原来的右子树成为 的左子树。若周围的三棵子树分别为 、 和 ,则它们的键仍保持如下顺序:
左旋是这一变换的逆操作。一次旋转只需更新常数个结构引用,不过也可能需要重新计算局部元数据。
AVL树由格奥尔基·阿德尔松-韦尔斯基和叶夫根尼·兰迪斯于1962年提出,要求每个节点的两棵子树高度之差至多为一。其平衡因子记录这一高度差。更新后,高度变化会向根节点传播,直到相关高度不再变化,或通过旋转恢复平衡。根据失衡的方向,修复时需要执行一次旋转或连续两次旋转。一次插入至多需要进行一次这样的局部修复,不过,确定修复位置可能需要沿祖先链向上遍历对数级数量的节点。
AVL树的高度为对数级,因为给定高度下的最少节点数满足类似斐波那契数列的递推关系。若空树高度为 ,叶节点高度为 ,则有:
这一递推关系的增长速度意味着,树高的上界约为 。删除可能降低某棵子树的高度,并导致更高处进一步失衡,因此可能需要在多个祖先层级上进行修复。这与插入的情形不同,也是实现中容易出错的一个重要原因。
红黑树使用节点颜色和另一组不变式。在一种常见定义中,根节点和空叶节点为黑色,红色节点不能有红色子节点,而且从任一节点到其任一空后代节点的每条路径都包含相同数量的黑色节点。按照相应的黑高计算方式,这些条件保证任意根到叶路径的长度都不超过另一条的两倍,从而使树高至多为 。更新操作通过重新着色和旋转来恢复这些规则。
AVL树和红黑树的查找、插入和删除操作在最坏情况下都具有 的时间复杂度,但它们对树形和维护方式的要求不同。AVL树对高度的限制更严格;红黑树则允许更大的局部差异。实际运行速度取决于键的比较成本、更新频率、节点表示方式和缓存行为,而不只是高度上界。其他确定性方法包括重量平衡树和替罪羊树。后者在不满足平衡条件时重建整棵子树,这说明维持对数级树高并不一定要完全依赖局部旋转。
随机化变体与自调整变体
树堆为每个节点分配一个键和一个优先级。键满足二叉搜索树的不变式,而优先级满足堆序不变式。当键和优先级各不相同时,这两个条件便唯一确定了树的形状。插入时,先像普通二叉搜索树那样将新键放在叶节点位置,再通过旋转使其上移,直到恢复优先级顺序。删除时,可以通过旋转将目标节点下移,直到能够将其移除;也可以根据优先级合并它的两棵子树。
如果优先级的相对次序是均匀随机的,且独立于键,那么树堆的形状分布就与按随机排列顺序插入键所构建的搜索树相同。因此,即使键按有序顺序到达,查找和更新的期望开销仍为 。这是随机化算法的一个例子:随机性由算法实现自身提供,而不是假定输入具有随机性。不过,某次具体生成的树仍可能具有线性高度,因此这种期望保证并不是确定性的最坏情况界。
伸展树采用另一种方法。每次访问后,它都会通过一系列称为“伸展”的旋转操作,将被访问的节点移向根节点。基本情形包括最后的一次单旋转、两次同向旋转,以及两次反向旋转,通常分别称为 zig、zig-zig 和 zig-zag。查找失败时,实现中通常会对最后访问的节点执行伸展。伸展树不需要显式维护平衡因子、颜色或随机优先级。
单次伸展操作可能耗时 。尽管如此,在适当计入初始树的影响后,伸展树在一系列标准操作中,每次操作的摊还时间仍为 。摊还分析并不是对随机输入求平均,而是通过考察高开销操作如何改变结构、使后续操作的开销降低,来约束整个操作序列的总开销。伸展树还具有更强的、与访问局部性相关的性质,包括能够高效地反复访问一个较小的键工作集。
这些方案体现了不同的效率观念。确定性平衡树限制每次操作在最坏情况下所需的结构调整工作量。树堆通过随机选择获得期望性能保证。伸展树则容许偶尔出现高开销操作,以利用访问模式。因此,平均吞吐量要求、严格的延迟要求,以及以反复访问相近键为主的工作负载,可能各自适合不同的设计。
结构调整也会影响读取行为。在普通 AVL 树或红黑树中,查找不必改变树的结构,而伸展树的查找通常会改变结构。这一区别对只读共享、同步和持久化都很重要。一种能够降低后续查找深度的方法,也可能同时增加写入或竞争。
信息增广、秩查询与树的组合
搜索树除了保存键和平衡信息,还可以维护其他信息。最常见的例子是在每个节点中存储其子树的节点数:
其中空子树的大小为零。借助这些计数,顺序统计树无需遍历所有排在前面的元素,就能回答秩查询和选择查询。如果重复键以计数表示,也可以调整这一递推关系,使其统计所存储的键的出现次数,而不是不同节点的数量。
要选择从零开始计数、秩为 的键,设当前节点左子树的大小为 。若 ,则继续向左查找;若 ,则返回当前条目;否则,继续向右查找,并将秩改为 。要计算小于目标值的键的数量,可以像普通查找一样向下遍历,每次向右移动时,都累加左子树的大小再加一。这两种操作的时间复杂度都是 ,因此在平衡树中均为 。插入、删除和旋转之后,都必须更新这些计数,包括结构发生变化的节点上方各祖先节点的计数。
区间树可以按区间的下端点组织区间,同时在每棵子树中存储最大的上端点。查找与查询区间重叠的区间时,可以利用这个最大值排除那些所有区间都过早结束的子树。采用闭区间约定时,如果左子树的最大上端点小于查询区间的下端点,那么该子树中就不可能存在重叠区间。经过增广的平衡树可以在对数时间内找到一个重叠区间。要报告所有重叠区间,则需要根据具体的区间树变体采用相应的遍历方法,并分析其复杂度。
其他有用的汇总信息包括子树中数值的总和、最小值、最大值,以及面向具体应用的组合聚合结果。设计时的关键要求是:每个节点的汇总信息都能根据自身条目及其子节点的汇总信息高效地重新计算。如果局部重新计算只需常数时间,旋转就能在不改变更新操作渐近复杂度的前提下维护增广信息。有些汇总信息还支持范围聚合:对于完全符合条件的子树,可以直接使用其存储的结果,无需逐条访问其中的记录。
搜索树也可以围绕分裂和合并来组织操作。按某个键分裂,会将条目划分为有序的几个部分;合并则将键值范围满足相应先后关系的树组合起来,有时还会在两棵树之间加入一个中间键。这些操作的实现方式取决于所用的平衡算法。在某些场景下,相比反复执行单键更新,它们更适合用来批量计算集合的并集、交集和差集。
增广并不能让任意查询都变得高效。例如,一棵按姓氏排序的树,通常无法在对数时间内找出所有具有某个指定年龄的记录,除非另有索引或适当的汇总信息。增广树是否有用,取决于其排序方式和元数据能否在保证正确性的前提下,排除大范围的数据,或直接利用这些数据的汇总结果。
内存布局、持久化与并发访问
传统的表示方式为每个节点单独分配内存,并通过指针连接节点。这种方式支持局部插入和删除,但可能使键值相近的节点分散在内存各处。查找时,每一层都可能需要一次依赖前一次结果的指针加载,从而减少硬件预取的机会。由此产生的 CPU 缓存访问特性,可能使平衡树的实际速度低于仅根据比较次数作出的预期。内存池、内存分配区、紧凑索引和内嵌链接可以减少分配开销或改善局部性,但这些方法都不能自动使搜索路径在内存中连续存放。
侵入式树将链接字段存储在应用程序对象内部,而不是存放在单独的包装节点中。这可以避免额外的内存分配,并让现有记录直接成为树中的成员,但对象的生命周期也因此成为保证树正确性的条件之一。记录只要还链接在结构中,就不能被销毁。相比之下,非侵入式容器自行管理节点,可以提供更明确的所有权边界。这一取舍涉及内存管理和接口设计,而非搜索不变式本身。
可持久化数据结构在更新后仍允许访问先前的版本。搜索树常用的一种技术是路径复制:复制从根到叶子的修改路径上的节点,复用未改变的子树,并发布新的根节点。在平衡树中,一次标准更新会创建 个新节点,其中包括局部结构调整所需的节点。结构共享避免了复制整个集合。这种方法尤其适合函数式编程,因为节点可以在构造后保持不可变。
父节点引用会使结构共享变得复杂,因为多个版本共享的子树可能具有不同的逻辑父节点。因此,可持久化实现通常只使用向下的链接,并单独维护遍历上下文。其内存回收方式也不同于单棵可变树:只要任何保留的版本仍能到达某个旧节点,该节点就仍然存活。垃圾回收或显式的所有权机制可以处理这一问题,但保留大量版本可能会使相当一部分历史数据一直驻留在内存中。
并发访问除了要求树本身正确,还带来了协调方面的要求。粗粒度锁可以将更新操作串行化并保护读取操作,而细粒度方法则对较小的区域加锁,或使用原子操作。旋转和删除会影响多个链接,因此仅保证每个指针各自正确是不够的:读取者必须按照算法的同步规则观察到有效状态。在并发计算中,可线性化的实现必须使每个已完成的操作看起来都在其调用与返回之间的某一时刻生效。
内存回收与逻辑删除是两个独立的问题。被移除的节点可能仍被另一个较早开始遍历的线程引用。危险指针、基于纪元的回收或垃圾回收等技术可以防止其内存被过早复用。一个设计是无锁、无等待还是基于锁,取决于对其整体进展保证的完整论证,而不能仅凭它是否使用原子指针更新来判断。
应用与替代方案
二叉搜索树很适合实现有序集合和有序映射。除了判断元素是否存在以及按键查找值之外,它们还支持前驱查询、按序遍历和区间筛选。例如,按时间戳排序的日历索引可以找到指定时间或之后的第一个事件,然后依次列出后续事件。平衡树在允许任意插入和删除的同时,仍能高效地完成这些操作。无序字典提供的接口则有所不同,无法直接支持这些依赖顺序的操作。
在采用合适的哈希方法和容量调整策略等假设下,哈希表通常能以期望常数时间完成成员查询、插入和删除。当主要操作是精确匹配键的查找时,哈希表往往更合适。相比之下,搜索树在保持平衡时能提供确定性的对数时间界限,并支持利用键之间的顺序关系。两者的比较并非简单的“常数时间与对数时间之争”:计算长键的哈希值可能代价不小,而树中的比较可能在遇到较短的不同前缀后就结束;此外,冲突处理方式、内存布局和工作负载都会影响实际开销。
有序数组可以通过二分查找实现对数时间的查找,同时具有存储紧凑、顺序遍历高效的优点。用作动态有序集合时,它的主要局限在于:插入或删除一个内部元素通常需要移动 个元素。因此,数组很适合静态或以静态为主的数据,而树则能适应频繁更新,无须移动整个后缀部分。混合设计可以将有序数据块与索引结合起来,从而同时改变更新开销和局部性。
对于以外部存储为后端的数据库索引,B树或 B+ 树通常比每个节点只存一个键的二叉树更合适。它们的每个节点都包含多个键和子节点引用,从而提高分支数,减少查找所需的块传输次数。B+ 树的叶节点组织方式还支持高效的有序扫描。二叉搜索树具有 的比较次数上界,但仅凭这一点并不能使它成为良好的磁盘索引;相关的成本模型还必须考虑页面、缓冲和持久化写入。
其他数据结构则各有所长。二叉堆可以高效地提供最小值或最大值,但并不满足搜索树的有序性约束,通常也无法在对数时间内找到任意给定的键。跳表通过相互链接的多个层级提供另一种有序表示,常见操作通常具有期望对数时间复杂度。字典树沿着键的符号或比特逐步查找,而不是比较完整的键,因此其开销更直接地取决于键的长度和表示方式。
平衡搜索树也会作为更大型算法的组成部分出现。计算机图形学中的平面扫描算法可能需要维护一个由当前活动对象组成的有序集合;操作系统组件也可能需要维护由区间或调度实体组成的有序集合。这些应用可能带来额外约束。尤其是,如果比较器依赖于不断变化的外部状态,而算法又没有显式处理每一项会影响已存元素顺序的变化,树的有序性就可能在毫无征兆的情况下被破坏。
历史发展与正确性方法
二叉搜索树源于早期对信息检索、符号表和动态存储组织的研究。历史上出现过多种相关思想,并不存在一个公认的单一发明事件。其核心吸引力在于保留二分查找选择性分支的特点,同时避免每次插入后都要移动有序数组中的元素。后续研究逐渐将两个问题区分开来:维护键的顺序,以及控制不断变化的操作序列所形成的树形。
几项里程碑式的进展确立了主要的平衡方法。Adelson-Velsky 和 Landis 于 1962 年提出了 AVL 树。Rudolf Bayer 于 1972 年提出了对称二叉 B 树,Leonidas Guibas 和 Robert Sedgewick 则于 1978 年提出了红黑树形式。Daniel Sleator 和 Robert Tarjan 于 1985 年提出了伸展树。Cecilia Aragon 和 Raimund Seidel 于 1989 年提出了随机化搜索树,确立了通常与树堆(treap)联系在一起的方法。这些结构的差别体现在不变量和保证上,而不只是实现细节上。
正确性证明从有序性不变量入手,但还必须证明其表示结构确实是一棵树。子节点链接不能形成环;对于可变且不共享节点的树,同一个节点不应出现在两个不同位置。查找的正确性源于这样一个事实:每次比较排除的都只是那些不可能等于目标的键。插入操作会保持沿搜索路径累积的区间约束。删除操作则需要证明,用于替换的条目或子树符合被删除节点所允许的区间。
仅将每个节点与其直接子节点进行比较的验证器并不足够。更严格的方法是在遍历过程中传递上下界,检查每个键是否落在其继承的区间内。中序遍历也可以根据所采用的重复键处理策略检查单调性,但仍然需要结构检查,以发现环或非预期的节点共享。平衡变体还需要额外检查:AVL 树中存储的高度、红黑树的颜色和黑高条件,以及树堆的优先级顺序。
测试通常将不变量检查与对照更简单的参考表示相结合。在生成的操作序列中,每次操作之后,实现都可以验证中序遍历输出是否与包含预期条目的有序集合一致。有针对性的序列用于覆盖棘手情况:删除根节点、删除后继节点带有右子节点的节点、反复插入和删除极值键,以及触发多次平衡修复的工作负载。重复键,以及比较器判定等价但并非同一对象的情况,需要单独覆盖。
形式验证可以将树形、键的顺序、平衡性和元数据表示为明确的谓词。旋转操作的证明不仅必须确立中序序列保持不变,还必须确立每个被更新字段的正确性。对于并发树,证明还需处理并发干扰、内存安全以及操作的可观察效果。性能主张仍需单独证明:证明一棵树始终包含正确的键,并不能证明其高度为对数级、内存使用量有界,或具有某个摊还成本界。