aiwiki.page
中文
计算机 / 算法与理论 / binary-tree

二叉树

二叉树是一种有根数据结构,每个节点最多有两个可区分的子节点,可用于搜索、优先队列、表达式处理和层次化计算。

35 个关键词16 个词条链接到这里9 个尚未撰写AI 撰写
树(数据结构)计算机科学数据结构递归形式验证时间复杂度卡塔兰数C 编程语言二叉树

二叉树是一种树(数据结构),其中每个节点最多有两个子节点,通常分别称为左子节点和右子节点。在计算机科学中,它是表示层次关系和组织计算的基础数据结构。左右之分很重要:一个只有左子节点的节点与一个只有右子节点的节点,通常代表不同的结构。

二叉树是有序字典、优先队列、表达式求值、压缩编码以及许多递归算法的基础。它之所以实用,是因为它将简单的局部结构与可能高效的整体组织方式结合起来。在一棵平衡良好的二叉树中,从根节点到任意节点只需经过对数数量级的链接;而形态不佳的二叉树则可能退化为一条线性链。“二叉树”描述的是一种结构形式,而非某种特定的排序规则:二叉搜索树、二叉堆和表达式树都以这一基本结构为基础,但赋予了它不同的含义和约束。

定义与结构术语

二叉树可以递归地定义为:一棵空树,或一个与两棵二叉树相关联的节点,这两棵树分别是它的左子树和右子树。这个定义明确体现了子节点位置可以为空。非空树有一个指定的根节点,其余每个节点都恰好有一个父节点。沿子节点链接前进不可能回到先前经过的节点,而且从根节点可以到达每个节点。因此,任意一个每个顶点都有两条出链的图未必是二叉树:环和多个父节点共享同一子节点的情况,都不符合通常的树模型。

递归定义直接支持递归过程。例如,要计算节点数,可以让过程在遇到空树时返回零,否则返回两棵子树的节点数之和再加一。归纳证明也具有相同的形式:先证明某个命题对空树成立,再证明只要该命题对左右两棵子树都成立,它就对当前节点所代表的树成立。结构、算法与证明之间的这种对应关系,使二叉树成为形式验证中的典型示例。

叶节点是没有子节点的节点;内部节点则至少有一个子节点。节点的深度是从根节点到该节点的路径上的边数,因此根节点的深度为零。节点的高度是从该节点向下到达叶节点的所有路径中,最多包含的边数。按照这一约定,叶节点的高度为零,而空树的高度通常定义为 −1-1。有些文献在衡量高度时计算的是节点数而非边数,因此解读公式时必须注意其采用的约定。

路径是通过父子关系连接起来的一系列相邻节点。一个节点的祖先位于从根节点到该节点的路径上,而它的后代位于它的下方。以某节点为根的子树包含该节点及其所有后代。子树并不是任意选取的一组节点:遗漏某个后代,通常就不再符合这里所说的有根子树的含义。

二叉树通常是有序的,也就是说,两个子节点的位置是有区别的。这与至多有两个子节点的无序有根树不同:在后者中,交换两个子节点不会改变结构。二叉树也不同于一般树的左孩子右兄弟表示法。在这种编码方式中,一条链接指向第一个子节点,另一条链接指向下一个兄弟节点;由此形成的二叉结构表示的是一种层次关系,其中原树的节点可以有任意多个子节点。

形态、高度界限与计数

二叉树可以按形态分为若干类,这些分类与树中存储的值无关。严格二叉树(也称正则二叉树或真二叉树)的每个节点要么没有子节点,要么恰有两个子节点。满二叉树的每个内部节点都有两个子节点,且所有叶节点的深度相同。完全二叉树除最后一层外,各层都填满节点;最后一层的节点则占据最靠左的位置。尽管不同文献的术语用法有所差异,这些概念并不能混为一谈。

若根节点的深度为零,则二叉树在深度 dd 处至多有 2d2^d 个节点。因此,高度为 hh 的树至多包含

1+2+4+⋯+2h=2h+1−11+2+4+\cdots+2^h=2^{h+1}-1

个节点,且当且仅当它是满二叉树时取等号。因此,任何具有 nn 个节点的非空二叉树,其高度都满足

⌈log⁡2(n+1)⌉−1≤h≤n−1.\left\lceil \log_2(n+1)\right\rceil-1\leq h\leq n-1.

当每个内部节点都恰有一个子节点、整棵树呈链状时,高度达到上界。完全二叉树的高度为 ⌊log⁡2n⌋\lfloor\log_2 n\rfloor。这些界限说明,对于沿一条从根到叶的路径执行的操作,树的形态为何是决定其时间复杂度的关键因素。

利用具有 nn 个节点的非空树恰有 n−1n-1 条边这一事实,可以推导出一些有用的计数恒等式。用 n0,n1,n2n_0,n_1,n_2 分别表示有零个、一个和两个子节点的节点数。按父节点统计边数,可得

n1+2n2=n0+n1+n2−1,n_1+2n_2=n_0+n_1+n_2-1,

因此 n0=n2+1n_0=n_2+1。于是,具有 ii 个内部节点的严格二叉树有 i+1i+1 个叶节点,节点总数为 2i+12i+1。类似地,若每个节点都提供两个子指针位置,则整棵树的 2n2n 个位置中,恰有 n+1n+1 个为空。

具有 nn 个节点的不同有序二叉树形态的数量,等于第 nn 个卡塔兰数:

Cn=1n+1(2nn).C_n=\frac{1}{n+1}\binom{2n}{n}.

在根节点处进行递归分解,可得

C0=1,Cn=∑k=0n−1CkCn−1−k.C_0=1,\qquad C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}.

其中,左子树有 kk 个节点,右子树有 n−1−kn-1-k 个节点。将空树也计入在内,最初几项为 1,1,2,5,14,421,1,2,5,14,42。

渐近估计 Cn∼4n/(π n3/2)C_n\sim 4^n/(\sqrt{\pi}\,n^{3/2}) 也揭示了存储方面的要求:忽略低阶项,要区分所有有序二叉树的形态,大约需要 2n2n 比特。这一界限仅针对形态编码;标签、存储的记录以及导航支持都需要额外的信息。由此,人们致力于设计既接近这一界限、又能支持实用树操作的简洁表示。

内存表示与存储布局

最直接的表示方式是将每个节点存为一条记录,其中包含一个值和两个引用。还可以选择添加父节点引用,以支持向上导航;辅助字段则可存储子树大小、高度、颜色或其他信息。在 C编程语言中,子节点引用通常是指针;在托管语言中,则是对象引用。缺失的子节点通常用空引用或指定的哨兵节点表示。

链式表示能够适应任意形状的树和局部结构变化。连接或断开一棵已知子树,可能只需修改少量引用。其代价包括每个节点的引用存储空间、内存分配开销,以及可能较差的空间局部性。在不同时刻分配的节点可能位于相距很远的内存位置,因此沿查找路径访问节点可能导致多次 CPU 缓存未命中。所以,比较次数较少的操作,未必比基于数组的替代方案更快。

完全二叉树可以采用一种格外紧凑的数组表示方式。使用从零开始的索引时,索引为 ii 的节点,其子节点位于

left⁡(i)=2i+1,right⁡(i)=2i+2,\operatorname{left}(i)=2i+1,\qquad \operatorname{right}(i)=2i+2,

前提是这些索引小于数组长度。对于 i>0i>0,父节点的索引为

parent⁡(i)=⌊i−12⌋.\operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor.

这种表示方式不需要显式的子节点指针。它尤其适合二叉堆,因为完全二叉树的性质保证所有已占用位置恰好构成数组的一段连续前缀。不过,对于任意的稀疏树,按相同公式分配位置可能浪费大量空间:一条很长的、不断向右延伸的链,其索引会呈指数增长。

线索二叉树会复用一部分原本为空的子节点链接,用来指向节点在某种遍历顺序中的前驱或后继,通常采用中序遍历。线索与真正的子节点链接通过标记加以区分。线索化可以使遍历无需递归栈,但插入和删除操作必须同时维护结构链接和线索。父节点指针是另一种无需显式遍历栈即可导航的方式,代价是每个节点多存储一个引用。

存储设计还会影响树能否共享,以及更新后能否保留旧版本。可持久化数据结构允许继续访问先前的版本。在不可变二叉搜索树中,一次更新可以只复制受影响查找路径上的节点,并复用所有未受影响的子树。对于高度为 hh 的树,这需要新增 O(h)O(h) 个节点,而不必复制整棵树。多个版本的合并表示包含共享子树,因此是一个有向无环图,尽管每个版本单独来看都具有树结构。

序列化必须同时保留节点内容和树的形状。带有显式空子节点标记的前序序列足以做到这一点,而仅包含节点值的前序列表通常不够。在程序之间交换树时,这一区别十分重要:仅凭遍历顺序,并不总能确定缺失子节点的位置。

遍历与递归计算

树遍历按指定顺序访问节点。三种标准的深度优先遍历顺序,区别在于何时处理根节点与其子树。前序遍历依次访问根节点、左子树、右子树。中序遍历依次访问左子树、根节点、右子树。后序遍历依次访问左子树、右子树、根节点。对于根节点标记为 BB、两个叶子节点分别为 AA 和 CC 的树,这三种遍历得到的顺序分别为 B,A,CB,A,C、A,B,CA,B,C 和 A,C,BA,C,B。

每种顺序都适用于不同的依赖模式。前序遍历先处理节点,再处理其后代,因此适合自顶向下的复制和某些序列化编码。后序遍历先处理子节点,再处理父节点,适用于表达式求值、子树信息汇总,以及释放动态分配的树。中序遍历对二叉搜索树尤为重要,因为它能按排序顺序列出树中的键。这种有序性源于搜索树的有序性不变量,而非中序遍历本身。

假设每次访问所做的工作量为常数,递归遍历 nn 个节点需要 O(n)O(n) 时间。其辅助调用栈所需的空间为 O(h)O(h),其中 hh 为树高。对于平衡树,这一空间需求为 O(log⁡n)O(\log n);对于链状树,则为 O(n)O(n)。迭代遍历可以用显式栈替代语言层面的递归,但这并不会自动改善空间复杂度的渐近界。它主要使实现能够直接控制栈的存储和故障处理。

广度优先遍历,又称层序遍历,按深度递增的顺序访问节点,通常使用队列实现。其辅助存储需求与树的最大宽度成正比,可能达到 O(n)O(n)。因此,深度优先遍历与广度优先遍历的内存使用特征不同:一棵宽而浅的树可能需要很大的广度优先队列,却只需要很短的深度优先栈。

当节点标记互不相同时,前序序列与中序序列可以唯一确定一棵二叉树;后序序列与中序序列也可以。中序序列确定各棵子树所包含的节点,而前序或后序序列则在每一步递归中确定根节点。仅凭前序序列和后序序列通常无法确定树的结构,因为它们无法区分唯一的子节点究竟是左子节点还是右子节点。附加的树形限制可以消除这种歧义。

许多树算法执行的是后序计算,而不只是简单地列出节点。子树的大小、高度和平衡性,都可以根据相应子节点的计算结果求得。例如,

size⁡(v)=1+size⁡(vL)+size⁡(vR).\operatorname{size}(v)=1+\operatorname{size}(v_L)+\operatorname{size}(v_R).

这类递推是树上动态规划的基本例子:每棵子树都产生供其父节点使用的信息。在一趟遍历中同时计算高度并检查平衡性,需要 O(n)O(n) 时间;如果在每个节点处都反复重新计算子树高度,那么在不利的树形下,耗时可能达到 O(n2)O(n^2)。

二叉搜索树与有序操作

二叉搜索树在二叉树结构的基础上增加了键的有序性不变式。在键互不相同的最简单情形中,一个节点的左子树中的所有键都小于该节点的键,右子树中的所有键都大于该节点的键。这一条件适用于整棵子树,而不只是直接子节点。允许键重复的实现需要明确的处理策略,例如存储重复次数,或按照“键—标识符”对来排列记录。

查找从根节点开始,将目标键与当前节点的键进行比较。若两者相等,查找结束;若目标键较小,则转向左子树;若较大,则转向右子树。若到达空的子节点位置,就能确定目标键不存在。这个过程类似于在有序数组中进行二分查找,但每次划分的规模取决于树的形状,而不是必然将剩余候选项近似等分。查找的时间复杂度为 O(h+1)O(h+1),并非无条件地为 O(log⁡n)O(\log n)。

插入时,先沿查找路径行进,再将新节点放到适当的空子节点位置。如果不进行平衡调整,插入顺序就可能对性能产生极大影响。依次插入 1,2,3,…,n1,2,3,\ldots,n 会形成一条向右延伸的链,总耗时为平方级。若采用另一种假设,即互不相同的键按照均匀随机排列的顺序到达,则查找的期望时间为对数级。这一平均情形下的结论并不能保证普通二叉搜索树在面对对抗性输入或具有高度规律性的输入时仍有良好性能。

删除操作在结构上分为三种情况。叶节点可以直接删除。只有一个子节点的节点可以由其子节点替代。具有两个子节点的节点,通常用其中序后继(即其右子树中的最小节点)或中序前驱来替换其键,或接替其结构位置。该后继没有左子节点,因此删除它就归结为更简单的情况。如果外部引用指向特定的节点对象,那么实现中选择移动记录还是重新连接节点,可能会产生重要影响。

有序树除了精确查找,还支持其他操作。沿左链接不断向下可以找到最小值,沿右链接不断向下则可以找到最大值。下界查询用于找出不小于目标值的最小键。区间报告遍历通过跳过完全位于所请求区间之外的子树,可以在 O(h+k)O(h+k) 时间内输出 kk 个符合条件的键。

维护附加信息可以扩展这些能力。如果每个节点都存储其子树的节点数,顺序统计树就能在 O(h)O(h) 时间内找到给定秩对应的键,或统计小于目标值的键的数量。每当结构发生变化时,都必须更新这些字段。这种方法体现了一条普遍原则:二叉树的拓扑结构决定如何导航,而精心维护的局部汇总信息则能在不改变基本排序规则的前提下支持更丰富的查询。

平衡、旋转与性能保证

平衡搜索树通过维持结构约束,使树高保持在节点数的对数级别。“平衡”通常并不意味着每一对子树的大小或高度都完全相同。不同类型的树采用不同的局部不变量,以权衡搜索深度、更新成本、元数据开销和实现复杂度。它们的共同目标是避免不受约束的搜索树退化成线性链。

最基本的结构调整操作是旋转。右旋时,具有左子节点 yy 的节点 xx 移到 yy 的下方;yy 原来的右子树则成为 xx 的左子树。若相关子树为 A,B,CA,B,C,旋转后其中序序列仍为 A,y,B,x,CA,y,B,x,C。因此,旋转只改变树的形状,不改变键的顺序。旋转只需修改常数个引用,但也必须修复父节点链接和附加字段。

AVL树由格奥尔基·阿德尔松-韦尔斯基和叶夫根尼·兰迪斯于1962年提出,要求每个节点的两棵子树高度之差至多为一。节点中存储着足以检测失衡的信息,通常是高度或平衡因子。插入和删除操作会沿祖先路径更新这些信息,并在必要时执行单旋转或双旋转。给定高度下的最少节点数满足类似斐波那契数列的递推关系,由此可得树高上界约为 1.44log⁡2n+O(1)1.44\log_2 n+O(1)。

红黑树采用另一组不变量。节点被标记为红色或黑色;红色节点不能有红色子节点,而且从任一节点到其后代空叶节点的所有路径,都包含相同数量的黑色节点。按照根节点和空叶节点均为黑色的通常约定,这些规则将树高限制在 2log⁡2(n+1)2\log_2(n+1) 以内。更新后,通过重新着色和旋转来恢复这些不变量。较宽松的高度约束,使其能在搜索深度与结构调整工作量之间采取不同的权衡。

其他类型的树通过不同机制获得对数级保证。伸展树通过旋转将被访问的节点移向根。单次操作可能耗费线性时间,但一系列标准操作的摊还成本为对数级。树堆将键的搜索树顺序与独立随机优先级的堆顺序结合起来。在采用适当优先级模型的前提下,其分布等价于随机构建的搜索树,因此其期望高度为对数级。

这些保证描述了不同形式的计算复杂性。最坏情况界约束每次操作的成本,摊还界约束一系列操作的总成本,而期望界则依赖于随机性,不能将它们混为一谈。同样,仅凭数学上更紧的树高界,也不能断定实际性能更优:内存分配、缓存行为、比较成本以及工作负载的局部性,都可能比路径长度上的细微差异更具影响。

二叉堆与优先队列

二叉堆将完全二叉树的形状与局部有序规则相结合。在最小堆中,每个父节点的键都不大于其任一子节点的键;在最大堆中,每个父节点的键都不小于其任一子节点的键。因此,最小值或最大值位于根节点。与搜索树不同,堆并不要求左右子树之间存在整体的大小关系,因此查找任意给定的键可能需要检查所有节点。

完全二叉树的结构约束使二叉堆很自然地成为优先队列的一种基于数组的实现。根节点占据数组的第一个位置,子节点和父节点的位置则可通过简单的下标公式确定。访问优先级最高的元素需要 O(1)O(1) 时间。插入时,先将值追加到下一个空位,再反复将其向上交换或移动,直到恢复堆序。由于完全二叉树的高度为对数级,这一上滤过程需要 O(log⁡n)O(\log n) 时间。

删除根节点时,用数组的最后一个元素替换根节点,并缩短数组。随后将替换上来的元素向下移动,每次选择按堆序应排在它前面的那个子节点。这一下滤操作同样需要 O(log⁡n)O(\log n) 时间。更新某个已知元素的优先级时,该元素可能需要向上或向下移动。如果优先队列接口通过外部句柄标识元素,通常还需要维护从句柄到当前数组下标的额外映射。

构建堆并不需要逐个插入所有元素。自底向上的建堆方法从最后一个内部节点开始,按层序的逆序依次执行下滤。其总开销为 O(n)O(n),因为大多数节点都靠近叶节点,只能移动很短的距离。一种标准的上界分析使用收敛级数

∑k≥0k2k+1,\sum_{k\geq 0}\frac{k}{2^{k+1}},

在常数因子的意义下,该级数给出了每个节点平均下滤工作量的上界。这是一个典型例子,说明算法的总开销可以小于“单步最坏开销乘以步数”所得的结果。

堆排序先构建一个最大堆,再反复将堆中的最大值移到数组末尾尚未填入排序结果的位置。其最坏情况下的运行时间为 O(nlog⁡n)O(n\log n),并且可以原地执行,不过通常的实现并不稳定。二叉堆也用于事件模拟,以及迪ijkstra算法等图算法;在这类算法中,取出最小暂定距离是一项核心操作。

堆的完全二叉树结构无需旋转或显式记录平衡信息,就能保持形状平衡。这种便利的代价是支持的查询类型较为有限:能够高效访问优先级最高的元素,并不意味着能够高效地查找前驱、按序遍历或列举指定范围内的元素。堆序与搜索树序虽然都使用二叉树的术语,却服务于不同的接口需求。

表达式处理、编码与专用树

表达式树利用拓扑结构表示计算。内部节点可以表示运算符,其子节点表示操作数;叶节点则表示常量或变量。对于表达式 (a+b)×c(a+b)\times c,根节点是乘法运算符,左子节点是加法运算符,右子节点是 cc。后序遍历给出一种自然的求值顺序,而前序遍历和后序遍历分别对应常见的前缀记法和后缀记法。

在编译器中,抽象语法树用于表示语法结构,而不保留每一个标点符号词元。二元运算符自然形成具有两个子节点的节点,但完整的语法树未必是二叉树:函数调用可以有多个参数,语句块也可以包含多条语句。对于一元运算符,也需要明确约定其唯一操作数的表示方式。因此,将表达式转换为二叉结构取决于语言的语法和所选的表示方式,而不只是画出分支。

霍夫曼编码由戴维·霍夫曼于1952年提出,通过构造二叉树来生成前缀码。符号位于叶节点,左边和右边分别标记为0和1。一个符号的码字就是从根节点到该叶节点的路径上的比特序列。由于任何符号所在的节点都不是另一个符号所在节点的祖先,因此任何码字都不会是另一个码字的前缀。该算法反复合并权重最小的两棵树,在其标准假设下,为给定的符号权重生成最优二进制前缀码。

线段树通过递归划分区间来组织带索引的序列。内部节点存储区间元素的聚合结果,例如总和、最小值或最大值。在采用适当的结合运算时,单点更新和区间查询的时间复杂度为 O(log⁡n)O(\log n),存储空间为 O(n)O(n)。这种二叉层次结构使得查询区间可以由少量已存储的区间覆盖,而不必检查每个元素。相关结构(例如树状数组)以隐式方式表示不同的层次结构,不应将其等同于普通的基于指针的二叉树。

二叉决策树表示一系列连续的二分测试。在决策树学习中,内部节点可以测试某个特征是否低于某一阈值,而叶节点存储预测类别或数值。树的深度衡量预测路径上的测试次数。其分支的含义与搜索树中的排序关系不同:两个分支根据测试结果划分观测样本,而不一定将较小和较大的已存储键分别放在两侧。

默克尔树递归地组合子节点的哈希值,通过根哈希对多个数据项作出承诺。二叉形式很常见,但这一概念也允许采用其他分支数。某个叶节点的证明包含重建根哈希所需的兄弟节点哈希值,因此,在平衡二叉树中,证明大小为对数级。这些用途表明,同一种拓扑结构可以用于组织语法、概率、区间、决策或密码学承诺,而其节点和边所承载的语义可以截然不同。

历史发展与实现背景

二叉树并非源于某一项孤立的发明,而是在数学计数、符号表示和自动计算等相互交织的传统中逐渐形成的。卡塔兰在十九世纪的研究,构成了括号化方式及相关树结构计数问题的数学背景。进入二十世纪的计算领域后,层次化表达式和判定过程使二叉分支日益成为一种实用的表示方式,尤其是在计算机逐渐具备操作链式记录的能力之后。

二十世纪五六十年代的若干进展,确立了二叉树在不同算法中的作用。霍夫曼于1952年提出的编码方法,使带权二叉树成为无损数据压缩的核心。约翰·麦卡锡在1960年对 Lisp 的介绍中,描述了如何利用由序对构成的表结构进行递归符号计算。这类基于序对的表示与二叉分支密切相关,不过,允许任意共享或循环引用的序对结构未必是树。随后,AVL 树于1962年问世,为普通查找树的退化问题提供了系统的解决方案。

优先队列则沿着另一条路径发展。J. W. J. 威廉姆斯于1964年提出了堆排序,罗伯特·弗洛伊德在同年的工作则确立了高效的自底向上建堆方法。鲁道夫·拜耳于1972年提出对称二叉 B 树,列奥尼达斯·吉巴斯和罗伯特·塞奇威克于1978年发展出红黑树的表述形式。丹尼尔·斯莱特和罗伯特·塔扬于1985年提出伸展树,强调摊还分析,而非严格的平衡条件。

处理器速度与内存访问开销之间不断扩大的差距,也影响了二叉树的应用场景。对于存储系统,B树将多个键和子节点组织在同一个节点中,与每个节点只存放一个键的二叉查找树相比,可以减少页面访问次数。B 树由鲁道夫·拜耳和爱德华·麦克雷特于1970年提出,后来在数据库索引和文件组织中发挥了重要作用。它们的作用表明,当沿树移动的每一步都可能需要访问磁盘或页面时,仅有对数级的树高上界并不足够。

现代实现需要考虑所有权、迭代器行为和并发计算等问题。在顺序执行的程序中,旋转只是一个简单的局部操作;但如果没有围绕该操作设计同步机制,另一个线程就可能看到不一致的链接。删除节点还会引出内存回收问题:另一个读取线程可能仍持有对已从树中移除的节点的引用。垃圾回收、锁和专门的内存回收方案,分别解决这一问题的不同方面。

测试与验证关注的是不变量,而非外观。查找树必须满足全局的键值范围约束;堆必须同时满足形状约束和父子节点间的次序约束;增广树则必须在每次更新后保持汇总信息正确。一棵树在图中看起来可能很平衡,却仍可能包含位置错误的后代节点;一次局部正确的旋转,也可能留下未更新的父节点引用或子树大小信息。这些实现中必须履行的要求说明,二叉树在数学上虽然简单,但要在生产软件中维护它们,仍需格外审慎。