树的革命——两个苏联数学家，如何让计算机学会保持平衡？

历史跨度：1857—1978年

本章主角：Arthur Cayley、Georgy Adelson-Velsky、Evgenii Landis、Rudolf Bayer、Edward McCreight、Robert Sedgewick

这一章，我们将经历三场革命：

1857年，数学家开始系统研究抽象的树。

1962年，两位苏联数学家设计出一种能够自动恢复平衡的搜索树。

1970年，两位研究人员发现：当数据需要存放在磁盘上时，树还必须改变自己的形状。

最终，这些研究将影响数据库、文件系统和现代软件中的有序数据结构。

序幕：一棵树，为什么会杀死一台计算机？

故事从一个简单的任务开始。

假设你是一名1960年代的计算机工程师。

你的公司需要管理100万份客户记录，每份记录都有唯一编号。

客户记录不断增加。

系统必须快速完成三个操作：

• 查询指定编号的客户。
• 添加新客户。
• 删除已经注销的客户。

你已经学过数组、链表和哈希表。

但现在，老板又提出一个要求：

除了查询某个编号，还要随时找出编号在50000到80000之间的全部客户。

这就有意思了。

哈希表虽然能快速查询具体编号，却无法直接提供有序区间。

如果把数据放在排序数组里，查询可以使用二分查找，但在中间插入新记录可能需要移动大量数据。

能不能设计一种数据结构，既保持有序，又方便动态插入？

于是，你画出了这样一张图：

              50
             /  \
           30    70
          / \    / \
         20 40  60 80

你制定了一条规则：

每个节点左侧的值小于自己，右侧的值大于自己。

现在要查找60。

首先比较50。

60比50大，向右。

到达70。

60比70小，向左。

找到60。

只经过三次比较！

你兴奋极了。

但是，几天之后，一场灾难发生了。

第一幕：1857年，树第一次进入重要的数学研究

我们先把时间倒回一个世纪以前。

1857年。

此时距离第一台现代电子计算机诞生，还有很长时间。

英国数学家 Arthur Cayley（阿瑟·凯莱，1821—1895） 正在研究一种特殊的数学结构。

Cayley 是19世纪最有影响力的数学家之一。

他年轻时就展现出突出的数学才能，但他的职业经历非常特别。

1849年，他成为一名执业律师。

此后的相当长一段时间，他一边从事法律工作，一边持续发表数学研究。

直到1863年，他才成为剑桥大学的萨德莱里安纯数学教授。

一个白天研究法律、业余时间研究数学的人，为什么会对树感兴趣？

1. 数学家眼中的树，并不需要树叶

想象我们有四个不同的符号：

A、B、C、D。

它们可以形成很多不同的连接关系。

例如：

    A
   / \
  B   C
       \
        D

也可以是：

    A
    |
    B
    |
    C
    |
    D

或者：

       A
     / | \
    B  C  D

这些结构外观不同，但都具有一个共同特征：

从一个节点到另一个节点，沿着连接关系可以找到路径，而且不存在环。

更严格地说，一个非空、连通、无环的无向图就是树。

数学家发现，研究这种结构能够帮助他们理解复杂表达式的组成方式。

1857年，Cayley 发表论文：

On the Theory of the Analytical Forms Called Trees

中文可以译为：

《论称为树的解析形式的理论》。

这篇论文研究了树状结构及其计数问题，是树的数学研究史上的重要文献。

但需要注意：树形思想和相关研究并非从 Cayley 一人开始，他的贡献在于对这类结构进行了重要的系统化数学研究。^{XXVIII. On the theory of the analytical forms called trees : The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science: Vol 13, No 85 · 242 [203 203. ON THE THEORY OF THE ANALYTICAL FORM}

一个有趣的数学问题

如果只有三个节点，能够形成多少种不同的树？

问题看起来很简单，但随着节点数量增加，不同连接方式的数量会迅速膨胀。

后来，Cayley 的名字与一个著名的公式联系起来：

对于 $n$ 个带有不同标签的顶点，能够构成的不同无向树的数量为：

$$\boxed{n^{n-2}}$$

这就是著名的 Cayley 公式。

例如，四个不同编号的节点，可以形成：

$$4^{4-2}=16$$

棵不同的标号树。

要注意，这里计数的是无向标号树，不是我们稍后要使用的二叉搜索树。

这两者属于同一类数学结构的不同研究方向。

为什么这段历史重要？

因为计算机后来需要解决的很多问题，都是把复杂信息组织为层次关系。

例如：

公司
├── 研发部
│   ├── 软件组
│   └── 硬件组
├── 财务部
└── 市场部

或者：

文件系统
├── Documents
│   ├── report.pdf
│   └── notes.txt
└── Pictures
    ├── photo1.jpg
    └── photo2.jpg

在这些结构中，树可以自然表达父子关系。

不过，我们今天要讨论的搜索树，又多了一条非常重要的规则：

节点之间不仅有层次关系，还有大小顺序。

这使得树从一种表示关系的结构，变成了一种高效的数据检索工具。

第二幕：二叉搜索树诞生之后，为什么很快暴露了致命弱点？

我们先不急着进入1962年。

假设你重新回到故事开头，正在设计一棵二叉搜索树。

你决定使用下面的规则：

• 比当前节点小的数字放左边。
• 比当前节点大的数字放右边。
• 每个节点最多有两个孩子。

这就是二叉搜索树，Binary Search Tree，简称 BST。

现在，我们依次插入：

50、30、70、20、40、60、80

得到：

              50
             /  \
           30    70
          / \    / \
         20 40  60 80

树看起来非常漂亮。

如果要寻找80：

50 → 70 → 80

只需要三次比较。

问题是：它为什么这么快？

因为在理想情况下，每次比较都能把搜索范围缩小到某个子树。

如果树足够平衡，节点数量增加一倍，树的高度通常只增加一层左右。

于是查找复杂度接近：

$$O(\log n)$$

100万个节点，理想平衡情况下，查找路径通常只有20层左右。

但是，这个结论藏着一个危险的前提。

树必须足够平衡。

灾难发生了

某天，客户资料按照编号从小到大导入：

10、20、30、40、50、60、70

你没有改变任何代码。

依然采用二叉搜索树的插入规则。

结果变成：

10
  \
   20
     \
      30
        \
         40
           \
            50
              \
               60
                 \
                  70

这还是一棵合法的二叉搜索树。

但是，它已经失去了最重要的优势。

如果要寻找70，必须经过：

10 → 20 → 30 → 40 → 50 → 60 → 70

七次比较。

如果有100万个节点，而且都是这样插入的呢？

最坏情况下，需要检查100万个节点。

复杂度从：

$$O(\log n)$$

退化为：

$$\boxed{O(n)}$$

原本聪明的搜索树，竟然退化成了一条链表。

而且这不是偶然发生的故障。

只要使用普通 BST，某些合法的输入顺序就一定会造成这种退化。

思考实验：哪种输入最危险？

假设你有以下三组数据：

对于普通 BST，输入顺序会显著影响树的形状。

现在问题来了：

既然输入顺序不可控制，我们能不能让树自动纠正自己的形状？

这一次，故事的舞台转到了苏联。

第三幕：1962年，两位苏联数学家的突破

1962年。

此时计算机科学作为独立学科还非常年轻。

世界各国的计算机研究人员正在探索如何处理越来越复杂的数据。

在苏联，两位数学家研究了一个关键问题：

如果数据不断插入、删除，怎样组织数据才能保证高效检索？

这两个人分别是：

Georgy Maximovich Adelson-Velsky

以及

Evgenii Mikhailovich Landis

他们的名字，后来被永久写进数据结构的历史。

AVL 树，就是两人姓氏首字母的组合。

1962年的真实论文

论文题目：

An Algorithm for the Organization of Information

《一种信息组织算法》

原文发表于1962年的苏联学术文献，英文译文刊登于 Soviet Mathematics Doklady 第3卷。

这篇论文被广泛认为是第一种自平衡二叉搜索树的正式提出。^{An algorithm for the organization of information | NDLサーチ | 国立国会図書館 · AVL tree}

这里有一个很值得注意的历史细节。

我们知道他们发表了算法，也知道算法的数学性质。

但是，对于两位研究者究竟在哪一天、哪间办公室、通过怎样的私人谈话想到旋转操作，公开史料并不足以支持详细还原。

因此，下面我们采用思想重建的方式，尝试重新发现他们的算法。

这不是未经证实的历史对话，而是根据 AVL 论文中的技术思想设计的推导实验。

1. 一个简单却深刻的想法

假设我们有这样一棵树：

       30
      /
     20
    /
   10

如果任由它继续增长，就会越来越像链表。

我们能不能制定一个规则：

每个节点左边与右边的高度，不能差得太多？

于是，定义：

$$BF=h_{\text{left}}-h_{\text{right}}$$

这叫作平衡因子（Balance Factor）。

如果：

$$BF=0$$

说明左右一样高。

如果：

$$BF=1$$

说明左边高一层。

如果：

$$BF=-1$$

说明右边高一层。

AVL 树要求所有节点满足：

$$\boxed{|BF|\leq1}$$

也就是说：

任何节点的左右子树高度差，都不能超过1。

这个限制看起来很简单。

但它带来了一个非常重要的数学保证：

AVL 树的高度始终为：

$$O(\log n)$$

因此，查找、插入和删除都可以保证最坏情况下的 $O(\log n)$ 时间复杂度。

这里要区分两个概念：

普通 BST 在理想条件下也能达到 $O(\log n)$。

而 AVL 的突破是：

它不依赖幸运的输入顺序，而是通过维护规则，保证树不会严重退化。

第四幕：一场不可思议的旋转——让树重新站起来

我们现在面临一个技术难题。

这棵树：

       30
      /
     20
    /
   10

已经不平衡了。

节点30的左子树高度比右子树高2。

按照 AVL 规则，这是不允许的。

那么应该怎么办？

最简单的想法是：

重新创建一棵树，把节点全部排列好。

当然可以。

但是，如果树中有100万个节点，只为了插入一个元素，就重新整理整棵树，成本显然无法接受。

两位数学家的方法更巧妙：

只修改局部几个节点之间的连接关系，就能恢复平衡。

这个操作叫作：

Rotation，旋转。

实验一：右旋如何挽救一棵失衡的树？

旋转前：

       30
      /
     20
    /
   10

现在，以30为中心执行一次右旋：

       20
      /  \
     10   30

注意，30并没有被删除。

10也没有移动到错误的位置。

只是三者的父子关系发生了变化。

而且最重要的是：

二叉搜索树的大小顺序完全没有改变。

旋转前，中序遍历得到：

10、20、30

旋转后，中序遍历还是：

10、20、30

这就是旋转操作真正聪明的地方。

它改变了树的形状，却没有改变数据的有序关系。

Python 实现右旋

def rotate_right(y):
    x = y.left
    t2 = x.right

    # 执行旋转
    x.right = y
    y.left = t2

    # 真实 AVL 实现还需要更新节点高度
    update_height(y)
    update_height(x)

    return x

其中 update_height 是维护节点高度的辅助函数。

我们暂时不展开完整的 AVL 类，而是先理解指针变化。

旋转前：

         y
        /
       x
        \
         T2

旋转后：

        x
         \
          y
         /
        T2

注意，子树 T2 必须重新挂在 y 的左边。

这一步非常关键。

否则，就会破坏 BST 的大小关系，或者丢失一部分节点。

为什么旋转如此高效？

因为一次单旋转只修改有限个指针，并更新少量节点信息。

它的操作本身是：

$$\boxed{O(1)}$$

不过，插入或删除后，算法还需要沿路径检查平衡状态，因此完整 AVL 更新操作的最坏复杂度仍是 $O(\log n)$。

特别值得记住的是：

AVL 插入时通常只需要一次单旋或双旋，就可以恢复整棵树的平衡；删除则可能需要沿祖先路径进行多次调整。

这也是 AVL 树算法实现中一个非常有意思的差别。

2. 更复杂的情况：为什么有时一次旋转还不够？

现在插入顺序变成：

30、10、20

得到：

       30
      /
     10
       \
        20

这棵树失衡了。

但如果直接对30右旋：

      10
        \
         30
        /
       20

依然不平衡。

为什么？

因为失衡路径发生了转折。

这就是 AVL 中的 LR 情况：

Left-Right。

解决方法需要两步。

第一步，对10左旋：

       30
      /
     20
    /
   10

第二步，对30右旋：

       20
      /  \
     10   30

树终于恢复平衡。

因此，AVL 的四种经典情况是：

这里的 LL、RR 等名称描述的是导致失衡的路径形态，而非所有情况下都必须机械地执行固定步骤；实际实现会依据子节点平衡因子处理相应情况。

一个小实验

假设插入：

10、30、20

你能预测是什么失衡类型吗？

先从10向右走到30。

再从30向左走到20。

所以属于：

RL（Right-Left）

修复过程是先对30右旋，再对10左旋。

最终得到：

       20
      /  \
     10   30

现在，你已经掌握了 AVL 插入算法最核心的思想。

第五幕：1962年，另一个改变计算机世界的事件正在发生

就在 AVL 树论文发表的同一年，计算机硬件也发生着重要变化。

1962年10月，IBM 推出了 IBM 1311 磁盘存储设备。

它采用可更换的磁盘组。

每个磁盘组能够存储约200万个字符。

放在今天，这点容量可能连一张照片都装不下。

但在当时，磁盘设备让计算机能够管理远大于主存容量的数据集合。

与磁带相比，磁盘可以相对直接地访问不同位置的数据。

不过，这并不意味着磁盘访问速度与内存相同。

磁头移动和等待盘片旋转都需要时间。

于是，一个新问题出现了。

假设一个数据库拥有100万条记录。

这些记录无法全部放进内存。

你需要把索引存储在磁盘上。

AVL 树虽然保证：

$$O(\log n)$$

但是，查询路径上的节点可能分散在不同磁盘位置。

如果每向下一层都要读取一个新的磁盘块，查询成本就会很高。

对于100万条数据，即使AVL 树仅有约20层，一次查找仍可能需要访问许多磁盘页。

而机械磁盘的访问成本，远远高于内存中的几次比较。

这时，一个新的思想开始变得非常重要：

我们不应该只计算比较次数，还必须计算磁盘访问次数。

这就是接下来 B 树故事的真正背景。

第六幕：1970年，两位研究人员决定让一棵树变得非常宽

1970年，美国。

在 Boeing Scientific Research Laboratories（波音科学研究实验室），两位研究人员正在研究大型有序索引。

他们分别是：

Rudolf Bayer

以及

Edward M. McCreight

他们面对的问题，与1962年的 AVL 树研究有相似之处：

如何在数据不断插入和删除时，仍然保持快速检索？

但是，他们的重点发生了变化。

AVL 树主要考虑适合内存访问的树形结构。

而 Bayer 和 McCreight 要处理的是：

索引大到无法全部放进主存，必须存储在磁盘或磁鼓等较慢的外部存储设备上。

1970年7月，他们形成了一份研究报告。

同年，相关论文出现在 SIGFIDET Workshop。

1972年，论文正式发表于 Acta Informatica：

Organization and Maintenance of Large Ordered Indexes

《大型有序索引的组织与维护》。^{dblp: Organization and Maintenance of Large Ordered Indexes. · dblp: Organization and Maintenance of Large Ordered Indices.}

这篇论文提出的结构，后来成为数据库技术的重要基础之一。

它就是：

B-Tree

B 树。

一个有趣的问题：B 到底是什么意思？

你可能以为：

B 就是 Balanced，平衡。

但历史并没有这么明确。

关于 B 的含义，人们提出过多种解释，包括 Balanced、Bayer、Boeing、Broad 等。

美国国家标准与技术研究院 NIST 的算法数据结构词典指出，作者并没有明确说明 B 的确切来源。

因此，不能简单地断言 B 一定代表 Balanced。^B-tree

这个细节很有意思。

一种后来影响无数数据库系统的数据结构，名字中最重要的字母，反而没有一个公认的确定解释。

第七幕：为什么磁盘上的树不能太高？

现在，让我们扮演 Bayer 和 McCreight。

假设一棵二叉搜索树的每个节点只能存放一个键。

              50
             /  \
           30    70
          / \    / \
         20 40  60 80

每访问一层，就可能需要读取一个磁盘页。

有没有更好的办法？

我们换一种思路。

既然读取一个磁盘页需要付出较大的固定成本，为什么不在每个页中存放多个键？

例如：

           [30 | 60]
          /    |    \
     [10 20] [40 50] [70 80]

注意，这已经不是二叉树了。

根节点存放两个键：

30和60。

于是可以划分出三个搜索范围：

• 小于30。
• 大于30且小于60。
• 大于60。

现在查找70。

只需要先读取根节点：

[30 | 60]

发现70大于60。

然后读取右侧子节点：

[70 | 80]

找到了！

仅经过两层。

这就是 B 树的重要思想：

让一个节点容纳多个键，从而大幅减少树的高度。

1. 为什么节点变宽会这么有效？

假设每个内部节点平均能够连接100个子节点。

那么：

第一层：

$$100$$

第二层：

$$100^2=10,000$$

第三层：

$$100^3=1,000,000$$

也就是说，少数几层就有能力组织非常庞大的数据集合。

当然，真正的 B 树节点还必须满足键数范围、子节点数以及叶节点深度等约束。

而且磁盘页能存放多少键，取决于页大小、键大小、指针大小等因素。

但整体思路十分清楚：

二叉树每层最多向两个方向分支。

B 树可以每层向几十甚至上百个方向分支。

结果就是：

B 树用更宽的节点，换取更矮的高度。

2. 1972年论文里最惊人的数据

Bayer 和 McCreight 并没有停留在理论分析。

他们还做了实际实验。

论文记载，研究人员在 IBM 360/44 计算机与 IBM 2311 磁盘设备上，测试了规模达到10万个键的索引。

其中，15000个键的索引能够维持平均每秒约9次事务操作；更大规模实验的性能也被记录在论文中。

这里的事务是论文中实验环境下的具体索引操作，不能直接等同于现代数据库系统的 TPS 指标。^{Organization and maintenance of large ordered indices}

对今天的程序员来说，每秒9次操作似乎非常慢。

但站在1970年的硬件条件下，这些实验的重要性在于：

研究者不仅提出了数学结构，而且证明了它能够真正用于磁盘上的大型有序索引。

更重要的是，B 树支持动态增长和收缩，不需要每次增加数据都重建整个索引。

第八幕：B 树为什么可以一边增长，一边保持平衡？

还记得 AVL 树吗？

AVL 通过旋转保持平衡。

B 树则采用另一种非常有趣的方法：

节点分裂（Split）与节点合并（Merge）。

我们使用一种简单的 2-3 树来演示。

2-3 树可以视为 B 树家族中的一种特殊形式。

每个节点最多存放两个键。

假设我们依次插入：

10、20、30

首先：

[10]

插入20：

[10 | 20]

接着插入30。

如果暂时放在一起：

[10 | 20 | 30]

节点超出了容量限制。

怎么办？

这时进行分裂。

把中间的20提升为父节点。

        [20]
       /    \
     [10]  [30]

一个节点变成了三个部分：

左子节点、父节点、右子节点。

现在继续插入40和50。

最终可能得到：

          [20 | 40]
         /    |    \
       [10] [30]  [50]

所有叶节点依然位于同一深度。

这就是 B 树重要的平衡机制。

它不像 AVL 那样依赖旋转。

而是通过节点分裂、借位和合并，维持节点容量以及统一的叶节点深度。

一个关键差别

AVL 树关注：

左右子树的高度差不能超过1。

B 树关注：

每个节点应满足规定的键数和孩子数量范围，而且所有叶节点处于同一深度。

两者都能够保证对数级别的树高。

但是，它们服务的存储环境和工程目标并不完全相同。

第九幕：1978年，树开始穿上红色和黑色的衣服

1970年代后期。

故事来到美国加利福尼亚州。

Xerox PARC（施乐帕洛阿尔托研究中心）正在进行大量计算机技术研究。

这个研究机构在个人计算机、图形用户界面、网络等领域留下了非常重要的历史。

这一时期，两位研究者开始研究另一个问题。

能不能让自平衡搜索树的实现更加统一、简洁？

他们是：

Leonidas Guibas

以及

Robert Sedgewick

1978年，两人发表论文：

A Dichromatic Framework for Balanced Trees

《平衡树的双色框架》。^{A dichromatic framework for balanced trees}

这篇论文研究了如何通过颜色信息统一表示和分析多种平衡树。

由此发展出的红黑树，后来成为计算机科学中最著名的平衡搜索树之一。

1. 为什么需要红色和黑色？

普通 BST 只保存：

value
left
right

而红黑树还会为节点保存一个颜色：

color = RED or BLACK

颜色不是为了好看。

它是一种非常紧凑的平衡信息。

红黑树通过若干约束，保证任何一条根到叶子的路径不会比另一条路径长得过于夸张。

经典红黑树包括这些性质：

1. 节点为红色或黑色。
2. 根节点为黑色。
3. 所有空叶子（NIL）视为黑色。
4. 红色节点的孩子必须为黑色。
5. 从任一节点到其后代 NIL 叶子的所有路径，黑色节点数量相同。

这些约束保证红黑树的高度不会超过：

$$2\log_2(n+1)$$

其中 $n$ 是内部节点数。

这意味着红黑树虽然没有 AVL 那么严格平衡，但仍然可以保证：

$$O(\log n)$$

的最坏情况查找时间。

那么，为什么偏偏是红色和黑色？

这个问题竟然有一段非常生动的真实历史。

Robert Sedgewick 在自己的研究回忆中谈到，研究人员当时在 Xerox PARC 使用白板绘制树形结构，而颜色有助于他们交流和分析。

后来，他们还能够使用实验性的彩色激光打印设备输出树的图形。

所以红黑树的颜色不仅是一种数学标记，也与当时研究人员的实际交流方式有关。^{Research - Robert Sedgewick}

这和那些经过后人加工的发明传奇不同。

因为它来自研究者本人对当年工作的回顾。

第十幕：AVL 与红黑树，谁更优秀？

这可能是你学完本章之后最感兴趣的问题。

为什么已经有 AVL 树，还要设计红黑树？

答案并不是谁彻底击败了谁。

而是因为不同系统有不同需求。

AVL 树

优点：

• 平衡条件比较严格。
• 树高通常更低。
• 在某些以查询为主的场景中具有优势。

缺点：

• 对平衡的维护要求严格。
• 删除操作可能触发沿路径的多次调整。

红黑树

优点：

• 平衡条件相对宽松。
• 更新操作时有良好的最坏情况复杂度保证。
• 在通用有序容器中应用广泛。

缺点：

• 树可能比 AVL 更高。
• 需要维护颜色和对应的修复规则。

B 树

优点：

• 节点能够容纳多个键。
• 高分支因子可以减少树高。
• 特别适合磁盘、页面式存储以及外存索引。

缺点：

• 节点分裂、合并和页管理更加复杂。
• 对于纯内存中的小规模数据，未必总是最合适。

三种树的对比

请注意，B 树的 $O(\log n)$ 只是从元素数量的渐近复杂度进行表达。

在外存环境中，我们更关注的是页访问次数，其数量通常与树高相关：

$$O(\log_B n)$$

这里的 $B$ 代表与节点分支因子有关的参数。

第十一幕：今天，我们还生活在这些树构建的世界里

故事走到这里，时间已经从1857年来到了1978年。

但树的历史并没有停止。

它们逐渐进入操作系统、数据库和编程语言的基础设施之中。

1. C++ 的有序容器

例如：

#include <map>
#include <string>

std::map<int, std::string> users;

users[1001] = "Alice";
users[1002] = "Bob";
users[1003] = "Charlie";

std::map 要求键按照比较关系有序组织。

标准规定了相关操作的对数复杂度保证，但并没有强制使用哪一种树。

许多主流标准库实现选择了红黑树。

因此，哪怕你从来没有亲自实现过红黑树，也很可能早就在使用它。

2. 数据库索引

假设数据库里有1000万条记录。

你执行：

SELECT *
FROM users
WHERE user_id BETWEEN 10000 AND 20000;

如果数据没有合适的索引，数据库可能需要扫描大量记录。

如果有合适的 B+ 树索引，就可以先定位起始键，再按索引顺序进行范围扫描。

B+ 树是 B 树家族中的重要变体。

它的典型设计是让叶节点承担全部记录键的存放，并便于顺序访问。

MySQL InnoDB 等数据库引擎便广泛使用 B+ 树索引。

这与上一章哈希表形成了鲜明的对照：

哈希表擅长精确查询；有序树索引不仅能定位具体键，还能高效支持范围查询。

当然，实际数据库性能还受到查询优化器、缓存、磁盘布局和记录选择性等因素影响。

第十二幕：一场跨越120年的接力

现在，让我们把四位主要研究方向放在同一条时间线上。

这里还有一个非常重要的历史关系。

这些树不是简单的替代关系。

AVL 树并没有因为红黑树出现而失去意义。

红黑树也没有取代 B 树。

B 树更不是因为 AVL 树不好用才被发明出来。

它们分别优化了不同的约束：

• AVL：严格控制树高。
• 红黑树：在动态更新与平衡约束之间寻求更灵活的折中。
• B 树：减少访问外部存储时需要读取的节点数量。

你会发现，数据结构的发展并不总是为了降低大 O 复杂度。

有时候，两个算法的时间复杂度完全相同，但它们解决的实际性能问题却截然不同。

这可能是本章最值得记住的一点。

终章挑战：假如你是1970年的数据库工程师

现在，我们安排一次真正的工程决策。

你有一台1970年代的计算机。

需要管理500万条记录。

机器具有以下特点：

• 内存容量有限。
• 数据主要保存在机械磁盘上。
• 每次磁盘寻道成本明显高于内存比较。
• 需要经常执行范围查询。
• 数据会不断插入和删除。

你可以选择三种结构：

方案A：AVL 树

严格控制树高，每个节点最多两个孩子。

方案B：红黑树

使用颜色保持近似平衡，维护动态有序数据。

方案C：B 树

每个磁盘页保存多个键，一个节点拥有大量孩子。

你会选哪一个？

如果你已经理解本章，你应该意识到：

答案不仅取决于数学复杂度，还取决于数据所处的硬件环境。

在这类典型的磁盘索引需求下，B 树家族通常更有优势。

但换成全部数据常驻内存、需要频繁更新的程序，答案就可能不同。

尾声：真正伟大的算法，懂得适应自己的时代

1857年，Arthur Cayley 研究树的数学性质时，现代计算机尚未诞生。

1962年，Adelson-Velsky 和 Landis 让搜索树能够在动态变化中自动恢复平衡。

1970年，Bayer 和 McCreight 认识到，外部存储的访问成本会改变数据结构的设计方向。

1978年，Guibas 和 Sedgewick 又通过红黑两色，展示了另一种优雅的平衡机制。

这是一条持续了一百多年的发展线索。

每一代研究者都站在前人的成果之上，又遇到了前人没有解决的新问题。

而我们从中学到的不只是四种树。

还有计算机科学中一条非常深刻的原则：

好的数据结构，并不是拥有最漂亮的数学形式，而是能够针对实际问题中的代价，作出最合适的取舍。

本章最应该记住的六件事

1. 树是一种具有层次关系的结构，在图论中，连通无环是其核心特征。
2. 二叉搜索树能够维护有序关系，但普通 BST 可能退化成链表。
3. AVL 树通过限制左右子树高度差，保证最坏情况下的对数时间复杂度。
4. 旋转可以改变树的形状，同时保持二叉搜索树的中序顺序。
5. B 树通过增加节点分支数量，降低外存索引的高度与页面访问成本。
6. 红黑树使用颜色约束维持近似平衡，是另一条重要的自平衡搜索树路线。

本章历史资料

• ^{https://alum.mit.edu/www/tchow/misc/cayley.pdf · https://alum.mit.edu/www/tchow/misc/cayley.pdf?utm_source=chatgpt.com}
• ^{https://xlinux.nist.gov/dads/HTML/avltree.html · https://xlinux.nist.gov/dads/HTML/avltree.html?utm_source=chatgpt.com}
• ^{https://rtheunissen.github.io/bst/docs/references/1972_bayer_mccreight.pdf · https://rtheunissen.github.io/bst/docs/references/1972_bayer_mccreight.pdf?utm_source=chatgpt.com}
• ^{https://sedgewick.io/wp-content/themes/sedgewick/papers/1978Dichromatic.pdf · https://sedgewick.io/wp-content/themes/sedgewick/papers/1978Dichromatic.pdf?utm_source=chatgpt.com}
• ^{https://sedgewick.io/research/ · https://sedgewick.io/research/?utm_source=chatgpt.com}

下一章预告

第六章：七座桥与一位天才数学家——图论是怎样诞生的？

1736年。

普鲁士，柯尼斯堡。

这座城市被河流分割成几个区域，七座桥连接着不同的陆地。

城里流传着一个问题：

能不能从某个地方出发，走遍全部七座桥，每座桥恰好走一次？

无数人尝试用不同路线寻找答案。

但一位名叫 Leonhard Euler 的数学家，却采用了一种完全不同的方法。

他不再关注街道有多长、桥梁是什么形状，甚至不关心城市的实际地图。

他只保留了两种东西：

地点，以及地点之间的连接关系。

这个看似简单的抽象，将成为现代图论的重要起点。

下一章，我们将从欧拉1736年的真实论文出发，走进图论、深度优先搜索、广度优先搜索，以及 Dijkstra 最短路径算法的发展史。

这一次，我们将看到：数学家怎样证明一条路根本不可能存在，而不是继续浪费时间寻找它。