卷一：基础理论与核心数据结构
第一章：算法的度量衡 —— 时空复杂度分析与Python性能陷阱
在踏上算法探索的征途之前，我们必须先锻造好我们的度量工具。没有度量，就无法比较；没有比较，就无法选择；没有选择，就无法优化。在算法的世界里，这个度量衡就是“时空复杂度”。
1.1 为何需要复杂度分析？—— “跑一下代码看看”的局限性
一个初学者在比较两个算法（例如，两种不同的排序方法）的优劣时，最直观的想法可能是：“我把这两个算法都实现出来，然后用同一个大列表去跑一下，看看哪个花的时间短。”
这是一种基于经验的测试方法，它在某些情况下有用，但作为一种严格的评判标准，它存在着致命的缺陷：
环境依赖性太强:
硬件差异: 同样的代码，在Intel i9处理器上和在树莓派上运行，其绝对时间天差地别。我们无法得出一个脱离硬件的普适性结论。
软件环境差异: 操作系统、Python解释器的版本、后台运行的其他程序，都会干扰计时的准确性。你这次测量的结果，下次可能就无法复现。
数据规模的迷惑性:
假设算法A在处理100个元素时耗时0.01秒，算法B耗时0.05秒。我们能说算法A一定优于算法B吗？未必。
可能算法A的复杂度是二次方级别（O(n²)），而算法B是线性对数级别（O(n log n)）。当数据规模扩大到100万个元素时，算法A可能需要几个小时，而算法B可能只需要几秒钟。在小数据规模下的“优势”，在大数据面前会变成灾难性的“劣势”。
数据状态的偶然性:
某些算法的性能与其处理的数据的初始状态密切相关。例如，一个简单的“快速排序”算法，在处理一个已经几乎排好序的列表时，其性能会急剧恶化。如果你碰巧用了一个这样的测试用例，你可能会错误地认为快速排序是一个很差的VBA算法。
因此，我们需要一种与具体硬件、环境无关，能够描述算法效率与数据规模之间增长关系的理论工具。这个工具，就是复杂度分析。它不关心算法执行的绝对时间（例如“跑了0.2秒”），而是关心算法执行时间（或占用空间）的增长趋势。
1.2 时间复杂度：代码执行时间的增长趋势
时间复杂度，全称为“渐进时间复杂度”（Asymptotic Time Complexity），它描述的是当输入数据规模n趋向于无穷大时，算法执行所需时间步数的增长级别。我们用**大O表示法（Big O Notation）**来表示。
让我们从一个最简单的例子开始，理解大O是如何推导出来的。
代码示例：计算列表中所有元素的和
def sum_list(data_list):
"""计算一个列表中所有数字的和。"""
total = 0 # 执行1次：赋值操作
for num in data_list: # 执行n次：其中n是data_list的长度
total += num # 执行n次：加法和赋值操作
return total # 执行1次：返回操作
推导过程:
数出基本操作次数:
total = 0 执行了1次。
for循环本身，连同其内部的total += num，对于一个长度为n的列表，总共会执行n次。我们粗略地将循环的每次迭代记为2个操作步（一次迭代判断，一次加法赋值）。
return total 执行了1次。
所以，总的操作步数 T(n) = 1 + 2*n + 1 = 2n + 2。T(n)代表了代码执行的总时间步数与输入规模n的函数关系。
已关注增长趋势，忽略常数、低阶项和系数:
忽略加法常数: 当n变得非常大时（比如10亿），2n + 2中的那个+2变得微不足道，完全可以忽略。公式简化为 T(n) ≈ 2n。
忽略乘法系数: 我们关心的是执行时间的增长“级别”，而不是精确的倍数关系。2n的增长趋势和n的增长趋势是同一种类型——线性增长。当n翻倍时，执行时间也大致翻倍。因此，我们把这个系数2也忽略掉。
最终，我们得到这个算法时间复杂度的增长级别是 O(n)。
大O表示法的核心：它抓住了一个函数中“最主要”的部分，也就是当n趋于无穷时，增长最快的那个项，并忽略掉所有“修饰性”的常数和系数。
1.2.1 常见的时间复杂度量级（从优到劣）
理解并能识别出这些常见的复杂度量级，是算法学习的第一步。
1. O(1) – 常数时间复杂度 (Constant Time)
这代表算法的执行时间不随输入数据规模n的变化而变化。无论n是10还是10亿，执行时间都保持在一个常数水平。
def get_first_element(data_list):
"""获取列表的第一个元素。"""
if not data_list: # 执行1次：检查列表是否为空
return None # 在列表为空时执行1次：返回None
return data_list[0] # 在列表不为空时执行1次：通过索引获取元素
解释: 无论列表data_list有多长，这个函数都只执行一次索引操作data_list[0]。它的执行时间是一个固定的、与n无关的常数。Python中字典（dict）和集合（set）的查找、插入、删除操作，在平均情况下的时间复杂度也是O(1)，这是哈希表数据结构的威力所在。
2. O(log n) – 对数时间复杂度 (Logarithmic Time)
这是非常优秀的一种复杂度。当n增大时，执行时间步数增长得非常缓慢。典型的O(log n)算法，每一步处理都会将待解决问题的规模缩减一个量级（例如，减半）。
经典案例：二分查找
def binary_search(sorted_list, target):
"""在一个排好序的列表中使用二分查找来寻找目标值。"""
low = 0 # 执行1次：初始化low指针
high = len(sorted_list) - 1 # 执行1次：初始化high指针
while low <= high: # 循环的次数是关键，我们称之为k次
mid = (low + high) // 2 # 执行k次：计算中间位置
guess = sorted_list[mid] # 执行k次：获取中间值
if guess == target: # 执行k次：比较操作
return mid # 最多执行1次：找到目标，返回索引
if guess > target: # 执行k次：比较操作
high = mid - 1 # 执行k次：缩小查找范围的上界
else: # 执行k次：比较操作
low = mid + 1 # 执行k次：缩小查找范围的下界
return None # 最多执行1次：未找到目标，返回None
解释: 为什么是O(log n)？假设列表长度为n。
第1次查找后，剩余的查找范围是 n/2。
第2次查找后，剩余的查找范围是 n/4。
第k次查找后，剩余的查找范围是 n / 2^k。
当查找结束时，剩余范围是1，即 n / 2^k = 1。
通过数学变换，得到 n = 2^k，进而得到 k = log₂(n)。
因此，循环的执行次数k与n的对数成正比。底数是2还是10在Big O表示法中被忽略，统一记为O(log n)。
3. O(n) – 线性时间复杂度 (Linear Time)
这是非常常见的一种复杂度，意味着算法的执行时间与输入规模n成正比。我们最开始的sum_list例子就是O(n)。
代码示例：线性查找
def linear_search(data_list, target):
"""在列表中进行线性查找。"""
for i in range(len(data_list)): # 循环会执行n次
if data_list[i] == target: # 比较操作会执行n次（最坏情况下）
return i # 如果找到，则提前返回
return None # 如果循环结束仍未找到，返回None
解释: 在最坏的情况下（目标元素在列表末尾或根本不存在），这个算法需要完整地遍历整个列表，检查n个元素。
4. O(n log n) – 线性对数时间复杂度 (Log-Linear Time)
这是算法领域的一个“黄金标准”，尤其是在排序领域。许多最高效的、基于比较的排序算法（如归并排序、快速排序的平均情况）都具有这个复杂度。它比O(n^2)快得多，但比O(n)慢。
直观理解: 想象一下，你有一个任务，需要对n个元素中的每一个都执行一次O(log n)的操作。那么总的复杂度就是 n * O(log n)，即 O(n log n)。
归并排序的例子: 归并排序会递归地将列表分成两半（这个过程的深度是log n层），在每一层，它都需要对总共n个元素进行合并操作。因此，总复杂度是 O(n log n)。我们将在排序章节详细实现它。
5. O(n²) – 平方时间复杂度 (Quadratic Time)
当n较大时，这种复杂度的算法会变得非常慢。它通常涉及到对数据集的嵌套循环。
代码示例：找出列表中的重复元素（朴素方法）
def find_duplicates_naive(data_list):
"""使用嵌套循环来查找列表中的重复元素。"""
duplicates = [] # 执行1次：初始化结果列表
n = len(data_list) # 执行1次：获取列表长度
for i in range(n): # 外层循环执行n次
for j in range(i + 1, n): # 内层循环执行的次数与i相关
# 当i=0时，内层循环n-1次
# 当i=1时，内层循环n-2次
# ...
# 总次数约等于 (n-1)+(n-2)+...+1 = n*(n-1)/2 = 0.5n² - 0.5n
if data_list[i] == data_list[j]: # 比较操作
if data_list[i] not in duplicates: # 检查是否已记录
duplicates.append(data_list[i]) # 添加到结果列表
return duplicates # 返回结果
解释: 内层循环的执行总次数约为 n²/2。根据大O表示法，我们忽略系数1/2和低阶项-0.5n，得到时间复杂度为O(n²)。
6. O(2ⁿ) – 指数时间复杂度 (Exponential Time)
这是一种非常糟糕的复杂度，算法的执行时间会随着n的增加而爆炸式增长。这类算法通常涉及到对问题所有可能子集的蛮力搜索。
经典案例：斐波那契数列的朴素递归实现
def fibonacci_recursive(n):
"""使用朴素递归计算斐波那契数列的第n项。"""
if n <= 1: # 递归的基线条件
return n
# 关键问题在这里：每次调用都会产生两个新的递归调用
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
解释: 调用fibonacci_recursive(5)会触发fib(4)和fib(3)。fib(4)又会触发fib(3)和fib(2)。你会发现fib(3)被重复计算了。这种递归调用的总次数大致是2^n的量级，形成一个巨大的、充满重复计算的递归树。
7. O(n!) – 阶乘时间复杂度 (Factorial Time)
这是最差的一类复杂度，只在n非常非常小的情况下才可用。它通常出现在需要计算所有排列组合的问题中。
经典案例：旅行商问题（TSP）的蛮力解法
问题描述: 一个商人要访问n个城市，每个城市只访问一次，最后回到出发城市。如何找到最短的路线？
蛮力解法: 列出所有可能的访问顺序（排列），计算每条路线的总长度，然后找出最短的。
复杂度: n个城市的排列组合有 (n-1)! 种。这是一个O(n!)级别的算法。当城市数量达到20个时，计算量就已经是天文数字了。
1.3 空间复杂度：算法占用的额外内存
空间复杂度（Space Complexity）衡量的是算法在运行过程中，除了存储输入数据本身所占用的空间之外，还需要额外占用的内存空间与输入规模n之间的增长关系。
1. O(1) – 常数空间复杂度
算法所需的额外空间是一个固定的常数，不随n的变化而变化。
def reverse_list_in_place(data_list):
"""原地反转一个列表。"""
left = 0 # 需要1个变量空间
right = len(data_list) - 1 # 需要1个变量空间
while left < right:
# 下面的交换操作只在已有的列表空间内进行，没有创建新列表
temp = data_list[left] # 需要1个临时变量空间
data_list[left] = data_list[right]
data_list[right] = temp
left += 1
right -= 1
解释: 无论data_list有多长，我们都只需要left, right, temp这几个固定数量的变量。因此，额外空间是O(1)。这种不产生额外数据副本的算法被称为“原地算法”（In-place Algorithm）。
2. O(n) – 线性空间复杂度
算法所需的额外空间与输入规模n成正比。
def create_copy_and_reverse(data_list):
"""创建一个新的反转后的列表。"""
new_list = [None] * len(data_list) # 创建了一个和输入规模n一样大的新列表
n = len(data_list)
for i in range(n):
new_list[i] = data_list[n - 1 - i]
return new_list
解释: 我们创建了一个new_list，它的大小与data_list完全相同。如果data_list的长度是n，那么额外空间就是O(n)。
3. O(n²) – 平方空间复杂度
算法所需的额外空间与n的平方成正比。
代码示例：创建一个邻接矩阵来表示图
def create_adjacency_matrix(n, edges):
"""为n个顶点的图创建邻接矩阵。"""
# 创建一个 n x n 的二维列表，所有元素初始化为0
matrix = [[0] * n for _ in range(n)] # 这里分配了 n*n 的空间
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # 假设是无向图
return matrix
解释: 对于一个有n个顶点的图，邻接矩阵需要n x n的空间来存储任意两个顶点之间是否存在边。因此，空间复杂度是O(n²)。
1.4 最好、最坏与平均情况复杂度
同一个算法，在处理不同状态的输入数据时，其性能表现可能大相径庭。
最坏情况时间复杂度 (Worst-case): 算法在任何输入规模为n的数据上，运行时间步数的上界。这是我们最关心、最常讨论的，因为它提供了一个性能保证。无论输入数据多么“不友好”，算法的性能都不会比这个更差。
最好情况时间复杂度 (Best-case): 算法在最“理想”的输入数据上运行的时间复杂度。这个指标通常用处不大，因为它不具有代表性。
平均情况时间复杂度 (Average-case): 假设所有可能的输入数据以等概率出现，算法运行的期望时间复杂度。这个指标能很好地反映算法在现实中的平均表现，但其数学分析通常比最坏情况复杂得多。
以线性查找为例:
最坏情况: O(n)。目标元素在列表的最后一个位置，或者根本不存在。
最好情况: O(1)。目标元素恰好是列表的第一个。
平均情况: O(n)。平均来说，需要查找 n/2 次。根据大O表示法，忽略系数1/2，仍然是O(n)。
以快速排序为例:
最坏情况: O(n²)。当每次选择的“基准元”都是当前子数组的最大或最小值时发生，这常见于处理一个已排序的列表。
最好情况: O(n log n)。
平均情况: O(n log n)。实践证明，通过随机选择基准元等方法，可以极大概率地避免最坏情况的发生，使得快速排序在平均情况下表现极为出色。
1.5 必须警惕的Python性能陷阱
Python的语法简洁优美，但这种简洁有时会掩盖底层操作的真实成本。不了解这些，很容易写出表面优雅但性能低下的代码。
陷阱一：列表的 + 拼接与 append
# list_concatenation_vs_append.py
import time
n = 100000
# 使用 + 拼接
start_time = time.time()
result_plus = []
for i in range(n):
result_plus = result_plus + [i] # 每次拼接都会创建一个新的列表
end_time = time.time()
print(f"使用 '+' 拼接 {
n} 次耗时: {
end_time - start_time:.4f} 秒")
# 使用 append
start_time = time.time()
result_append = []
for i in range(n):
result_append.append(i) # append是原地修改，效率高得多
end_time = time.time()
print(f"使用 'append' {
n} 次耗时: {
end_time - start_time:.4f} 秒")
分析:
result = result + [i]: 看起来简单，但+操作符在Python列表中意味着创建一个全新的列表，将result的所有元素复制到新列表中，然后再把[i]的元素也复制过去。这个操作的成本与result的当前长度成正比。在循环中，这个操作的复杂度近似于 1 + 2 + 3 + ... + n，这是一个O(n²)的过程！
result.append(i): append方法是原地修改。Python的列表是动态数组，它会预分配一些额外空间。大多数情况下，append只是在末尾填入一个值，是O(1)操作。即使偶尔空间不足需要重新分配和复制整个数组，其“均摊时间复杂度”依然是O(1)。整个循环是O(n)。
陷阱二：in 操作符在列表和字典/集合中的天壤之别
# in_list_vs_in_dict.py
import time
n = 100000
data_list = list(range(n))
data_dict = {
i: True for i in range(n)} # 创建一个字典，键是0到n-1
target = n - 1 # 要查找的目标
# 在列表中查找
start_time = time.time()
is_in_list = target in data_list # 'in' 对于列表是线性扫描
end_time = time.time()
print(f"在 {
n} 个元素的列表中查找: {
'找到' if is_in_list else '未找到'}, 耗时: {
end_time - start_time:.6f} 秒")
# 在字典中查找
start_time = time.time()
is_in_dict = target in data_dict # 'in' 对于字典是哈希查找
end_time = time.time()
print(f"在 {
n} 个元素的字典中查找: {
'找到' if is_in_dict else '未找到'}, 耗时: {
end_time - start_time:.6f} 秒")
分析:
target in data_list: 为了判断target是否在列表中，Python必须从头到尾逐个检查元素，直到找到匹配项或遍历完整个列表。这是一个O(n)的线性查找。
target in data_dict: 字典的in操作利用了哈希表。它会直接计算target的哈希值，通过哈希值几乎可以立即定位到target应该在的位置，然后进行一次比较即可。这是一个平均O(1)的操作。
结论: 当你需要频繁地进行成员资格检查时，使用集合（set）或字典（dict）的键，其性能远超列表。
陷阱三：字符串的拼接
这与列表的+拼接陷阱非常相似。Python的字符串是**不可变（immutable）**的。
# string_concatenation.py
# 坏方法：使用 + 在循环中拼接
def bad_string_join(words):
result = ""
for word in words:
result += word + " " # 每次都会创建新字符串，O(n²)
return result
# 好方法：使用 join 方法
def good_string_join(words):
return " ".join(words) # join方法会先计算总长度，一次性构建字符串，O(n)
分析:
result += word: 因为字符串不可变，所以这行代码的背后是：创建一个新的、足够大的字符串，将result的旧内容复制过去，再将word的内容复制过去，然后让result变量指向这个全新的字符串。在循环中，这是一个O(n²)的灾难。
" ".join(words): join方法是专门为此优化的。它会先遍历一次words列表，计算出最终字符串所需的总长度，然后只分配一次内存，最后将所有单词复制到这个新空间中。这是一个高效的O(n)操作，其中n是所有单词的总长度。
第二章：线性数据结构 —— 序列、链条与栈队的艺术
在构建了坚固的复杂度分析基石之后，我们开始搭建算法大厦的第一层——线性数据结构。所谓“线性”，指的是数据元素之间存在着一对一的、线性的前后关系，就像一串珍珠项链，每个珍珠后面只跟着另一颗珍珠。这种结构虽然简单，却是构建更复杂数据结构和算法的基础。
2.1 数组与Python列表：看似简单，内有乾坤
数组（Array）是几乎所有编程语言都内置的最基本的数据结构。它是一块连续的内存空间，用于存储一系列相同类型的元素。
数组的核心特性:
连续内存: 这是数组最本质、最重要的特征。a[0], a[1], a[2]等元素在物理内存中是紧挨着存放的。
随机访问 (Random Access): 正因为内存连续，计算机可以通过一个简单的数学公式 address(a[i]) = base_address + i * element_size，在O(1)的常数时间内直接计算出任何一个索引i的元素的内存地址，并立即访问它。这是数组最大的优势。
Python中的list：动态数组的实现
Python的list类型，虽然用法上像一个可以存储任何类型、长度可变的“超级数组”，但其底层实现是一个动态数组（Dynamic Array）。它保留了传统数组“连续内存”和“随机访问”的核心优势，同时又巧妙地解决了传统数组长度固定的问题。
动态数组的内部机制:
预留空间: 当你创建一个list时，Python解释器并不会只分配你当前需要的空间。它会额外预留一些空间，以备未来的append操作。这被称为“超额分配”（Over-allocation）。
append操作: 当你append一个新元素时，如果预留空间足够，Python会直接在末尾的空闲位置放入新元素。这是一个O(1)的操作。
扩容 (Resizing): 如果预留空间用完了，append操作会触发一次“扩容”。这个过程包括：
a. 申请一块更大的新内存空间（通常是当前大小的1.5倍或2倍）。
b. 将旧数组中的所有元素，逐个复制到新的内存空间中。
c. 释放旧的内存空间。
d. 在新空间的末尾放入新元素。
这次扩容操作本身是O(n)的，其中n是列表的当前大小。但由于它不是每次append都发生，而是随着列表长度的增长，其发生的频率越来越低，因此，经过均摊（Amortized）分析，append操作的均摊时间复杂度依然是O(1)。
2.1.1 列表的基本操作复杂度分析
理解Python列表的底层实现，对于分析其各种操作的性能至关重要。
| 操作 | 例子 | 平均时间复杂度 | 最坏时间复杂度 | 解释 |
|---|---|---|---|---|
| 索引访问 | L[i] |
O(1) |
O(1) |
基于连续内存的地址计算，始终是常数时间。 |
| 索引赋值 | L[i] = v |
O(1) |
O(1) |
同上，直接定位并修改。 |
| 末尾追加 | L.append(v) |
O(1) |
O(n) |
均摊为O(1)。最坏情况发生在需要扩容时。 |
| 末尾弹出 | L.pop() |
O(1) |
O(1) |
只是移动内部的“size”指针，通常不涉及缩容，极快。 |
| 插入元素 | L.insert(i,v) |
O(n) |
O(n) |
在索引i处插入，需要将i之后的所有元素向右移动一位。 |
| 删除元素 | del L[i], L.pop(i) |
O(n) |
O(n) |
删除索引i的元素，需要将i之后的所有元素向左移动一位。 |
| 成员检查 | v in L |
O(n) |
O(n) |
线性扫描，从头到尾逐个比较。 |
| 切片 (读取) | L[i:j] |
O(k) |
O(k) |
k=j-i。需要创建新列表并复制k个元素。 |
| 切片 (删除) | del L[i:j] |
O(n-j) |
O(n-j) |
需要将被删除部分之后的所有元素向左移动。 |
| 列表拼接 | L1 + L2 |
O(m+n) |
O(m+n) |
创建新列表，并复制L1和L2的所有元素。m, n为长度。 |
代码示例：insert 和 del 的成本演示
# list_insertion_deletion_cost.py
import time
n = 100000
# 在列表头部插入
start_time = time.time()
l_head = []
for i in range(n):
l_head.insert(0, i) # 每次都在索引0处插入，每次都移动所有已有元素
end_time = time.time()
print(f"在列表头部插入 {
n} 个元素耗时: {
end_time - start_time:.4f} 秒") # 这是一个O(n²)的操作
# 在列表尾部插入 (使用 append)
start_time = time.time()
l_tail = []
for i in range(n):
l_tail.append(i) # 均摊 O(1)
end_time = time.time()
print(f"在列表尾部追加 {
n} 个元素耗时: {
end_time - start_time:.4f} 秒") # 这是一个O(n)的操作
# 从列表头部删除
l_to_delete = list(range(n))
start_time = time.time()
for _ in range(n):
l_to_delete.pop(0) # 每次都从索引0处删除，每次都移动所有剩余元素
end_time = time.time()
print(f"从列表头部删除 {
n} 个元素耗时: {
end_time - start_time:.4f} 秒") # 这是一个O(n²)的操作
这个实验的结果会非常清晰地告诉你：对Python列表的头部进行频繁的插入和删除，是极其低效的行为！ 这也是为什么我们需要队列（Queue）这种专门为头尾操作优化的数据结构。
2.2 链表：非连续内存的自由舞者
与数组将所有元素紧凑地存放在一块连续内存中不同，链表（Linked List）采取了一种完全不同的、更“自由”的存储策略。
链表的核心思想:
节点 (Node): 链表的基本组成单位是节点。每个节点至少包含两部分信息：
数据域 (Data): 存储元素本身的数据。
指针域 (Pointer/Next): 存储下一个节点的内存地址。
非连续存储: 链表的各个节点在内存中可以是任意分布的，它们不需要物理上相邻。
链接关系: 节点之间的逻辑顺序是通过指针域串联起来的。第一个节点被称为“头节点”（Head），它的指针指向第二个节点；第二个节点的指针指向第三个，以此类推。最后一个节点的指针通常指向一个特殊值None（或NULL），表示链表的结束。
2.2.1 从零开始构建一个单向链表
为了深刻理解链表的运作机制，我们必须亲手实现它。
# linked_list_implementation.py
class Node:
"""定义链表的节点类。"""
def __init__(self, data, next_node=None):
self.data = data # 数据域，存储节点的值
self.next = next_node # 指针域，存储下一个节点的引用
class SinglyLinkedList:
"""定义一个单向链表类，并实现其核心操作。"""
def __init__(self):
"""初始化一个空链表。"""
self._head = None # 初始化头节点为None，表示链表为空
def is_empty(self):
"""检查链表是否为空。"""
return self._head is None # 如果头节点是None，则链表为空
def prepend(self, data):
"""在链表头部添加一个新节点 (头插法)。O(1)操作。"""
# 创建一个包含新数据的新节点
# 这个新节点的 next 指针指向当前的头节点
new_node = Node(data, self._head) # 新节点的next指向旧的头节点
# 将链表的头节点更新为这个新创建的节点
self._head = new_node # 将链表的头指针更新为新节点
def append(self, data):
"""在链表尾部添加一个新节点 (尾插法)。O(n)操作。"""
new_node = Node(data) # 创建一个新节点，其next默认为None
if self.is_empty(): # 如果链表是空的
self._head = new_node # 新节点就是头节点
return
# 如果链表不为空，需要遍历到最后一个节点
last_node = self._head # 从头节点开始
while last_node.next: # 只要当前节点的next不为None，就继续向后移动
last_node = last_node.next
# 循环结束后，last_node就是最后一个节点
last_node.next = new_node # 将原来的最后一个节点的next指针指向新节点
def traverse(self):
"""遍历链表并打印所有节点的数据。"""
print("遍历链表: ", end="") # 打印前缀
current = self._head # 从头节点开始
while current: # 只要当前节点不为None
print(f"{
current.data} -> ", end="") # 打印当前节点的数据
current = current.next # 移动到下一个节点
print("None") # 链表末尾打印None
def find(self, target):
"""在链表中查找一个值，如果找到则返回True。O(n)操作。"""
current = self._head # 从头节点开始
while current: # 遍历
if current.data == target: # 如果找到了目标值
return True # 返回True
current = current.next # 移动到下一个节点
return False # 如果遍历完都没找到，返回False
def remove(self, target):
"""从链表中删除第一个匹配目标值的节点。O(n)操作。"""
if self.is_empty(): # 如果链表为空，直接返回
return
# Case 1: 要删除的是头节点
if self._head.data == target: # 如果头节点就是要删除的目标
self._head = self._head.next # 直接将头指针指向第二个节点即可
return
# Case 2: 要删除的是中间或尾部的节点
prev_node = self._head # prev_node 指向当前节点的前一个节点
current_node = self._head.next # current_node 指向当前要检查的节点
while current_node: # 遍历
if current_node.data == target: # 如果找到了要删除的节点
# “跳过”这个节点
# 将前一个节点的next指针，直接指向当前节点的下一个节点
prev_node.next = current_node.next # 实现删除
return
# 如果没找到，两个指针都向后移动一位
prev_node = current_node
current_node = current_node.next
# --- 使用我们自己实现的链表 ---
my_list = SinglyLinkedList() # 创建一个空链表实例
print(f"链表是否为空? {
my_list.is_empty()}") # 检查是否为空
print("
在头部添加 10, 20, 30...") # 打印操作描述
my_list.prepend(10) # 链表: 10 -> None
my_list.prepend(20) # 链表: 20 -> 10 -> None
my_list.prepend(30) # 链表: 30 -> 20 -> 10 -> None
my_list.traverse() # 遍历并打印
print(f"链表是否为空? {
my_list.is_empty()}") # 再次检查
print("
在尾部添加 5...") # 打印操作描述
my_list.append(5) # 链表: 30 -> 20 -> 10 -> 5 -> None
my_list.traverse() # 遍历并打印
print(f"
查找值 20: {
my_list.find(20)}") # 查找存在的值
print(f"查找值 100: {
my_list.find(100)}") # 查找不存在的值
print("
删除值 20...") # 打印操作描述
my_list.remove(20) # 删除中间节点
my_list.traverse() # 遍历并打印
print("
删除值 30 (头节点)...") # 打印操作描述
my_list.remove(30) # 删除头节点
my_list.traverse() # 遍历并打印
print("
删除值 5 (尾节点)...") # 打印操作描述
my_list.remove(5) # 删除尾节点
my_list.traverse() # 遍历并打印
这个实现过程，能让你深刻理解链表的插入和删除操作是如何通过改变节点的next指针来完成的。尤其是删除操作，需要一个prev_node来“记住”前一个节点，这是链表操作中的一个经典模式。
2.2.2 数组 vs. 链表：世纪对决
现在，我们可以对这两种核心的线性结构进行一次全面的性能对比。
| 特性 | 数组 (Python list) |
链表 (我们实现的) | 优胜者 & 原因 |
|---|---|---|---|
| 内存布局 | 连续 | 分散 | 数组: 内存连续性带来了缓存友好性，CPU在访问一个元素后，很可能已经把它的邻居也加载到了高速缓存中，后续访问更快。 |
| 随机访问 | O(1) |
O(n) |
数组: 绝对优势。链表要访问第i个元素，必须从头节点开始，一步一步地跳i次。 |
| 头部插入/删除 | O(n) |
O(1) |
链表: 绝对优势。链表的头插/头删只需要修改头指针，是常数时间操作。数组需要移动所有元素。 |
| 尾部插入 | O(1) (均摊) |
O(n) (朴素实现) |
数组: append是O(1)的。我们实现的链表尾插需要遍历到末尾，是O(n)。 |
| 中间插入/删除 | O(n) |
O(n) |
平手: 两者都需要O(n)。数组慢在移动元素，链表慢在查找要操作的位置。 |
| 空间开销 | 较小 | 较大 | 数组: 只需要存储数据本身。链表每个节点都需要额外的空间来存储next指针。 |
优化链表的尾部插入:
我们上面实现的链表，尾部插入是O(n)，这是一个痛点。我们可以通过在链表类中额外维护一个_tail指针，始终指向最后一个节点，来将尾部插入的复杂度优化到O(1)。
代码示例：带尾指针的优化链表
class OptimizedSinglyLinkedList:
"""一个带有头尾指针的单向链表，优化了尾部操作。"""
def __init__(self):
self._head = None # 头指针
self._tail = None # 尾指针
self._size = 0 # 维护一个size属性，获取长度是O(1)
def __len__(self):
"""让链表支持len()函数。"""
return self._size
def append(self, data):
"""优化的尾部插入方法。O(1)操作。"""
new_node = Node(data) # 创建新节点
if self._tail: # 如果链表不为空 (即尾指针存在)
self._tail.next = new_node # 将当前的尾节点的next指向新节点
self._tail = new_node # 更新尾指针为这个新节点
else: # 如果链表为空
self._head = new_node # 新节点既是头也是尾
self._tail = new_node
self._size += 1 # 尺寸加一
# prepend, traverse, find, remove 等方法也需要相应地更新_tail和_size
# (此处为简化省略，但这是实现完整功能所必需的)
结论与应用场景:
选择数组 (Python list):
当你需要频繁地通过索引随机访问元素时。
当你的主要操作是在列表尾部进行添加和删除时。
当对内存占用比较敏感时。
绝大多数情况下，Python的list都是一个足够好、足够快的选择。
选择链表:
当你的主要需求是频繁地在数据结构的头部进行插入和删除时。这是链表最核心的优势场景。
当你需要实现一个**真正的队列（Queue）**时（我们下一节会讲）。
当你处理的数据量极大，无法在内存中开辟一块巨大的连续空间时，链表的非连续存储特性会成为优势。
当插入和删除操作的频率远高于访问操作时。
2.2.3 链表的变体：双向链表与循环链表
双向链表 (Doubly Linked List):
结构: 每个节点除了有next指针指向下一个节点，还有一个prev指针指向上一个节点。
优势:
可以双向遍历。
删除一个节点变得更容易。如果给你一个节点的引用node_to_delete，你不需要像单向链表那样从头遍历来找到它的前一个节点。你可以直接通过node_to_delete.prev来找到前驱，然后执行 node_to_delete.prev.next = node_to_delete.next 和 node_to_delete.next.prev = node_to_delete.prev 来完成删除。这使得在给定节点引用下的删除操作是O(1)的。
劣势: 每个节点需要额外存储一个prev指针，空间开销更大。插入和删除操作需要同时维护next和prev两个指针，逻辑稍微复杂一点。
代码片段：双向链表节点定义
class DoublyNode:
def __init__(self, data, prev_node=None, next_node=None):
self.data = data
self.prev = prev_node # 指向前一个节点的指针
self.next = next_node # 指向后一个节点的指针
循环链表 (Circular Linked List):
结构: 链表的最后一个节点的next指针不再指向None，而是指向头节点，形成一个环。
优势:
从任何一个节点出发，都可以遍历到整个链表。
在某些特定算法（如约瑟夫环问题）中非常有用。
可以用来实现某些循环缓冲区。
劣势: 遍历时需要小心处理终止条件，否则会陷入无限循环。通常需要让遍历指针回到起点来判断循环结束。
2.3 栈：后进先出 (LIFO) 的哲学
栈（Stack）是一种特殊的线性数据结构，它遵循**后进先出（Last-In, First-Out, LIFO）**的原则。你可以把它想象成一摞盘子：你最后放上去的盘子，总是第一个被拿走。
栈的核心操作:
push(item): 将一个元素压入栈顶。
pop(): 从栈顶弹出一个元素，并返回它。
peek() (或 top()): 查看栈顶元素，但不弹出。
is_empty(): 检查栈是否为空。
所有这些核心操作的时间复杂度都应该是O(1)。
2.3.1 Python中的栈实现
在Python中，有多种方式可以实现一个栈。
方式一：使用Python list
Python的list类型提供了append()和pop()方法，它们都作用于列表的尾部，并且都是O(1)（均摊）的。这完美地契合了栈的LIFO特性。因此，使用list来模拟栈是最简单、最直接、也最常见的方式。
# stack_using_list.py
stack = [] # 用一个空列表来代表栈
# Push 操作
stack.append('A') # 'A'入栈
stack.append('B') # 'B'入栈
stack.append('C') # 'C'入栈
print(f"当前栈 (列表表示): {
stack}") # 打印栈内容
# Peek 操作 (查看栈顶)
# 列表的最后一个元素就是栈顶
top_element = stack[-1] # 获取列表的最后一个元素
print(f"栈顶元素是: {
top_element}") # 打印栈顶元素
# Pop 操作
popped_item = stack.pop() # 从列表尾部弹出一个元素
print(f"弹出的元素是: {
popped_item}") # 打印弹出的元素
print(f"Pop操作后的栈: {
stack}") # 打印操作后的栈
popped_item = stack.pop() # 再次弹出
print(f"弹出的元素是: {
popped_item}")
print(f"Pop操作后的栈: {
stack}")
# is_empty 操作
is_empty = not stack # 一个空列表在布尔上下文中是False，取反即为True
print(f"栈现在是否为空? {
is_empty}") # 打印是否为空
方式二：使用collections.deque
collections.deque（双端队列，Double-ended Queue）是一个专门为在两端进行快速添加和删除操作而设计的序列类型。它的append()（右端添加）和pop()（右端弹出）操作都是严格的O(1)，没有list扩容时那种最坏情况的性能波动。
对于一个严格要求性能稳定性的栈实现，或者当栈的规模可能非常巨大，deque是比list更好的选择。
# stack_using_deque.py
from collections import deque
stack = deque() # 使用deque创建一个栈
# Push 操作 (使用 append)
stack.append('X')
stack.append('Y')
stack.append('Z')
print(f"当前栈 (deque表示): {
stack}")
# Peek 操作
top_element = stack[-1] # deque也支持索引访问最后一个元素
print(f"栈顶元素是: {
top_element}")
# Pop 操作
popped_item = stack.pop()
print(f"弹出的元素是: {
popped_item}")
print(f"Pop操作后的栈: {
stack}")
方式三：使用queue.LifoQueue
queue模块提供的是线程安全的数据结构，用于在多线程编程中安全地传递数据。LifoQueue就是一个后进先出的队列，也就是一个线程安全的栈。如果你是在单线程环境中使用，它会比list或deque慢，因为有额外的锁开销。但如果你在多线程程序中需要一个共享的栈，这应该是你的首选。
2.3.2 栈的经典应用场景
栈的LIFO特性，使得它在计算机科学中无处不在。
应用一：函数调用栈
这是栈最底层、最核心的应用。当你调用一个函数时，操作系统会把这个函数的返回地址、参数、局部变量等信息打包成一个“栈帧（Stack Frame）”，然后压入一个叫做“调用栈”的内存区域。当函数返回时，再从栈顶弹出它的栈帧，恢复到调用前的状态。递归函数之所以能工作，就是依赖于调用栈。如果递归深度太深，会导致调用栈溢出（Stack Overflow）。
应用二：括号匹配
这是一个经典的面试题。如何检查一个字符串中的括号（如(), [], {}）是否是成对且正确嵌套的？
# balanced_parentheses.py
def is_balanced(s: str) -> bool:
"""使用栈来检查括号是否平衡。"""
stack = [] # 使用列表作为栈
# 创建一个映射，将闭括号映射到其对应的开括号
mapping = {
")": "(", "]": "[", "}": "{"}
for char in s: # 遍历字符串中的每个字符
if char in mapping: # 如果当前字符是一个闭括号
# 1. 尝试从栈顶弹出一个元素。如果栈为空，说明没有对应的开括号，用一个虚拟值'#'代替。
top_element = stack.pop() if stack else '#'
# 2. 检查弹出的开括号是否与当前闭括号匹配
if mapping[char] != top_element: # 如果不匹配
return False # 括号不平衡，立即返回False
else: # 如果当前字符是一个开括号
stack.append(char) # 将其压入栈中
# 循环结束后，如果栈是空的，说明所有开括号都被正确匹配了
# 如果栈不为空，说明有未被匹配的开括号
return not stack # 返回栈是否为空的布尔值
# 测试用例
print(f"'()[]{
{}}' 是否平衡? {is_balanced('()[]{}')}") # True
print(f"'([)]' 是否平衡? {
is_balanced('([)]')}") # False
print(f"'{
{[]}}' 是否平衡? {is_balanced('{
{[]}}')}") # True
print(f"'(' 是否平衡? {
is_balanced('(')}") # False
算法思路: 遍历字符串。遇到开括号，就压入栈中。遇到闭括号，就从栈顶弹出一个开括号进行匹配。如果匹配成功，继续；如果栈为空或匹配失败，则字符串不平衡。遍历结束后，如果栈为空，则字符串平衡，否则不平衡。
应用三：逆波兰表达式求值 (后缀表达式)
逆波兰表达式（Reverse Polish Notation, RPN）是一种将运算符写在操作数后面的数学表达式。例如，3 4 + 等价于 3 + 4。求值RPN表达式是栈的完美应用场景。
# evaluate_rpn.py
def eval_rpn(tokens: list[str]) -> int:
"""使用栈来计算逆波兰表达式的值。"""
stack = [] # 使用列表作为栈
for token in tokens: # 遍历表达式中的每个标记
if token in "+-*/": # 如果标记是运算符
# 从栈顶弹出两个操作数
# 注意顺序：先弹出的是右操作数
right_operand = stack.pop() # 弹出右操作数
left_operand = stack.pop() # 弹出左操作数
# 根据运算符进行计算
if token == "+":
result = left_operand + right_operand
elif token == "-":
result = left_operand - right_operand
elif token == "*":
result = left_operand * right_operand
else: # token == "/"
# 注意Python中除法的结果是浮点数，题目通常要求向零取整
result = int(left_operand / right_operand)
stack.append(result) # 将计算结果压回栈中
else: # 如果标记是数字
stack.append(int(token)) # 将其转换为整数并压入栈中
# 遍历结束后，栈中应该只剩下一个元素，即最终结果
return stack.pop() # 弹出并返回最终结果
# 测试用例
expression1 = ["2", "1", "+", "3", "*"] # (2 + 1) * 3 = 9
expression2 = ["4", "13", "5", "/", "+"] # 4 + (13 / 5) = 4 + 2 = 6
print(f"表达式 {
expression1} 的值是: {
eval_rpn(expression1)}")
print(f"表达式 {
expression2} 的值是: {
eval_rpn(expression2)}")
算法思路: 遍历表达式。遇到数字，就压入栈。遇到运算符，就从栈顶弹出两个数字进行运算，然后将结果再压回栈中。遍历结束后，栈中剩下的唯一一个数字就是最终结果。
2.4 队列：先进先出 (FIFO) 的公平之道
与栈的LIFO原则相对，队列（Queue）遵循的是**先进先出（First-In, First-Out, FIFO）**的原则。这就像在超市排队结账，最先来排队的人，总是第一个结账离开。
队列的核心操作:
enqueue(item): 将一个元素加入队尾（入队）。
dequeue(): 从队头移除一个元素，并返回它（出队）。
peek() (或 front()): 查看队头元素，但不移除。
is_empty(): 检查队列是否为空。
同样，所有这些核心操作的时间复杂度都应该是O(1)。
2.4.1 Python中的队列实现：为何不能用list？
如果我们尝试用Python的list来模拟队列：
入队 (enqueue): 我们可以用list.append(item)，这是一个O(1)的操作，很好。
出队 (dequeue): 我们需要从队列的头部移除元素，对应到列表就是索引0的位置。这个操作需要调用list.pop(0)。
陷阱: 我们在2.1.1节已经知道，list.pop(0)是一个**O(n)**的操作，因为它需要将所有后续元素向左移动一位。当队列很长时，这会变得极其低效。
结论：永远不要用list来实现一个真正的队列！
正确的实现方式：collections.deque
collections.deque（双端队列）是专门为此而生的。
它支持从**右端（尾部）**快速添加：deque.append(item) (对应 enqueue)
它支持从**左端（头部）**快速移除：deque.popleft() (对应 dequeue)
这两个操作都是严格的O(1)时间复杂度，因为deque底层是用双向链表实现的，对两端的操作都只需要修改头尾指针。
# queue_using_deque.py
from collections import deque
queue = deque() # 使用deque创建一个队列
# Enqueue 操作
queue.append('任务1') # "任务1" 入队
queue.append('任务2') # "任务2" 入队
queue.append('任务3') # "任务3" 入队
print(f"当前队列 (deque表示): {
queue}") # 打印队列内容
# Peek 操作 (查看队头)
# deque的第一个元素就是队头
front_element = queue[0] # 获取deque的第一个元素
print(f"队头元素是: {
front_element}") # 打印队头元素
# Dequeue 操作
dequeued_item = queue.popleft() # 从队列左端（头部）弹出一个元素
print(f"出队的元素是: {
dequeued_item}") # 打印出队元素
print(f"Dequeue操作后的队列: {
queue}") # 打印操作后的队列
dequeued_item = queue.popleft() # 再次出队
print(f"出队的元素是: {
dequeued_item}")
print(f"Dequeue操作后的队列: {
queue}")
2.4.2 队列的经典应用场景
队列的FIFO特性，使其成为处理任务、请求和广度优先搜索等问题的理想工具。
应用一：任务队列与资源调度
在操作系统中，多个进程需要共享打印机。操作系统会将所有的打印请求放入一个队列中。打印机按照先来后到的顺序，从队列头部取出任务进行打印。这保证了公平性。在Web服务器中，用户的HTTP请求也会被放入一个队列中，由工作线程池来依次处理。
应用二：广度优先搜索 (Breadth-First Search, BFS)
BFS是一种图和树的遍历算法，它从一个起始节点开始，首先访问所有与起始节点距离为1的邻居节点，然后是距离为2的，以此类推，像水波纹一样一层一层地向外扩散。队列是实现BFS的核心。
代码示例：使用队列实现树的层序遍历 (BFS)
# tree_level_order_traversal.py
from collections import deque
class TreeNode:
"""定义一个简单的二叉树节点。"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order_traversal(root: TreeNode) -> list[list[int]]:
"""使用队列对二叉树进行层序遍历。"""
if not root: # 如果树为空
return [] # 返回空列表
result = [] # 存储最终结果，一个包含每层节点的列表
queue = deque([root]) # 初始化队列，将根节点入队
while queue: # 当队列不为空时，循环继续
level_size = len(queue) # 当前层的节点数量
current_level_nodes = [] # 存储当前层所有节点的值
# 遍历当前层的所有节点
for _ in range(level_size):
# 1. 从队头出队一个节点
node = queue.popleft() # 出队
current_level_nodes.append(node.val) # 将其值加入当前层列表
# 2. 将其非空的子节点入队，为下一层的遍历做准备
if node.left: # 如果左子节点存在
queue.append(node.left) # 左子节点入队
if node.right: # 如果右子节点存在
queue.append(node.right) # 右子节点入队
result.append(current_level_nodes) # 将处理完的当前层列表加入最终结果
return result
# 构建一个测试树
# 3
# /
# 9 20
# /
# 15 7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print("树的层序遍历结果:")
print(level_order_traversal(root)) # 预期输出: [[3], [9, 20], [15, 7]]
算法思路:
创建一个队列，并将根节点入队。
当队列不为空时，进入循环。在每一轮循环中，我们处理“一层”的节点。
首先记录下当前队列的长度level_size，这就是当前层的节点数。
循环level_size次，每次从队头popleft一个节点，将其值存入一个临时列表current_level_nodes。
在处理每个节点时，将其非空的左、右子节点append到队尾。这些子节点就是下一层的节点。
内层循环结束后，current_level_nodes就包含了当前层的所有节点值，将其加入最终结果result。此时，队列中剩下的，正好是下一层的所有节点。
重复此过程，直到队列为空。
这个例子完美地展示了队列FIFO的特性是如何保证我们能够一层一层地、不重不漏地遍历整个树形结构的。
第三章：哈希表 —— 恒定时间查找的魔法
在我们精通了线性结构之后，我们将踏入一个更具魔力的领域。想象一下，你有一个巨大的图书馆，但你不需要像线性查找那样一本一本地找书（O(n)），也不需要事先把所有书按字母排好序再用二分法查找（O(log n)）。你只需要告诉图书管理员书名，他就能在几乎一瞬间，直接告诉你书在哪一排、哪一架。无论图书馆藏书十万册还是一百万册，这个“瞬间”几乎不变。
这就是哈希表（Hash Table）带给我们的魔法——近乎O(1)的恒定时间查找、插入和删除。它是计算机科学中最强大、应用最广泛的数据结构之一，也是Python语言核心利器dict和set的底层基石。
3.1 核心思想：从直接寻址到哈希映射
要理解哈希表，我们先从一个理想化的、不切实际的想法开始：直接寻址表（Direct Address Table）。
假设你正在为一个小型在线课程平台统计学生出勤，学生的学号是从0到999的整数。你想快速记录和查询某个学号的学生是否出勤。最简单粗暴的方法是什么？
你可以创建一个长度为1000的巨大布尔数组 attendance：
attendance = [False] * 1000
记录出勤: 学号为 520 的学生来了，执行 attendance[520] = True。这是一个O(1)操作。
查询出勤: 想知道学号为 123 的学生是否来了，只需检查 attendance[123] 的值。这也是一个O(1)操作。
这就是直接寻址，它利用了数组O(1)随机访问的特性。关键字（Key，这里是学号）本身就是数组的索引。
直接寻址的致命缺陷:
这个想法在关键字（Key）的范围很小且是整数时可行。但现实世界中：
关键字范围太大: 如果关键字是中国的18位身份证号，你需要创建一个长度达到10¹⁸的数组，这在宇宙毁灭前也造不出来。
关键字不是整数: 如果关键字是学生的姓名（字符串），例如"Zhang San"，你根本无法直接把它当作数组索引。
为了解决这个问题，我们需要一座桥梁，一个“翻译官”，它能将任意的、范围巨大的关键字，转化成一个固定范围内的、可作为数组索引的整数。这个“翻译官”，就是哈希函数（Hash Function）。
哈希函数的诞生:
哈希函数，我们通常记为h(key)，是一个数学函数，它的输入是任意的key，输出是一个整数，我们称之为哈希值（Hash Value）或哈希码（Hash Code）。
h(key) -> hash_value
然后，我们用这个哈希值对数组（哈希表）的长度m取模，得到最终的数组索引index。
index = hash_value % m
整个过程就是哈希映射：
任意的Key ---(哈希函数h)--> 哈希值 ---(取模运算%)--> 数组索引index
现在，我们的存储和查找流程变成了：
存储: table[h(key) % m] = value
查找: return table[h(key) % m]
通过引入哈希函数，我们似乎用一种巧妙的方式，将直接寻址的能力扩展到了任意类型的关键字上，同时将巨大的关键字空间压缩到了一个可控大小的数组空间内。
理想的哈希函数应具备的品质:
确定性 (Deterministic): 对于同一个key，每次调用哈希函数都必须返回相同的哈希值。
高效性 (Efficient): 哈希函数的计算过程必须非常快，不能成为性能瓶颈。
均匀性 (Uniformity): 这是最重要也最难的一点。一个好的哈希函数应该能够将不同的key尽可能均匀地散列（scatter）到数组的各个索引位置上。如果哈希函数设计不佳，导致大量不同的key都映射到同一个索引上，灾难就发生了。
这个灾难，就是哈希冲突（Hash Collision）。
3.2 哈希冲突：不可避免的“生日悖论”
哈希冲突，指的是两个或多个不同的key，经过哈希函数计算后，得到了相同的数组索引。
key1 != key2, 但是 h(key1) % m == h(key2) % m
为什么说冲突是不可避免的？因为关键字的可能取值空间（例如，所有可能的字符串）通常是无限或极其巨大的，而我们的数组大小m是有限的。根据“鸽巢原理”（Pigeonhole Principle），当要放入的“鸽子”（关键字）数量超过“鸽巢”（数组槽位）数量时，必然至少有两个鸽子要挤在同一个巢里。
实际上，即使关键字数量远小于数组大小，冲突发生的概率也比直觉要高得多，这就是著名的“生日悖论”：在一个23人的班级里，至少有两个人生日相同的概率就已经超过了50%。
因此，一个哈希表的性能和健壮性，几乎完全取决于它如何优雅地解决哈希冲突。解决冲突的策略主要分为两大流派：拉链法和开放寻址法。
3.2.1 冲突解决方法一：拉链法 (Separate Chaining)
拉链法（也叫链接法）是解决哈希冲突最常用、最经典的方法。它的思想非常直观：
核心思想: 哈希表的数组本身不直接存储数据，而是存储一个“容器”的指针。所有哈希到同一个索引位置的key-value对，都被放入这个索引位置对应的容器中。这个容器最常见的就是链表（Linked List）。
工作流程:
创建一个数组，数组的每个槽位（slot）都初始化为一个空链表的头指针。
插入 (key, value):
a. 计算index = h(key) % m。
b. 找到数组第index个槽位的那个链表。
c. 将新的(key, value)对作为一个新节点，添加到这个链表的末尾（或头部）。
查找key:
a. 计算index = h(key) % m。
b. 找到数组第index个槽位的链表。
c. 遍历这个链表，逐个检查节点的key是否与要查找的key相等。
d. 如果找到，返回对应的value；如果遍历完整个链表都没找到，则说明key不存在。
拉链法的复杂度分析:
负载因子 (Load Factor): 我们定义一个重要的参数 α = n / m，其中n是已存储的元素数量，m是哈希表的数组大小。α代表了哈希表的“拥挤程度”，或者说每个槽位上链表的平均长度。
查找/插入/删除:
最好情况: O(1)。没有发生冲突，链表为空或只有一个节点。
最坏情况: O(n)。哈希函数设计极差，导致所有n个元素都哈希到了同一个索引上，哈希表退化成了一个长长的链表，查找操作变成了链表的线性扫描。
平均情况: O(1 + α)。一次成功的查找，平均需要遍历链表的一半；一次不成功的查找，需要遍历整个链表。计算哈希和索引是O(1)，遍历链表的期望时间是O(α)。因此总的平均时间是O(1 + α)。
结论: 只要我们能通过合理的哈希函数和适时的扩容（后面会讲）来保证负载因子α是一个不大的常数（例如，始终小于1），我们就可以认为拉链法的平均时间复杂度是 O(1)。
从零开始实现一个基于拉链法的哈希表
这个实现将模仿Python字典的行为，支持[]赋值和取值。
# hash_table_separate_chaining.py
from linked_list_implementation import Node, SinglyLinkedList # 假设我们复用之前实现的链表
class HashTableSeparateChaining:
"""一个使用拉链法解决冲突的哈希表示例实现。"""
def __init__(self, initial_capacity=11):
"""初始化哈希表。"""
# 选择一个素数作为初始容量，有助于减少冲突
self._capacity = initial_capacity # 哈希表的容量 (数组大小m)
self._table = [SinglyLinkedList() for _ in range(self._capacity)] # 创建一个空链表数组
self._size = 0 # 当前存储的元素数量n
def _hash(self, key):
"""一个简单的哈希函数，用于将键转换为哈希值。"""
# 对于不同类型的键，使用不同的哈希方法
if isinstance(key, (int, float)): # 如果是数字
return int(key) # 直接使用其整数部分
elif isinstance(key, str): # 如果是字符串
# 使用一个简单的多项式滚动哈希
hash_val = 0
p = 31 # 一个小的素数
for char in key:
hash_val = (hash_val * p + ord(char))
return hash_val
else: # 对于其他不可哈希的类型
raise TypeError(f"Unhashable type: '{
type(key).__name__}'")
def _get_index(self, key):
"""根据键计算其在哈希表数组中的索引。"""
hash_code = self._hash(key) # 计算键的哈希值
return hash_code % self._capacity # 取模得到最终索引
def __setitem__(self, key, value):
"""实现 hash_table[key] = value 的功能。"""
index = self._get_index(key) # 获取键对应的索引
bucket = self._table[index] # 找到对应的桶（链表）
# 遍历链表，检查键是否已存在
current = bucket._head
while current:
# 在链表中，我们存储(key, value)元组
if current.data[0] == key: # 如果找到了相同的键
# 更新值，然后返回
current.data = (key, value) # 更新已存在键的值
return
current = current.next
# 如果键不存在，则在链表头部插入新的(key, value)对
bucket.prepend((key, value)) # 在链表头部插入新的键值对
self._size += 1 # 哈希表大小加一
# (TODO: 在这里检查负载因子并决定是否需要扩容)
def __getitem__(self, key):
"""实现 value = hash_table[key] 的功能。"""
index = self._get_index(key) # 获取键对应的索引
bucket = self._table[index] # 找到对应的桶（链表）
current = bucket._head # 从链表头部开始遍历
while current:
if current.data[0] == key: # 如果找到了键
return current.data[1] # 返回对应的值
current = current.next
# 如果遍历完链表都没找到
raise KeyError(key) # 抛出KeyError异常，与Python字典行为一致
def __delitem__(self, key):
"""实现 del hash_table[key] 的功能。"""
index = self._get_index(key) # 获取键对应的索引
bucket = self._table[index] # 找到对应的桶（链表）
# 需要特殊处理头节点
if bucket._head and bucket._head.data[0] == key: # 如果头节点就是要删除的
bucket._head = bucket._head.next # 直接移除头节点
self._size -= 1 # 哈希表大小减一
return
# 遍历查找要删除的节点及其前驱节点
prev = bucket._head
current = bucket._head.next if bucket._head else None
while current:
if current.data[0] == key: # 如果找到了要删除的节点
prev.next = current.next # “跳过”当前节点，实现删除
self._size -= 1 # 哈希表大小减一
return
prev = current
current = current.next
# 如果遍历完都没找到
raise KeyError(key) # 抛出KeyError
def __len__(self):
"""实现 len(hash_table) 功能。"""
return self._size
def __str__(self):
"""为打印哈希表提供一个友好的字符串表示。"""
elements = []
for i in range(self._capacity):
elements.append(f"Bucket {
i}:")
bucket = self._table[i]
current = bucket._head
while current:
elements.append(f" -> {
current.data}")
current = current.next
return "
".join(elements)
# --- 使用我们自己实现的哈希表 ---
ht = HashTableSeparateChaining() # 创建一个哈希表示例
ht['name'] = 'Alice' # 插入字符串键
ht['age'] = 30 # 插入整数键
ht[99.5] = 'score' # 插入浮点数键
ht['city'] = 'New York' # 插入另一个字符串键，可能会发生冲突
print(f"哈希表大小: {
len(ht)}") # 打印大小
print(f"姓名: {
ht['name']}") # 获取值
print(f"年龄: {
ht['age']}") # 获取值
# 测试更新
print("
更新姓名为 'Bob'...") # 打印操作描述
ht['name'] = 'Bob' # 更新一个已存在的键
print(f"更新后的姓名: {
ht['name']}") # 打印更新后的值
# 测试删除
print("
删除年龄...") # 打印操作描述
del ht['age']
print(f"删除后的哈希表大小: {
len(ht)}") # 打印删除后的大小
try:
print(ht['age']) # 尝试访问已删除的键
except KeyError as e:
print(f"尝试访问已删除的键 'age'，正确地抛出了 KeyError: {
e}") # 打印捕获的异常
print("
哈希表内部结构:") # 打印内部结构标题
print(ht) # 打印整个哈希表的内部存储结构
3.2.2 冲突解决方法二：开放寻址法 (Open Addressing)
开放寻址法是另一种解决哈希冲突的思路，它的核心思想是：所有元素都必须存储在哈希表的主数组中，不使用任何外部数据结构（如链表）。
核心思想: 当要插入一个(key, value)对，计算出索引index后发现该位置已经被占用了，就**继续探测（Probe）**数组中的下一个、下下个……槽位，直到找到一个空位，然后将数据存入。
这个“探测下一个槽位”的策略，就是不同开放寻址法的区别所在。
A. 线性探测 (Linear Probing)
这是最简单的探测策略。如果h(key)位置被占用，就检查h(key) + 1，如果还被占用，就检查h(key) + 2，以此类推，直到找到一个空槽位。探测序列为 i, i+1, i+2, ... （对数组大小m取模）。
优点: 实现简单，并且因为它倾向于访问连续内存，可以很好地利用CPU缓存。
缺点: 会产生一种叫做**一次聚集（Primary Clustering）**的现象。当几个元素哈希到相近的位置时，它们会形成一长串连续的、被占用的槽位“团块”。后续任何哈希到这个团块内部或团块前一个位置的新元素，都需要遍历很长的距离才能找到空位，并且还会使这个团块变得更长，形成恶性循环，严重影响性能。
B. 二次探测 (Quadratic Probing)
为了缓解一次聚集，二次探测采用非线性的方式寻找下一个空位。探测序列为 i, i+1², i+2², i+3², ... （即 i, i+1, i+4, i+9, ...，对数组大小m取模）。
优点: 能够有效地打散一次聚集形成的团块，因为探测的步长越来越大。
缺点:
可能会产生二次聚集（Secondary Clustering）。如果两个不同的键初始哈希到了同一个位置，那么它们的整个探测序列将是完全相同的。
不能保证探测到整个哈希表的所有槽位。为了能探测到所有槽位，哈希表的容量m必须是素数，并且负载因子α不能超过0.5。
C. 双重哈希 (Double Hashing)
这是解决开放寻址法聚集问题的最佳方案。它使用两个不同的哈希函数，h1(key)和h2(key)。
第一个哈希函数h1和之前一样，用来计算初始的索引位置。
第二个哈希函数h2用来计算探测的步长。
探测序列为 h1(key), h1(key) + 1*h2(key), h1(key) + 2*h2(key), ... （对m取模）。
优点: 因为步长h2(key)是由键本身决定的，所以即使两个键的初始哈希值h1相同，只要它们的h2值不同，它们的探测序列也会完全不同。这极大地打散了元素，几乎完全消除了聚集现象。
要求: h2(key)的返回值不能是0，并且h2(key)的值应该与表容量m互质，以保证能探测到所有槽位。这通常通过让m为素数，并让h2(key) = q - (key % q)（其中q是小于m的另一个素数）来实现。
开放寻址法中的删除问题:
在开放寻址法中，你不能简单地将一个要删除的槽位设置为空（None）。为什么？
想象一下A, B, C三个键，h(A)=i, h(B)=i, h(C)=i+1。
插入A：存入table[i]。
插入B：table[i]被占用，线性探测，存入table[i+1]。
插入C：table[i+1]被占用，线性探测，存入table[i+2]。
现在，如果我们删除了B，将table[i+1]设为None。
然后我们去查找C，计算出h(C)=i+1，发现table[i+1]是空的！算法会错误地认为C不存在，因为它中断了探测链。
解决方案: 使用一个特殊的**墓碑（Tombstone）**标记。当删除一个元素时，我们不把它设为None，而是设为一个特殊的哨兵对象（例如，一个专门创建的TOMBSTONE对象）。
查找时: 遇到墓碑，要继续探测，不能停下来。
插入时: 遇到墓碑，可以直接将新元素插入到这个墓碑的位置，这可以重用已删除的槽位。
从零开始实现一个基于线性探测的哈希表
# hash_table_open_addressing.py
# 创建一个哨兵对象，用于标记被删除的槽位
TOMBSTONE = object()
class HashTableOpenAddressing:
"""一个使用开放寻址法（线性探测）解决冲突的哈希表示例。"""
def __init__(self, initial_capacity=11):
self._capacity = initial_capacity
# 在开放寻址中，表直接存储(key, value)元组
self._table = [None] * self._capacity
self._size = 0
# _hash 和 _get_index 方法与拉链法的实现相同 (此处省略)
def _hash(self, key):
if isinstance(key, (int, float)): return int(key)
elif isinstance(key, str):
hash_val = 0
p = 31
for char in key: hash_val = (hash_val * p + ord(char))
return hash_val
else: raise TypeError(f"Unhashable type: '{
type(key).__name__}'")
def _find_slot(self, key):
"""查找键对应的槽位，或者第一个可用的槽位（空或墓碑）。"""
index = self._hash(key) % self._capacity # 计算初始索引
first_tombstone = None # 记录遇到的第一个墓碑的位置
while self._table[index] is not None: # 只要当前槽位不为空
# 检查当前槽位是否是我们要找的键
if self._table[index] is not TOMBSTONE and self._table[index][0] == key:
return index, True # 找到了键，返回其索引和True
# 如果当前槽位是墓碑，并且我们还没记录过墓碑位置
if self._table[index] is TOMBSTONE and first_tombstone is None:
first_tombstone = index # 记录下来
# 线性探测，移动到下一个槽位
index = (index + 1) % self._capacity
# 循环结束，说明没找到键
if first_tombstone is not None:
# 如果我们曾遇到过墓碑，返回第一个墓碑的位置，因为可以插入这里
return first_tombstone, False
else:
# 如果一路都是被占用的（直到遇到None），返回这个空槽位的位置
return index, False
def __setitem__(self, key, value):
"""实现 hash_table[key] = value """
index, found = self._find_slot(key) # 查找槽位
if not found: # 如果键不存在
# (TODO: 在这里检查负载因子并扩容)
if self._table[index] is None: # 如果这个槽位是真正的空位
self._size += 1 # 只有在占用新槽位时才增加size
# 无论键是否存在，都将(key, value)放入找到的槽位
self._table[index] = (key, value) # 插入或更新
def __getitem__(self, key):
"""实现 value = hash_table[key] """
index, found = self._find_slot(key) # 查找槽位
if not found: # 如果没找到
raise KeyError(key) # 抛出异常
return self._table[index][1] # 返回槽位中存储的值
def __delitem__(self, key):
"""实现 del hash_table[key] """
index, found = self._find_slot(key) # 查找槽位
if not found: # 如果没找到
raise KeyError(key) # 抛出异常
# 将槽位标记为墓碑
self._table[index] = TOMBSTONE # 设置为墓碑，而不是None
# 注意：在这种简单实现中，size没有减少，这会导致负载因子不准确。
# 一个更完整的实现需要区分size和已占用槽位数。
def __len__(self):
return self._size
# --- 使用 ---
ht_oa = HashTableOpenAddressing()
ht_oa['a'] = 1
ht_oa['b'] = 2
ht_oa['c'] = 3 # 'c' 和 'a' 可能会哈希到相近的位置
ht_oa['d'] = 4
print(f"Value for 'c': {
ht_oa['c']}")
del ht_oa['b']
print(f"Value for 'c' after deleting 'b': {
ht_oa['c']}") # 应该仍然能找到'c'
try:
print(ht_oa['b'])
except KeyError:
print("Key 'b' correctly not found after deletion.")
这个开放寻址法的实现，让你能亲身体会到探测过程和墓碑机制的重要性。它与拉链法相比，在内存使用上更紧凑，但冲突解决的逻辑更复杂，且对负载因子和哈希函数的均匀性要求更高。
3.3 哈希表的动态扩容：保持性能的关键
我们在之前的分析中一直强调，哈希表能维持O(1)平均性能的关键，在于保证其**负载因子α = n / m**处于一个合理的、较低的水平。随着我们不断向哈希表中插入新元素，n会持续增大，如果数组容量m保持不变，负载因子α就会线性增长。
对于拉链法，α的增大会导致链表越来越长，查找效率逐渐退化为O(n)。
对于开放寻址法，α的增大意味着空槽位越来越少，每次插入和查找都需要进行更多的探测，性能会急剧恶化。当α接近1时，哈希表几乎被填满，性能将趋向于O(n)。
因此，一个生产级别的哈希表实现，必须具备**动态扩容（Resizing 或 Re-hashing）的能力。当负载因子超过某个预设的阈值（Threshold）**时，哈希表必须进行一次“重组”，以降低负载因子，恢复其高性能。
动态扩容的触发时机:
拉链法: 通常在负载因子 α > 0.75 或 α > 1.0 时触发。
开放寻址法: 必须在 α < 1 时触发，通常阈值设置得更低，例如 α > 0.5 或 α > 0.7，因为它的性能对负载因子更敏感。
扩容的核心过程 (Re-hashing):
扩容绝不是简单地将原有数组复制到一个更大的数组中。因为哈希表的索引是与数组容量m相关的（index = hash_value % m），当m改变时，同一个key的索引也会随之改变。
正确的扩容过程如下：
创建新表: 创建一个容量更大的新数组，通常是当前容量的两倍（m_new = 2 * m）。选择两倍的大小可以在多次扩容中平摊成本。新容量最好也选择一个素数，但这在实践中为了方便计算常被简化。
遍历旧表: 遍历旧哈希表中的每一个已存储的元素（key, value对）。
重新哈希 (Re-hash): 对于每一个从旧表中取出的key，使用**新的容量m_new**来重新计算它的新索引：new_index = h(key) % m_new。
放入新表: 将这个(key, value)对插入到新哈希表的new_index位置上。如果新位置也发生冲突，则按照新表的冲突解决策略（如拉链法或开放寻址法）进行处理。
替换旧表: 当所有元素都从旧表迁移到新表后，用新表替换掉旧表，并更新哈希表的容量m和大小n等属性。
扩容的成本:
这个过程需要遍历所有n个现有元素，并为它们每一个都重新计算哈希和索引，然后插入到新表中。因此，单次扩容操作的时间复杂度是**O(n + m)，其中n是元素数量，m是旧表的容量。由于n和m通常是同量级的，我们可以简化为O(n)**。
虽然单次扩容成本很高，但它并不会频繁发生。与list的append操作类似，通过均摊分析，我们可以证明，只要每次扩容都将容量加倍，那么将n个元素逐个插入一个空哈希表（包括所有中间可能发生的扩容）的总时间复杂度依然是O(n)，即均摊下来每次插入的成本仍然是O(1)。
将动态扩容机制集成到我们的实现中
现在，我们来修改之前实现的HashTableSeparateChaining，为其添加动态扩容功能。
# hash_table_with_resizing.py
# (我们假设之前的Node和SinglyLinkedList类已经定义好)
from linked_list_implementation import Node, SinglyLinkedList
class ResizableHashTable:
"""一个实现了动态扩容的、基于拉链法的哈希表。"""
def __init__(self, initial_capacity=11, load_factor_threshold=0.75):
self._capacity = initial_capacity # 哈希表的容量 (m)
self._table = [SinglyLinkedList() for _ in range(self._capacity)] # 创建链表数组
self._size = 0 # 当前存储的元素数量 (n)
self._load_factor_threshold = load_factor_threshold # 触发扩容的负载因子阈值
def _hash(self, key):
# (哈希函数与之前实现相同，此处省略以保持简洁)
if isinstance(key, (int, float)): return int(key)
elif isinstance(key, str):
hash_val = 0
p = 31
for char in key: hash_val = (hash_val * p + ord(char))
return hash_val
else: raise TypeError(f"Unhashable type: '{
type(key).__name__}'")
def _get_load_factor(self):
"""计算当前的负载因子。"""
return self._size / self._capacity # 负载因子 α = n / m
def _resize(self):
"""执行扩容操作 (Re-hashing)。"""
new_capacity = self._capacity * 2 # 计算新容量，通常为旧容量的两倍
print(f"
--- 触发扩容！负载因子已超过阈值 ---") # 打印扩容提示
print(f"旧容量: {
self._capacity}, 新容量: {
new_capacity}") # 打印容量变化
# 1. 保存旧表中的所有元素
all_elements = [] # 创建一个临时列表来存储所有旧的键值对
for i in range(self._capacity): # 遍历旧表的每一个桶
current = self._table[i]._head
while current: # 遍历桶中的链表
all_elements.append(current.data) # 将 (key, value) 元组存入临时列表
current = current.next
# 2. 创建一个全新的、更大的空表
self._capacity = new_capacity # 更新容量属性
self._table = [SinglyLinkedList() for _ in range(self._capacity)] # 创建新的空链表数组
self._size = 0 # 重置大小计数器，因为我们会通过__setitem__重新填充
# 3. 将所有旧元素重新哈希并插入到新表中
print("正在重新哈希所有元素...") # 打印rehash提示
for key, value in all_elements: # 遍历临时列表中保存的所有元素
self.__setitem__(key, value, resizing=True) # 调用__setitem__将元素插入新表
# 传入 resizing=True 避免在扩容过程中再次触发扩容
print("--- 扩容完成 ---") # 打印扩容完成提示
def __setitem__(self, key, value, resizing=False):
"""实现 hash_table[key] = value，并集成扩容检查。"""
# 仅在非扩容过程中的插入操作前检查是否需要扩容
if not resizing and self._get_load_factor() >= self._load_factor_threshold:
self._resize() # 如果负载因子达到阈值，则执行扩容
index = self._hash(key) % self._capacity # 使用当前（可能已更新的）容量计算索引
bucket = self._table[index]
current = bucket._head
is_update = False
while current:
if current.data[0] == key:
current.data = (key, value)
is_update = True
break
current = current.next
if not is_update:
bucket.prepend((key, value))
self._size += 1
# __getitem__, __delitem__, __len__, __str__ 等方法与之前实现相同
# (为简洁省略，但它们现在会受益于扩容带来的性能稳定性)
def __getitem__(self, key):
index = self._hash(key) % self._capacity
bucket = self._table[index]
current = bucket._head
while current:
if current.data[0] == key: return current.data[1]
current = current.next
raise KeyError(key)
def __len__(self):
return self._size
# --- 演示动态扩容 ---
ht_resizable = ResizableHashTable(initial_capacity=5, load_factor_threshold=0.7) # 创建一个小容量哈希表以便观察扩容
print(f"哈希表初始容量: {
ht_resizable._capacity}, 阈值: {
ht_resizable._load_factor_threshold}") # 打印初始状态
keys_to_add = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] # 准备要添加的键
for key in keys_to_add:
print(f"
插入键 '{
key}'...") # 打印插入操作
value = ord(key) # 用字符的ASCII码作为值
ht_resizable[key] = value # 执行插入
print(f"插入后大小: {
len(ht_resizable)}, 容量: {
ht_resizable._capacity}, 负载因子: {
ht_resizable._get_load_factor():.2f}") # 打印插入后的状态
当你运行这个脚本时，你会观察到：
前几个元素（‘a’, ‘b’, ‘c’）被正常插入。
当插入第4个元素 ‘d’ 时，size变为4，容量为5，负载因子 4/5 = 0.8，超过了我们设置的阈值0.7。
此时，_resize方法会被自动触发，哈希表的容量会从5擴展到10。
旧的4个元素会被重新哈希并放入这个容量为10的新表中。
后续的元素’e’, ‘f’, 'g’会继续被插入，直到负载因子再次达到阈值。
这个动态扩容的机制，正是Python的dict和set能够在各种规模下都保持惊人性能的秘密武器。
3.4 Python的dict和set：站在巨人的肩膀上
我们花费了大量篇幅从零开始构建哈希表，目的就是为了让你能够深刻理解Python中dict和set这两个无处不在的核心数据类型的内部工作原理。
dict (字典): 就是一个实现了我们上述所有机制（哈希函数、冲突解决、动态扩容）的、高度优化的哈希表。它的key必须是可哈希的（hashable），value可以是任意对象。
set (集合): 可以看作是一个只有key没有value的特殊哈希表。它的主要用途是高效地存储不重复的元素，并进行快速的成员资格检查。
什么是“可哈希的” (Hashable)？
一个对象是可哈希的，必须满足两个条件：
支持hash()函数: 它必须实现一个__hash__()方法，以便内置的hash()函数可以计算出它的哈希值。
值是不可变的 (Immutable): 它的值在生命周期内不能改变。这是因为哈希表的索引是基于key的哈希值计算的。如果一个key在存入哈希表后，其内容发生了改变，那么它的哈希值也可能随之改变，但它在哈希表中的位置却没有变。这将导致我们再也无法通过新的哈希值找到它。
Python中的可哈希与不可哈希类型:
可哈希 (Immutable): int, float, bool, str, tuple, frozenset。
不可哈希 (Mutable): list, dict, set。
# hashable_vs_unhashable.py
my_dict = {
}
# 合法的键
my_dict[100] = "integer key" # 整数是可哈希的
my_dict[3.14] = "float key" # 浮点数是可哈希的
my_dict["hello"] = "string key" # 字符串是可哈希的
my_dict[(1, 'a')] = "tuple key" # 元组是可哈希的，前提是其内部所有元素也都是可哈希的
print("合法的字典:", my_dict) # 打印字典
# 非法的键
try:
my_list_key = [1, 2] # 列表是可变的
my_dict[my_list_key] = "list key" # 尝试用列表作为键
except TypeError as e:
print(f"
尝试用列表作为键，引发了TypeError: {
e}") # 捕获并打印预期的TypeError
try:
my_set_key = {
1, 2} # 集合是可变的
my_dict[my_set_key] = "set key" # 尝试用集合作为键
except TypeError as e:
print(f"尝试用集合作为键，引发了TypeError: {
e}") # 捕获并打印预期的TypeError
Python字典的实现细节（CPython）:
冲突解决: CPython中的dict实现采用的是开放寻址法，但它使用了一种巧妙的随机化探测序列来避免聚集，其效果类似于双重哈希。
扩容策略: 当字典被填满超过2/3时（即负载因子 > 0.66），就会触发扩容。
优化: 从Python 3.6开始，dict的实现被重新设计，使其在保持O(1)性能的同时，还额外保证了插入顺序。这意味着当你遍历一个字典时，元素的顺序会与你插入它们时的顺序保持一致。这是通过维护一个额外的、紧凑的索引数组来实现的，但这部分属于更深层的实现细节。
3.5 哈希函数的应用：超越哈希表
哈希函数的应用远不止于构建哈希表。它“将任意数据映射为固定长度指纹”的特性，使其在很多领域都大放异彩。
应用一：数据完整性校验 (Checksum)
当你从网上下载一个大文件时，网站通常会提供一个MD5、SHA-1或SHA-256的哈希值。这是一种加密哈希函数的输出。
工作原理:
网站对原始文件内容运行SHA-256算法，得到一个唯一的、定长的哈希字符串（指纹）。
你下载文件后，在你的本地计算机上对你下载的文件内容再次运行同一个SHA-256算法。
比较你计算出的哈希值和网站提供的哈希值。
如果两者完全一致，你就可以非常有信心地认为，你下载的文件在传输过程中没有被损坏或篡改。任何一个比特位的改变都会导致最终的哈希值发生天翻地覆的变化（雪崩效应）。
代码示例：计算文件的SHA-256哈希值
# file_checksum.py
import hashlib
import os
def calculate_sha256(filepath):
"""计算一个文件的SHA-256哈希值。"""
sha256_hash = hashlib.sha256() # 创建一个SHA-256哈希对象
try:
with open(filepath, "rb") as f: # 必须以二进制模式("rb")读取文件
# 为了处理大文件，我们分块读取，而不是一次性读入内存
for byte_block in iter(lambda: f.read(4096), b""): # 每次读取4KB的数据块
sha256_hash.update(byte_block) # 将读取的数据块送入哈希对象进行更新
return sha256_hash.hexdigest() # 返回计算出的十六进制哈希字符串
except FileNotFoundError:
return "Error: File not found."
except Exception as e:
return f"An error occurred: {
e}"
# 创建一个临时文件用于测试
test_filename = "my_test_file.txt"
with open(test_filename, "w") as f:
f.write("Hello, this is a test file for hashing.
")
f.write("The content must be exactly the same to get the same hash.
")
# 计算哈希值
file_hash = calculate_sha256(test_filename)
print(f"文件 '{
test_filename}' 的SHA-256哈希值是:") # 打印哈希值
print(file_hash)
# 清理临时文件
os.remove(test_filename)
应用二：密码存储
网站的数据库永远不应该明文存储用户的密码。正确的做法是存储密码的哈希值。
工作原理:
注册: 用户输入密码"pa$$w0rd"。服务器计算 hash("pa$$w0rd")，得到一个哈希值（例如"abc123def456"），然后将这个哈希值存入数据库，与用户名关联。
登录: 用户再次输入密码"pa$$w0rd"。服务器再次对用户输入的密码计算哈希值 hash("pa$$w0rd")，得到"abc123def456"。
比较: 服务器将计算出的新哈希值与数据库中存储的哈希值进行比较。如果一致，则认证通过。
安全性: 即使黑客窃取了整个数据库，他们得到的也只是一堆哈希值，而无法直接知道用户的原始密码，因为哈希函数是单向的，从哈希值反推出原始密码在计算上是不可行的。
加盐 (Salting): 为了防止“彩虹表攻击”（即预先计算好常用密码的哈希值），现代密码存储方案会在计算哈希前，为每个用户的密码添加一个随机的、独一无二的“盐”（salt）字符串。即存储 hash(password + salt)。这样，即使两个用户使用了相同的密码，由于他们的盐不同，最终存储的哈希值也完全不同。
第四章：树形结构（上）—— 深入二叉树与二叉搜索树
告别了线性结构的秩序与哈希表的瞬时魔法，我们即将步入一个更广阔、更具层次感的世界——树形结构。如果说线性结构是“一维”的线，那么树形结构就是“二维”的面，它引入了“层级”和“分支”的概念，使其能够模拟现实世界中无处不在的层级关系，例如公司组织架构、文件系统目录、家族谱系等等。
树形结构是计算机科学的支柱之一，是构建高效搜索、索引和数据库系统的基础。我们将从最基础、最重要的树形结构——二叉树（Binary Tree）——开始，逐步深入到其有序的变体——二叉搜索树（Binary Search Tree, BST），并亲手实现它们的构建、遍历与操作，深刻理解其内在的递归之美与性能权衡。
4.1 树之初：基本概念与术语
在深入代码之前，我们必须先掌握树的通用语言。一棵树是由n（n>=0）个有限节点组成的一个具有层次关系的集合。
节点 (Node): 树的基本组成单位。每个节点包含数据域和指向其子节点的指针。
根节点 (Root): 树的最顶层节点，一棵非空树有且仅有一个根节点。
子节点 (Child): 一个节点的直接下级节点。
父节点 (Parent): 一个节点的直接上级节点。
兄弟节点 (Sibling): 拥有同一个父节点的节点互为兄弟节点。
叶子节点 (Leaf Node): 没有任何子节点的节点，也称为终端节点。
内部节点 (Internal Node): 非根节点且非叶子节点的节点。
边的度 (Degree of an Edge): 连接两个节点的线。
节点的度 (Degree of a Node): 一个节点拥有的子树的数量（即其子节点的数量）。
树的度 (Degree of a Tree): 树中所有节点的度的最大值。
路径 (Path): 从一个节点到另一个节点所经过的节点序列。
路径长度 (Path Length): 路径上边的数量。
节点的层 (Level): 根节点为第1层（有些定义为第0层，本书统一为第1层），其子节点为第2层，以此类推。
节点的深度 (Depth): 从根节点到该节点所经过的唯一路径的长度。根节点的深度为0。
节点的高度 (Height): 从该节点到其最远叶子节点的最长路径的长度。叶子节点的高度为0。
树的高度 (Height of a Tree): 树中所有节点高度的最大值，也即根节点的高度。
子树 (Subtree): 以一个节点的子节点为根的树。
森林 (Forest): m（m>=0）棵互不相交的树的集合。
4.2 二叉树：限制与可能
二叉树（Binary Tree）是一种特殊的树，它的特殊之处在于：树中每个节点的度最多为2。也就是说，每个节点最多有两个子节点，通常我们称之为“左子节点”和“右子节点”。
二叉树的重要性质:
二叉树的第i层，最多有 2^(i-1) 个节点。
高度为h的二叉树，最多有 2^h - 1 个节点。
对于任何一棵二叉树，如果其叶子节点数为n₀，度为2的节点数为n₂，则 n₀ = n₂ + 1。
特殊的二叉树:
满二叉树 (Full Binary Tree): 在一棵二叉树中，如果所有非叶子节点的度都为2，且所有叶子节点都在同一层，则称之为满二叉树。它是一种形态上非常“完美”的树。
完全二叉树 (Complete Binary Tree): 高度为h的二叉树，其前h-1层都是满的，最后一层的节点都从左到右连续排列。满二叉树是一种特殊的完全二叉树。完全二叉树的这个“从左到右不间断”的特性，使其非常适合用数组来存储，我们将在堆（Heap）的章节中详细探讨这种存储方式。
4.2.1 二叉树的节点表示与构建
在Python中，我们通常用一个类来表示二叉树的节点。
# binary_tree_node.py
class TreeNode:
"""定义一个二叉树节点类。"""
def __init__(self, value, left=None, right=None):
self.val = value # 节点存储的值
self.left = left # 指向左子节点的引用
self.right = right # 指向右子节点的引用
def __str__(self):
"""提供一个友好的字符串表示，方便调试。"""
return f"Node({
self.val})"
# 手动构建一棵简单的二叉树
# A
# /
# B C
# / /
# D E F
# 从叶子节点开始创建
node_d = TreeNode('D')
node_e = TreeNode('E')
node_f = TreeNode('F')
# 创建它们的父节点
node_b = TreeNode('B', left=node_d) # B的左孩子是D
node_c = TreeNode('C', left=node_e, right=node_f) # C的左孩子是E，右孩子是F
# 创建根节点
root = TreeNode('A', left=node_b, right=node_c) # A的左孩子是B，右孩子是C
# 验证一下结构
print(f"根节点是: {
root}") # 打印根节点
print(f"根节点的左孩子是: {
root.left}") # 打印根节点的左孩子
print(f"根节点的右孩子是: {
root.right}") # 打印根节点的右孩子
print(f"{
root.left}的左孩子是: {
root.left.left}") # 打印B的左孩子
print(f"{
root.right}的右孩子是: {
root.right.right}") # 打印C的右孩子
4.3 树的灵魂：递归遍历
如何访问树中的每一个节点，且每个节点只访问一次？这个过程称为树的遍历 (Tree Traversal)。与线性结构简单的从头到尾遍历不同，树的遍历充满了递归的智慧。二叉树最核心、最基础的三种遍历方式都以根节点的访问时机来命名：前序、中序和后序。
这三种遍历方式，其递归结构几乎完全相同，唯一的区别就是print(node.val)（即访问根节点）这行代码的位置。
4.3.1 前序遍历 (Pre-order Traversal): 根-左-右
遍历顺序：
访问当前节点（根）。
递归地前序遍历左子树。
递归地前序遍历右子树。
前序遍历常用于创建树的副本或序列化树，因为它首先处理根节点，可以确定结构。
代码实现：递归与迭代
# tree_traversal.py
# (假设TreeNode类已定义)
class TreeNode:
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right
# --- 递归实现 ---
def preorder_traversal_recursive(node, result_list):
"""递归地实现前序遍历。"""
if node is None: # 递归的基线条件：如果节点为空，则返回
return
# 1. 访问根节点
result_list.append(node.val) # 将当前节点的值加入结果列表
# 2. 递归遍历左子树
preorder_traversal_recursive(node.left, result_list) # 递归调用左子树
# 3. 递归遍历右子树
preorder_traversal_recursive(node.right, result_list) # 递归调用右子树
# --- 迭代实现 (使用栈) ---
def preorder_traversal_iterative(root):
"""使用栈来迭代地实现前序遍历。"""
if not root: # 如果根节点为空，返回空列表
return []
result = [] # 存储遍历结果
stack = [root] # 初始化栈，并将根节点压入
while stack: # 当栈不为空时循环
# 从栈顶弹出一个节点进行处理
node = stack.pop() # 弹出节点
result.append(node.val) # 访问该节点，将其值加入结果
# 关键：先压入右子节点，再压入左子节点！
# 因为栈是后进先出，所以后压入的左子节点会先被处理。
if node.right: # 如果右子节点存在
stack.append(node.right) # 将右子节点压入栈
if node.left: # 如果左子节点存在
stack.append(node.left) # 将左子节点压入栈
return result
# --- 构建测试树 ---
# 1
# /
# 2 3
# /
# 4 5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
# --- 测试 ---
print("--- 前序遍历 (根-左-右) ---")
# 递归方式
recursive_result = []
preorder_traversal_recursive(root, recursive_result)
print(f"递归实现结果: {
recursive_result}") # 预期: [1, 2, 4, 5, 3]
# 迭代方式
iterative_result = preorder_traversal_iterative(root)
print(f"迭代实现结果: {
iterative_result}") # 预期: [1, 2, 4, 5, 3]
迭代法剖析: 迭代遍历的核心是使用栈来模拟递归的函数调用栈。前序遍历的迭代法非常直观：
处理（访问）当前节点。
将其右孩子和左孩子（如果存在）先后压入栈中。
这样，下一次循环从栈顶弹出的自然就是左孩子，实现了“根-左-右”的顺序。
4.3.2 中序遍历 (In-order Traversal): 左-根-右
遍历顺序：
递归地中序遍历左子树。
访问当前节点（根）。
递归地中序遍历右子树。
对于二叉搜索树（我们稍后会讲），中序遍历会得到一个有序的节点序列，这是它最重要的应用。
代码实现：递归与迭代
# (继续在 tree_traversal.py 中添加)
# --- 递归实现 ---
def inorder_traversal_recursive(node, result_list):
"""递归地实现中序遍历。"""
if node is None: # 基线条件
return
# 1. 递归遍历左子树
inorder_traversal_recursive(node.left, result_list) # 先处理左子树
# 2. 访问根节点
result_list.append(node.val) # 然后处理根节点
# 3. 递归遍历右子树
inorder_traversal_recursive(node.right, result_list) # 最后处理右子树
# --- 迭代实现 (使用栈) ---
def inorder_traversal_iterative(root):
"""使用栈来迭代地实现中序遍历。"""
if not root:
return []
result = []
stack = []
current = root # 使用一个current指针来追踪当前节点
while current or stack: # 当current不为空或栈不为空时循环
# 1. 将所有左子节点一路压入栈中
while current: # 只要当前节点存在
stack.append(current) # 就将其压入栈
current = current.left # 然后继续向其左子树深入
# 2. 当无法再往左走时（current变为None），从栈顶弹出一个节点
# 这个弹出的节点，是当前子树中“最左”的节点
node = stack.pop() # 弹出节点
result.append(node.val) # 访问这个节点 (处理根)
# 3. 将current指针转向该节点的右子树，准备处理右子树
current = node.right # 转向右子树
return result
# --- 测试 ---
print("
--- 中序遍历 (左-根-右) ---")
# 递归方式
recursive_result_inorder = []
inorder_traversal_recursive(root, recursive_result_inorder)
print(f"递归实现结果: {
recursive_result_inorder}") # 预期: [4, 2, 5, 1, 3]
# 迭代方式
iterative_result_inorder = inorder_traversal_iterative(root)
print(f"迭代实现结果: {
iterative_result_inorder}") # 预期: [4, 2, 5, 1, 3]
迭代法剖析: 中序遍历的迭代法比前序要稍微复杂一点，它完美地模拟了“先一路向左，到底后处理，再转向右边”的逻辑：
使用current指针，一路向左，将沿途所有节点压入栈。
当current为空时，说明左边走到了尽头。此时从栈顶弹出的节点，就是需要被“访问”的节点。
访问该节点后，将current指针指向它的右孩子，开始对右子树重复上述过程。
4.3.3 后序遍历 (Post-order Traversal): 左-右-根
遍历顺序：
递归地后序遍历左子树。
递归地后序遍历右子树。
访问当前节点（根）。
后序遍历常用于计算依赖于子节点结果的表达式树或安全地释放树的内存（因为必须先释放子节点才能释放父节点）。
代码实现：递归与迭代
# (继续在 tree_traversal.py 中添加)
# --- 递归实现 ---
def postorder_traversal_recursive(node, result_list):
"""递归地实现后序遍历。"""
if node is None: # 基线条件
return
# 1. 递归遍历左子树
postorder_traversal_recursive(node.left, result_list) # 先处理左子树
# 2. 递归遍历右子树
postorder_traversal_recursive(node.right, result_list) # 再处理右子树
# 3. 访问根节点
result_list.append(node.val) # 最后处理根节点
# --- 迭代实现 (巧妙利用前序遍历) ---
def postorder_traversal_iterative(root):
"""使用栈来迭代地实现后序遍历。"""
if not root:
return []
result = []
stack = [root]
# 后序遍历是 "左-右-根"
# 其逆序是 "根-右-左"
# 这个 "根-右-左" 的顺序与前序遍历 "根-左-右" 非常相似！
# 我们只需要修改前序遍历的迭代代码，将压栈顺序改为先左后右即可。
while stack:
node = stack.pop()
result.append(node.val) # 访问根
# 与前序遍历相反，先压入左子节点
if node.left:
stack.append(node.left)
# 再压入右子节点
if node.right:
stack.append(node.right)
# 最后，将得到的 "根-右-左" 结果列表反转，就得到了 "左-右-根"
return result[::-1] # 反转列表
# --- 测试 ---
print("
--- 后序遍历 (左-右-根) ---")
# 递归方式
recursive_result_postorder = []
postorder_traversal_recursive(root, recursive_result_postorder)
print(f"递归实现结果: {
recursive_result_postorder}") # 预期: [4, 5, 2, 3, 1]
# 迭代方式
iterative_result_postorder = postorder_traversal_iterative(root)
print(f"迭代实现结果: {
iterative_result_postorder}") # 预期: [4, 5, 2, 3, 1]
迭代法剖析: 直接实现后序遍历的迭代法比较复杂，因为它需要在处理完右子树后才能处理根，需要判断一个节点是从左子树返回还是从右子树返回。上面提供的是一种非常讨巧且易于理解的方法：
我们观察到后序左-右-根的逆序是根-右-左。
这个根-右-左的顺序和前序根-左-右非常像，我们只需要交换前序迭代法中左右子节点的压栈顺序即可实现。
最后，将得到的根-右-左的结果列表整个反转，就得到了我们想要的后序遍历结果。
4.4 二叉搜索树 (BST)：有序的魔法
普通的二叉树，节点的值是任意存放的，查找一个特定值需要遍历整棵树，时间复杂度是O(n)。为了提高查找效率，我们引入了二叉搜索树（Binary Search Tree, BST）。
BST是一种特殊的二叉树，它对节点的值施加了一个严格的排序约束：
对于树中的任意一个节点node：
其左子树中所有节点的值，都小于node的值。
其右子树中所有节点的值，都大于node的值。
其左、右子树也分别是二叉搜索树。
这个简单的约束，赋予了BST强大的能力。它结合了链表（插入删除相对灵活）和有序数组（查找高效）的优点。
4.4.1 BST的核心操作：查找、插入与删除
A. 查找 (Search)
BST的查找过程，类似于一个“决策树”或“二分查找”的过程。
从根节点开始。
如果当前节点的值等于目标值，查找成功。
如果目标值小于当前节点的值，则在左子树中继续查找。
如果目标值大于当前节点的值，则在右子树中继续查找。
如果走到了None（空节点），说明树中不存在该目标值。
B. 插入 (Insert)
插入过程与查找非常类似。
从根节点开始，按照查找的路径向下走，直到找到一个空位（None）。
将新节点插入到这个空位上。
C. 删除 (Delete)
删除是BST中最复杂的操作，因为它必须在删除节点后，依然保持BST的性质。需要分三种情况讨论：
要删除的节点是叶子节点: 直接删除即可，将其父节点的对应指针（left或right）设为None。
要删除的节点只有一个子节点: 将其父节点的对应指针，直接指向它的那个唯一子节点（实现“跳过”）。
要删除的节点有两个子节点 (最复杂的情况):
a. 在其右子树中，找到最小的节点（这个节点被称为该节点的“中序后继”，In-order Successor）。这个“最小”节点一定在右子树的最左边。
b. 或者，在其左子树中，找到最大的节点（被称为“中序前驱”，In-order Predecessor）。
c. 用这个“后继”或“前驱”节点的值，替换掉要删除节点的值。
d. 最后，删除那个被用来替换的“后继”或“前驱”节点。由于这个后继/前驱节点最多只有一个（右）子节点，所以删除它就转化为了前面更简单的Case 1或Case 2。
4.4.2 从零开始实现一个二叉搜索树
# binary_search_tree.py
class TreeNode: # 复用之前的TreeNode类
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right
class BinarySearchTree:
"""定义一个二叉搜索树类，并实现其核心操作。"""
def __init__(self):
self.root = None # 初始化根节点为空
def insert(self, value):
"""向BST中插入一个新值。"""
if self.root is None: # 如果树是空的
self.root = TreeNode(value) # 新节点就是根节点
else:
self._insert_recursive(self.root, value) # 调用递归辅助函数
def _insert_recursive(self, current_node, value):
"""插入操作的递归辅助函数。"""
if value < current_node.val: # 如果新值小于当前节点值
if current_node.left is None: # 如果左子节点为空
current_node.left = TreeNode(value) # 直接插入
else:
self._insert_recursive(current_node.left, value) # 否则，在左子树中继续递归插入
elif value > current_node.val: # 如果新值大于当前节点值
if current_node.right is None: # 如果右子节点为空
current_node.right = TreeNode(value) # 直接插入
else:
self._insert_recursive(current_node.right, value) # 否则，在右子树中继续递归插入
# 如果 value == current_node.val，则什么都不做（不允许重复值）
def search(self, value):
"""在BST中查找一个值。"""
return self._search_recursive(self.root, value) # 调用递归辅助函数
def _search_recursive(self, current_node, value):
"""查找操作的递归辅助函数。"""
if current_node is None: # 如果走到了空节点，说明没找到
return False
if current_node.val == value: # 如果找到了
return True
elif value < current_node.val: # 如果目标值更小
return self._search_recursive(current_node.left, value) # 在左子树中查找
else: # 如果目标值更大
return self._search_recursive(current_node.right, value) # 在右子树中查找
def delete(self, value):
"""从BST中删除一个值。"""
self.root = self._delete_recursive(self.root, value) # 调用递归辅助函数
def _find_min_node(self, node):
"""在一个子树中找到最小值的节点（一路向左）。"""
current = node
while current.left:
current = current.left
return current
def _delete_recursive(self, current_node, value):
"""删除操作的递归辅助函数。"""
if current_node is None: # 如果没找到要删除的值
return None # 返回None
# 1. 寻找要删除的节点
if value < current_node.val:
current_node.left = self._delete_recursive(current_node.left, value)
elif value > current_node.val:
current_node.right = self._delete_recursive(current_node.right, value)
else: # 找到了要删除的节点 (current_node.val == value)
# 2. 根据子节点情况执行删除
# Case 1: 叶子节点 或 只有一个子节点
if current_node.left is None:
return current_node.right # 返回右子节点（或None）作为新的子树
if current_node.right is None:
return current_node.left # 返回左子节点（或None）作为新的子树
# Case 2: 有两个子节点
# 找到右子树中的最小节点（中序后继）
successor = self._find_min_node(current_node.right)
# 用后继节点的值替换当前节点的值
current_node.val = successor.val
# 在右子树中删除那个后继节点（这会转化为Case 1）
current_node.right = self._delete_recursive(current_node.right, successor.val)
return current_node
def inorder_traversal(self):
"""执行中序遍历，应该得到一个有序序列。"""
result = []
self._inorder_recursive(self.root, result)
return result
def _inorder_recursive(self, node, result_list):
if node:
self._inorder_recursive(node.left, result_list)
result_list.append(node.val)
self._inorder_recursive(node.right, result_list)
# --- 使用我们自己实现的BST ---
bst = BinarySearchTree()
nodes_to_insert = [50, 30, 70, 20, 40, 60, 80] # 准备插入的节点值
for val in nodes_to_insert:
bst.insert(val) # 逐个插入
print("构建BST后的中序遍历结果 (应该是有序的):")
print(bst.inorder_traversal()) # 打印中序遍历结果
print(f"
查找 40: {
'找到' if bst.search(40) else '未找到'}") # 查找存在的值
print(f"查找 100: {
'找到' if bst.search(100) else '未找到'}") # 查找不存在的值
print("
--- 删除操作演示 ---")
print("删除叶子节点 20...") # 演示删除叶子节点
bst.delete(20)
print(f"删除后的中序遍历: {
bst.inorder_traversal()}")
print("
删除只有一个子节点的节点 70 (假设先删掉80)...") # 演示删除只有一个子节点的节点
bst.delete(80) # 先删除80，让70只有一个左孩子60
bst.delete(70)
print(f"删除后的中序遍历: {
bst.inorder_traversal()}")
print("
删除有两个子节点的节点 50 (根节点)...") # 演示删除有两个子节点的节点
bst.insert(80) # 先把80加回来，让60的父节点70重新有右子节点
bst.insert(70) # 重新插入70和80，恢复树的结构，再删除根节点
bst.delete(50)
print(f"删除后的中序遍历: {
bst.inorder_traversal()}")
print(f"新的根节点的值是: {
bst.root.val}") # 打印新的根节点值
4.4.3 BST的性能：最好与最坏
查找、插入、删除的时间复杂度:
最好情况/平均情况: O(h)，其中h是树的高度。在一个平衡的（Balanced）BST中，节点大致均匀分布在两侧，其高度h约等于log₂(n)。因此，在平衡状态下，BST的性能非常出色，为O(log n)。
最坏情况: O(n)。如果插入的节点序列是有序的（例如，[10, 20, 30, 40, 50]），BST会退化成一个链表。树的高度h等于节点数n，所有操作都变成了线性扫描。
BST退化的风险，是它最大的软肋。如何防止BST退化，在任何情况下都维持其O(log n)的性能？
第五章：自平衡二叉搜索树 —— 旋转的艺术
我们领略了二叉搜索树（BST）的有序之美，它通过简单的规则（左小右大）实现了高效的O(h)级别查找。然而，我们也看到了它致命的弱点：在最坏的情况下，BST会因有序数据的连续插入而退化成一个高度为n的链表，其所有操作的性能也随之骤降至O(n). 这在需要性能稳定性的现实世界应用中是不可接受的。我们能否构建一种“更聪明”的二叉搜索树，让它能够自我监督、自我修复，无论我们如何插入或删除数据，它都能始终保持一个相对“矮胖”的平衡形态，从而将O(h)永远维持在O(log n)的水平？
答案是肯定的。这便是**自平衡二叉搜索树（Self-balancing Binary Search Tree）**的使命。这类数据结构的核心思想是：在每次执行插入或删除操作后，都会进行一次“体检”，检查树的“平衡”是否被破坏。一旦发现不平衡，它就会通过一系列精巧的局部重构操作——旋转（Rotation）——来恢复平衡。
5.1 AVL树：追求极致平衡的完美主义者
AVL树的名字来源于其两位发明者：Georgy Adelson-Velsky 和 Evgenii Landis。它是有史以来第一个被发明的自平衡二叉搜索树。AVL树对“平衡”的定义非常苛刻，它要求树中的每一个节点，其左子树的高度与右子树的高度之差的绝对值不能超过1。
5.1.1 平衡因子（Balance Factor）
为了量化节点的平衡状态，我们引入一个概念：平衡因子（Balance Factor）。
BalanceFactor(node) = Height(node.left) - Height(node.right)
根据AVL树的定义，对于树中的任意一个节点node，其BalanceFactor(node)的值只可能为 -1, 0, 或 1。
-1: 右子树比左子树高1。
0: 左右子树等高。
1: 左子树比右子树高1。
如果任何一个节点的平衡因子变成了-2或+2，我们就说这棵树失去了平衡，需要立即进行修复。
5.1.2 失衡的根源：四种失衡场景
一次插入或删除操作，最多只会影响从操作节点到根节点的路径上的节点的平衡因子。当我们沿着这条路径回溯检查时，第一个发现其平衡因子变为+2或-2的节点，我们称之为失衡节点。失衡的根本原因，可以归结为以下四种情况，它们的命名揭示了导致失衡的新节点插入路径：
左-左 (Left-Left, LL): 新节点被插入到了失衡节点的左孩子的左子树上。这使得失衡节点的左子树比右子树高了2。
右-右 (Right-Right, RR): 新节点被插入到了失衡节点的右孩子的右子树上。这使得失衡节点的右子树比左子树高了2。
左-右 (Left-Right, LR): 新节点被插入到了失衡节点的左孩子的右子树上。这是一个“拐弯”的路径。
右-左 (Right-Left, RL): 新节点被插入到了失衡节点的右孩子的左子树上。这也是一个“拐弯”的路径。
5.1.3 恢复平衡的魔法：旋转操作
旋转是AVL树的灵魂，它是一种能改变树的局部结构，同时保持二叉搜索树性质（左小右大）的操作。通过旋转，我们可以降低较高子树的高度，增加较低子树的高度，从而恢复平衡。
A. 右旋 (Right Rotation)
右旋用于解决**左-左 (LL)**失衡。它作用于失衡节点。可以想象成以失衡节点的左孩子为轴，将失衡节点“向右”旋转下来。
场景: 节点y因为其左孩子x的左子树（T1）过高而失衡（平衡因子为+2）。
操作前:
y (+2)
/
x T3
/
T1 T2
BST性质: T1 < x < T2 < y < T3
操作:
y的左指针不再指向x，而是指向x的右子树T2。
x的右指针不再指向T2，而是指向y。
x成为新的子树根节点。
操作后:
x
/
T1 y
/
T2 T3
BST性质检查: T1 < x < T2 < y < T3。性质依然保持！
高度变化: T1的高度没变，但y的高度降低了1，x的高度增加了1。原本过高的左侧被“提”了上来，恢复了平衡。
B. 左旋 (Left Rotation)
左旋与右旋完全对称，用于解决**右-右 (RR)**失衡。它作用于失衡节点。可以想象成以失衡节点的右孩子为轴，将失衡节点“向左”旋转下来。
场景: 节点y因为其右孩子x的右子树（T3）过高而失衡（平衡因子为-2）。
操作前:
y (-2)
/
T1 x
/
T2 T3
BST性质: T1 < y < T2 < x < T3
操作:
y的右指针不再指向x，而是指向x的左子树T2。
x的左指针不再指向T2，而是指向y。
x成为新的子树根节点。
操作后:
x
/
y T3
/
T1 T2
BST性质检查: T1 < y < T2 < x < T3。性质依然保持！
高度变化: T3的高度没变，但y的高度降低了1，x的高度增加了1。原本过高的右侧被“提”了上来，恢复了平衡。
C. 左-右 (LR) 旋转
LR旋转用于解决**左-右 (LR)**失衡。它不能通过一次旋转解决，而需要一个组合拳：先左旋，再右旋。
场景: 节点z因为其左孩子y的右子树过高而失衡。新节点插入到了y的右孩子x的子树（T2或T3）中。
操作前:
z (+2)
/
y T4
/
T1 x
/
T2 T3
BST性质: T1 < y < T2 < x < T3 < z < T4
操作:
第一步：对y进行一次左旋。 这会将y-x子树变成一个标准的“左-左”结构。
z (+2)
/
x T4
/
y T3
/
T1 T2
第二步：对z进行一次右旋。 这就和我们之前讲的LL情况完全一样了。
x
/
y z
/ /
T1 T2 T3 T4
BST性质检查: T1 < y < T2 < x < T3 < z < T4。性质依然保持！
高度变化: 原本“拐弯”的结构被拉直，并恢复了平衡。
D. 右-左 (RL) 旋转
RL旋转与LR旋转完全对称，用于解决**右-左 (RL)**失衡。它也需要一个组合拳：先右旋，再左旋。
场景: 节点z因为其右孩子y的左子树过高而失衡。
操作前:
z (-2)
/
T1 y
/
x T4
/
T2 T3
BST性质: T1 < z < T2 < x < T3 < y < T4
操作:
第一步：对y进行一次右旋。
z (-2)
/
T1 x
/
T2 y
/
T3 T4
第二步：对z进行一次左旋。
x
/
z y
/ /
T1 T2 T3 T4
BST性质检查: T1 < z < T2 < x < T3 < y < T4。性质依然保持！
5.1.4 AVL树的Python实现
现在，我们将理论付诸实践，从零开始构建一个功能完备的AVL树。
# avl_tree.py
class AVLNode:
"""定义一个AVL树节点类，比普通节点多了height属性。"""
def __init__(self, value):
self.val = value # 节点存储的值
self.left = None # 指向左子节点的引用
self.right = None # 指向右子节点的引用
self.height = 1 # 节点的高度，新插入的叶子节点高度为1
class AVLTree:
"""定义一个AVL树类，并实现其核心操作。"""
def get_height(self, node):
"""获取一个节点的高度，如果节点为空则高度为0。"""
if not node:
return 0
return node.height
def get_balance(self, node):
"""计算一个节点的平衡因子。"""
if not node:
return 0
# 平衡因子 = 左子树高度 - 右子树高度
return self.get_height(node.left) - self.get_height(node.right)
def right_rotate(self, y):
"""
对节点y进行右旋操作。
y是失衡的节点。
y
/
x T3
/
T1 T2
旋转后变为:
x
/
T1 y
/
T2 T3
"""
print(f"对节点 {
y.val} 进行右旋...")
x = y.left # x是y的左孩子
T2 = x.right # T2是x的右子树
# 执行旋转
x.right = y # x的右孩子变为y
y.left = T2 # y的左孩子变为T2
# 更新高度: 必须先更新y的高度，再更新x的高度，因为x的高度依赖于更新后的y
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
# 返回旋转后新的子树根节点
return x
def left_rotate(self, y):
"""
对节点y进行左旋操作。
y是失衡的节点。
y
/
T1 x
/
T2 T3
旋转后变为:
x
/
y T3
/
T1 T2
"""
print(f"对节点 {
y.val} 进行左旋...")
x = y.right # x是y的右孩子
T2 = x.left # T2是x的左子树
# 执行旋转
x.left = y # x的左孩子变为y
y.right = T2 # y的右孩子变为T2
# 更新高度
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
# 返回旋转后新的子树根节点
return x
def insert(self, root, value):
"""
递归地向AVL树中插入一个值，并返回新的树根。
"""
# 1. 执行标准的BST插入
if not root: # 如果当前节点为空，则创建新节点并返回
return AVLNode(value)
elif value < root.val: # 如果值小于当前节点，向左子树递归插入
root.left = self.insert(root.left, value)
else: # 如果值大于等于当前节点，向右子树递归插入
root.right = self.insert(root.right, value)
# 2. 更新祖先节点的高度
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
# 3. 获取平衡因子，检查是否失衡
balance = self.get_balance(root)
# 4. 如果失衡，则进行旋转操作
# Case 1: 左-左 (LL)
if balance > 1 and value < root.left.val:
return self.right_rotate(root)
# Case 2: 右-右 (RR)
if balance < -1 and value > root.right.val:
return self.left_rotate(root)
# Case 3: 左-右 (LR)
if balance > 1 and value > root.left.val:
root.left = self.left_rotate(root.left) # 先对左孩子进行左旋
return self.right_rotate(root) # 再对根节点进行右旋
# Case 4: 右-左 (RL)
if balance < -1 and value < root.right.val:
root.right = self.right_rotate(root.right) # 先对右孩子进行右旋
return self.left_rotate(root) # 再对根节点进行左旋
# 如果没有失衡，直接返回当前节点
return root
def get_min_value_node(self, node):
"""找到一个子树中的最小节点 (用于删除操作)。"""
if node is None or node.left is None:
return node
return self.get_min_value_node(node.left)
def delete(self, root, value):
"""
递归地从AVL树中删除一个值，并返回新的树根。
"""
# 1. 执行标准的BST删除
if not root:
return root
elif value < root.val:
root.left = self.delete(root.left, value)
elif value > root.val:
root.right = self.delete(root.right, value)
else: # 找到了要删除的节点
if root.left is None: # 如果左孩子为空
temp = root.right
root = None
return temp
elif root.right is None: # 如果右孩子为空
temp = root.left
root = None
return temp
# 如果有两个孩子，找到中序后继节点
temp = self.get_min_value_node(root.right)
root.val = temp.val # 用后继节点的值覆盖当前节点
root.right = self.delete(root.right, temp.val) # 删除那个后继节点
# 如果树在删除后变为空（只有一个节点被删了）
if root is None:
return root
# 2. 更新高度
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
# 3. 获取平衡因子
balance = self.get_balance(root)
# 4. 如果失衡，进行旋转 (逻辑与插入类似，但判断条件略有不同)
# Case 1: 左-左 (LL)
if balance > 1 and self.get_balance(root.left) >= 0:
return self.right_rotate(root)
# Case 2: 右-右 (RR)
if balance < -1 and self.get_balance(root.right) <= 0:
return self.left_rotate(root)
# Case 3: 左-右 (LR)
if balance > 1 and self.get_balance(root.left) < 0:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Case 4: 右-左 (RL)
if balance < -1 and self.get_balance(root.right) > 0:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def inorder_traversal(self, root):
"""辅助函数，用于中序遍历并返回节点值列表。"""
res = []
if root:
res = self.inorder_traversal(root.left)
res.append(root.val)
res = res + self.inorder_traversal(root.right)
return res
# --- 使用我们自己实现的AVL树 ---
my_avl_tree = AVLTree()
root = None
# 演示LL失衡和右旋
print("--- 插入 30, 20, 10 (触发LL失衡) ---")
root = my_avl_tree.insert(root, 30)
root = my_avl_tree.insert(root, 20)
root = my_avl_tree.insert(root, 10) # 插入10后，30的平衡因子变为+2，触发LL
print(f"平衡后的中序遍历: {
my_avl_tree.inorder_traversal(root)}")
print(f"新的根节点是: {
root.val}
") # 根节点应变为20
# 演示RR失衡和左旋
print("--- 插入 40, 50 (触发RR失衡) ---")
root = my_avl_tree.insert(root, 40)
root = my_avl_tree.insert(root, 50) # 插入50后，30的平衡因子变为-2，触发RR
print(f"平衡后的中序遍历: {
my_avl_tree.inorder_traversal(root)}")
print(f"子树根节点(30的父节点)是: {
root.right.val}
") # 30的父节点应变为40
# 演示LR失衡和左右双旋
print("--- 插入 5 (触发LR失衡) ---")
# 当前树结构 (简化):
# 20
# /
# 10 40
# /
# 30 50
#
# 先插入 15, 使 10 的右边有节点
root = my_avl_tree.insert(root, 15)
# 再插入 5, 让 10 的左边也失衡
root = my_avl_tree.insert(root, 5)
# 再插入 3, 让 5 的左边失衡，导致 10 成为失衡点
# root = my_avl_tree.insert(root, 3) # 这里为了简化，我们直接在 15 旁边插入
# 假设我们插入 12, 会导致 10 的LR失衡
# 插入 12 到 15 的左边
# 10
# /
# 5 15
# /
# 12 <-- 插入这个
# 10 的平衡因子是 +2, 其左孩子 5 的平衡因子是 -1 (假设插入的是12)
# 这里我们用一个更经典的例子
# 清空树，重新构造LR场景
root = None
print("清空树，重新构造LR场景: 插入 30, 10, 20")
root = my_avl_tree.insert(root, 30)
root = my_avl_tree.insert(root, 10)
root = my_avl_tree.insert(root, 20) # 插入20后，30处发生LR失衡
print(f"平衡后的中序遍历: {
my_avl_tree.inorder_traversal(root)}")
print(f"新的根节点是: {
root.val}
") # 根节点应变为20
# 演示删除操作
print("--- 删除 10, 30 (触发重新平衡) ---")
root = my_avl_tree.delete(root, 10)
print(f"删除10后的中序遍历: {
my_avl_tree.inorder_traversal(root)}")
root = my_avl_tree.delete(root, 30) # 删除后只剩20
print(f"删除30后的中序遍历: {
my_avl_tree.inorder_traversal(root)}")
print(f"最后的根节点是: {
root.val}
")
通过AVL树，我们第一次看到了算法如何通过精巧的设计，来主动维持自身的高效性。它对平衡的极致追求，保证了任何操作都可以在O(log n)时间内完成，为性能提供了坚如磐石的保障。然而，这种严格的平衡策略也带来了一定的代价：为了维持平衡，插入和删除操作可能需要进行多次（尽管是常数次）旋转，这在写操作非常频繁的场景下，可能会比那些对平衡要求稍稍“宽松”的树要慢一些。
5.2 红黑树：在性能与平衡间的优雅舞蹈
如果说AVL树是一位严格的、追求完美体态的芭蕾舞者，那么红黑树（Red-Black Tree, RBT）则更像是一位经验丰富的现代舞者，它懂得在严格的规则（平衡）与自由的表达（性能）之间找到一个最佳的平衡点。红黑树对平衡的追求不像AVL树那样苛刻，它允许一定程度的“不完美”，但正是这种宽容，使得它在插入和删除节点时，需要进行的“调整动作”（旋转）次数大大减少，从而在频繁写入的场景中获得了更高的效率。
这种卓越的工程权衡，使得红黑树成为了工业界应用最广泛的自平衡二叉搜索树。从你使用的操作系统的内核调度器，到C++的std::map和std::set，再到Java的TreeMap和TreeSet，其背后都闪耀着红黑树的身影。
5.2.1 红黑树的五条核心法则
红黑树的“平衡”不是通过节点高度来直接定义的，而是通过五条看似简单却蕴含深意的规则来间接保证的。一棵合法的红黑树，必须同时满足以下所有性质：
颜色法则: 每个节点要么是红色，要么是黑色。
根节点法则: 根节点永远是黑色。
叶子节点法则: 所有的叶子节点（在红黑树的定义中，叶子节点特指NIL或NULL节点，即外部空节点）都是黑色。
红色法则: 如果一个节点是红色的，那么它的两个子节点必须都是黑色的。这条规则反过来也意味着：从根到叶子的任何路径上，都不会出现两个连续的红色节点。这是红黑树最重要的性质之一。
黑色高度法则: 对于树中的任意一个节点，从该节点到其所有后代叶子节点的每一条简单路径上，所包含的黑色节点数量都必须相同。这个共享的黑色节点数，被称为该节点的黑高（Black-Height）。
这些法则是如何保证平衡的？
这五条规则的精妙组合，共同限制了树的高度。虽然它不保证树是绝对平衡的，但它保证了从根节点到最远叶子节点的最长路径，不会超过到最近叶子节点的最短路径的两倍长。
最短路径: 一条路径全是黑色节点（这是可能的）。其长度为根节点的黑高 bh(root)。
最长路径: 根据“红色法则”，路径上不能有两个连续的红色节点，所以最长的情况就是黑色和红色节点交替出现。其路径上最多有 bh(root) 个红色节点。因此，最长路径的长度最多为 bh(root) + bh(root) = 2 * bh(root)。
这个“最长路径不超过最短路径两倍”的特性，足以证明红黑树的高度h始终维持在O(log n)的量级，从而保证了其所有操作的高效性。
5.2.2 红黑树的插入操作：变色与旋转的协同
红黑树的插入操作比AVL树要复杂，因为它涉及到颜色和结构的双重调整。其核心思想是：
初步插入: 按照标准BST的规则找到插入位置，并将新节点作为红色插入。
为什么是红色？ 因为插入黑色节点会立刻违反“黑色高度法则”（路径上的黑色节点数变了），修复起来非常麻烦。而插入红色节点，只会可能违反“红色法则”（出现了连续的红色节点）或“根节点法则”（如果插入的是根节点），这两种情况相对更容易修复。
插入后修复 (Insert Fixup): 从新插入的节点z开始，检查并修复可能被破坏的红黑性质。修复过程是一个循环，它依赖于z的**叔叔节点（Uncle）**的颜色。
我们用z表示当前节点，p表示其父节点，g表示其祖父节点，u表示其叔叔节点。
修复的三大场景 (基于叔叔节点的颜色):
场景一：叔叔节点 u 是红色
这是最简单的情况。它意味着祖父节点g一定是黑色的（因为p和u都是红色）。
操作:
将父节点p变为黑色。
将叔叔节点u变为黑色。
将祖父节点g变为红色。
结果:
g的左右子树的黑色高度都保持不变（一红变黑，一黑变红）。
但是，新变红的g节点可能会和它的父节点（g的父节点）形成连续的红色，违反“红色法则”。
因此，我们将g视为新的z，继续向上回溯，重复修复过程。这个操作就像把问题“向上推”了一层。
G(黑) G(红) <-- g作为新的z，继续向上检查
/ /
P(红) U(红) --> P(黑) U(黑)
/ /
Z(红) Z(红)
场景二：叔叔节点 u 是黑色，且当前形成了“三角”结构 (LR 或 RL)
这对应于AVL树中的LR和RL失衡。
子场景 LR: z是父节点p的右孩子，而p是祖父节点g的左孩子。
操作:
以p为轴进行一次左旋。
旋转后，原先的p节点成了新的z节点，整个结构从“三角”变成了“直线”（LL）。
接下来就进入场景三。
子场景 RL: z是父节点p的左孩子，而p是祖父节点g的右孩子。
操作:
以p为轴进行一次右旋。
旋转后，结构从“三角”变成了“直线”（RR）。
接下来就进入场景三。
G(黑) G(黑)
/ /
P(红) U(黑) 左旋(P) Z(红) U(黑) <-- 变成LL直线结构
--> /
Z(红) P(红)
场景三：叔叔节点 u 是黑色，且当前形成了“直线”结构 (LL 或 RR)
这是修复过程的终点，执行完这一步，整棵树将恢复平衡。
操作:
将父节点p变为黑色。
将祖父节点g变为红色。
以g为轴进行一次旋转（LL情况进行右旋，RR情况进行左旋）。
结果: 旋转和变色完成后，子树的根节点变为了原来的p，它是黑色的。它的两个子节点z和g都是红色的。子树的黑色高度保持不变，并且不再存在连续的红色节点。修复完成。
G(黑) P(黑)
/ /
P(红) U(black) --> Z(红) G(红)
/
Z(红) U(黑)
(经过变色和对G右旋后)
最后一步: 无论中间经过了何种修复，循环结束后，都要强制将根节点设为黑色，以满足“根节点法则”。
5.2.3 红黑树的Python实现
红黑树的实现比AVL树更依赖于节点的亲属关系，因此，在节点中保存一个指向父节点的引用（parent）会极大地简化旋转和修复逻辑。同时，为了优雅地处理叶子节点（NIL），我们引入一个**哨兵节点（Sentinel Node）**来代表所有的NIL叶子。这个哨兵节点是黑色的，它的left, right, parent都指向自己。
# red_black_tree.py
# 定义颜色常量
RED = "RED"
BLACK = "BLACK"
class RedBlackNode:
"""定义一个红黑树节点类。"""
def __init__(self, value, color=RED, parent=None, left=None, right=None):
self.val = value # 节点值
self.color = color # 节点颜色 (新节点默认为红色)
self.parent = parent # 指向父节点的引用
self.left = left # 指向左子节点
self.right = right # 指向右子节点
def __str__(self):
return f"({
self.val}, {
self.color})"
class RedBlackTree:
"""定义一个红黑树类，并实现其核心操作。"""
def __init__(self):
# 初始化一个哨兵节点T.nil，它代表所有的叶子节点
self.TNULL = RedBlackNode(0, color=BLACK)
# 树的根节点初始化为哨兵节点，表示一棵空树
self.root = self.TNULL
def left_rotate(self, x):
"""对节点x进行左旋。"""
y = x.right # y是x的右孩子
x.right = y.left # 将y的左子树挂到x的右边
if y.left != self.TNULL: # 如果y的左子树不是哨兵
y.left.parent = x # 更新其父指针
y.parent = x.parent # y的父节点变为x的父节点
if x.parent is None: # 如果x是根节点
self.root = y # y成为新的根节点
elif x == x.parent.left: # 如果x是其父节点的左孩子
x.parent.left = y # y成为新的左孩子
else: # 如果x是其父节点的右孩子
x.parent.right = y # y成为新的右孩子
y.left = x # x成为y的左孩子
x.parent = y # x的父节点变为y
def right_rotate(self, x):
"""对节点x进行右旋 (与左旋对称)。"""
y = x.left # y是x的左孩子
x.left = y.right # 将y的右子树挂到x的左边
if y.right != self.TNULL: # 如果y的右子树不是哨兵
y.right.parent = x # 更新其父指针
y.parent = x.parent # y的父节点变为x的父节点
if x.parent is None: # 如果x是根节点
self.root = y # y成为新的根节点
elif x == x.parent.right: # 如果x是其父节点的右孩子
x.parent.right = y # y成为新的右孩子
else: # 如果x是其父节点的左孩子
x.parent.left = y # y成为新的左孩子
y.right = x # x成为y的右孩子
x.parent = y # x的父节点变为y
def insert(self, value):
"""向红黑树中插入一个新值。"""
# 创建一个新节点，颜色为红，左右孩子为哨兵
node = RedBlackNode(value, left=self.TNULL, right=self.TNULL)
parent = None # 追踪父节点
current = self.root # 从根节点开始
# 1. 按照BST规则找到插入位置
while current != self.TNULL:
parent = current
if node.val < current.val:
current = current.left
else:
current = current.right
# 2. 链接新节点
node.parent = parent
if parent is None: # 如果是空树
self.root = node
elif node.val < parent.val:
parent.left = node
else:
parent.right = node
# 如果新节点是根节点，直接变黑即可
if node.parent is None:
node.color = BLACK
return
# 如果父节点为空，则无需修复
if node.parent.parent is None:
return
# 3. 调用修复函数
self.insert_fixup(node)
def insert_fixup(self, z):
"""插入后的修复操作。"""
# 只要父节点是红色的，就需要修复 (违反了红色法则)
while z.parent.color == RED:
# 父节点是祖父节点的右孩子
if z.parent == z.parent.parent.right:
uncle = z.parent.parent.left # 叔叔是左孩子
# Case 1: 叔叔是红色
if uncle.color == RED:
uncle.color = BLACK # 叔叔变黑
z.parent.color = BLACK # 父亲变黑
z.parent.parent.color = RED # 祖父变红
z = z.parent.parent # 将z指向祖父，继续向上检查
else:
# Case 2: 叔叔是黑色，且z是左孩子 (RL 三角)
if z == z.parent.left:
z = z.parent # z指向父亲
self.right_rotate(z) # 对z进行右旋，变为RR直线
# Case 3: 叔叔是黑色，且z是右孩子 (RR 直线)
z.parent.color = BLACK # 父亲变黑
z.parent.parent.color = RED # 祖父变红
self.left_rotate(z.parent.parent) # 对祖父进行左旋
# 父节点是祖父节点的左孩子 (与上面对称)
else:
uncle = z.parent.parent.right # 叔叔是右孩子
# Case 1: 叔叔是红色
if uncle.color == RED:
uncle.color = BLACK # 叔叔变黑
z.parent.color = BLACK # 父亲变黑
z.parent.parent.color = RED # 祖父变红
z = z.parent.parent # 将z指向祖父
else:
# Case 2: 叔叔是黑色，且z是右孩子 (LR 三角)
if z == z.parent.right:
z = z.parent # z指向父亲
self.left_rotate(z) # 对z进行左旋，变为LL直线
# Case 3: 叔叔是黑色，且z是左孩子 (LL 直线)
z.parent.color = BLACK # 父亲变黑
z.parent.parent.color = RED # 祖父变红
self.right_rotate(z.parent.parent) # 对祖父进行右旋
if z == self.root: # 如果z到达了根节点，循环结束
break
# 最后，无论如何都要保证根节点是黑色的
self.root.color = BLACK
def inorder_helper(self, node):
"""辅助函数，用于中序遍历并返回节点信息列表。"""
if node != self.TNULL:
yield from self.inorder_helper(node.left)
yield str(node)
yield from self.inorder_helper(node.right)
# --- 使用我们自己实现的红黑树 ---
rbt = RedBlackTree()
# 插入一系列值来观察树的平衡过程
values_to_insert = [55, 40, 65, 60, 75, 57]
for val in values_to_insert:
print(f"
>>> 插入值: {
val}")
rbt.insert(val)
print(f"插入后中序遍历结果: {
' -> '.join(rbt.inorder_helper(rbt.root))}")
print("
--- 最终树结构 ---")
print(f"根节点: {
rbt.root}")
print(f"根的左孩子: {
rbt.root.left}")
print(f"根的右孩子: {
rbt.root.right}")
print(f"根的右孩子的左孩子: {
rbt.root.right.left}")
5.2.4 红黑树的删除操作（概念概览）
红黑树的删除操作是其所有操作中最复杂的，其修复逻辑（delete_fixup）比插入要多出数种情况。在此我们先建立其核心思想的宏观理解。
删除操作的难点在于，如果删除的是一个黑色节点，那么包含这个节点的所有路径上的黑色节点数就会减1，直接违反了“黑色高度法则”。
为了解决这个问题，算法会想象在替代被删除节点位置的那个节点上，附加了一层额外的“黑色”。这个节点被称为**“双重黑色”（Double Black）**。删除修复的目标，就是通过一系列的变色和旋转，将这个“双重黑色”属性不断向上推，直到：
它被一个红色节点吸收（将红色节点变为黑色，问题解决）。
它到达了根节点（根节点的额外黑色可以直接移除）。
delete_fixup的逻辑主要围绕着“双重黑色”节点的兄弟节点的颜色来展开，分为多种情况进行处理，每种情况都对应着不同的旋转和变色策略。尽管其实现细节繁琐，但其最终目标仍然是在不超过3次旋转内，恢复红黑树的所有性质，维持O(log n)的性能保证。
5.2.5 AVL树 vs. 红黑树：现实世界的抉择
现在我们已经深入了解了这两种经典的自平衡树，是时候对它们进行一次全面的对比。
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡性 | 更严格。所有节点的左右子树高度差不超过1。 | 较宽松。最长路径不超过最短路径的2倍。 |
| 高度 | 更接近log₂(n)，树更“矮胖”。 |
可能比AVL树高，但渐进复杂度仍为O(log n)。 |
| 查找性能 | 理论上更快。因为树的高度更低，查找路径更短。 | 非常快，与AVL树的实际差距通常可以忽略不计。 |
| 插入/删除性能 | 可能较慢。为维持严格平衡，可能需要O(log n)次旋转。 |
通常更快。插入最多需要2次旋转，删除最多3次。主要开销是变色，非常迅速。 |
| 实现复杂度 | 相对简单。逻辑只关心高度和平衡因子。 | 非常复杂。需要处理颜色、父指针、多种修复场景。 |
| 适用场景 | 读多写少的应用，如数据库索引，其中查找速度至关重要。 | 写操作频繁或读写均衡的应用。这是绝大多数通用场景的选择，如图形库、内核、语言标准库。 |
总而言之，AVL树像是实验室中的精密仪器，追求理论上的最优平衡。而红黑树则是久经考验的工业级工具，它通过适度的妥协，换来了在动态变化环境中更稳定、更高效的综合表现。
第六章：B-家族树 —— 海量数据时代的磁盘王者
至此，我们已经征服了二叉搜索树的山峰，无论是朴素的BST，还是纪律严明的AVL树，亦或是灵活高效的红黑树，它们都在内存的世界里为我们提供了O(log n)的卓越性能。它们的核心假设是：所有数据都能舒适地存放在主内存（RAM）中，CPU访问任何一个节点的成本都是均等的、纳秒级的。
然而，当我们踏入大数据的真实世界，这个假设便轰然崩塌。TB级甚至PB级的数据集，远远超出了任何单台机器的内存容量。这些海量数据必须被存储在相对廉价但速度慢上千上万倍的外部存储设备上，例如机械硬盘（HDD）或固态硬盘（SSD）。
在这里，算法效率的瓶颈发生了根本性的转变。CPU飞速的计算能力在缓慢的磁盘I/O面前显得无足轻重。一次磁盘读取操作（将一个数据块从磁盘加载到内存）可能需要几毫秒，这段时间足够CPU执行数百万次计算。因此，一个为外部存储设计的优秀算法，其首要目标不再是减少CPU比较次数，而是尽可能地减少磁盘I/O次数。
我们之前学习的二叉树，无论是AVL还是红黑树，都存在一个致命问题：它们太“瘦高”了。一个包含数十亿节点的平衡二叉树，其高度依然有几十层（log₂(10⁹) ≈ 30）。在最坏情况下，一次查找操作可能需要进行30次磁盘读取，因为树的每个节点都可能存储在磁盘的不同位置。这种性能是灾难性的。
为了征服磁盘I/O这座大山，计算机科学家们设计出了一种全新的树形结构，它的形态与二叉树截然相反——它不是“瘦高”，而是极度的“矮胖”。这种结构就是B-树（B-Tree）。B-树通过在单个节点中存储大量的关键字和子节点指针，极大地增加了树的“扇出”（fan-out），从而在存储海量数据的同时，保持树的高度异常之低，通常只有3到5层。这意味着，在B-树上进行一次查找，往往只需要3到5次磁盘I/O，这在外部存储场景下是革命性的性能提升。
我们将深入探索B-树及其最重要的变体——B+树的内部工作原理。我们将揭示它们是如何通过独特的节点分裂与合并机制，来维持其矮胖身材，并最终成为现代数据库和文件系统领域无可争议的王者。
6.1 B-树的核心解构
B-树并非“二叉树”（Binary-Tree），它名字中的“B”并没有一个官方公认的完整单词定义，你可以理解为代表“平衡的”（Balanced）、“宽阔的”（Broad）或其发明者姓氏“Bayer”。
一个**m阶（order m）的B-树**，或等价地，一个最小度为t（minimum degree t）的B-树（其中 t = ⌈m/2⌉），必须满足以下铁律：
节点构成法则: 每个节点最多可以包含 m-1 个关键字（keys）和 m 个指向子节点的指针。节点内的关键字是按升序排列的。
关键字与子节点关系法则: 对于任意一个内部（非叶子）节点，如果它包含 n 个关键字 (key₁, key₂, ..., keyₙ)，那么它必定包含 n+1 个指向子节点的指针 (child₁, child₂, ..., childₙ₊₁)。其中，childᵢ 指向的子树中所有关键字都介于 keyᵢ₋₁ 和 keyᵢ 之间。
child₁ 指向的子树，所有关键字都 < key₁。
child₂ 指向的子树，所有关键字都 > key₁ 且 < key₂。
…
childₙ₊₁ 指向的子树，所有关键字都 > keyₙ。
节点容量法则（根节点除外）: 每个非根节点的内部节点，至少包含 ⌈m/2⌉ - 1 个关键字和 ⌈m/2⌉ 个子节点指针。这保证了节点的空间利用率至少在50%左右。
根节点法则: 根节点是个特例。如果它不是叶子节点，那么它至少有两个子节点。如果树只有一个节点（根即叶子），它可以包含1到 m-1 个任意数量的关键字。
高度平衡法则: 所有的叶子节点都必须出现在同一层。这表明B-树是一种绝对的高度平衡树。树的生长和收缩不是通过旋转，而是通过节点的分裂和合并，且高度只在根节点分裂或合并时才会发生变化。
一个B-树节点的内部视图（以m=5为例）
一个5阶B-树的节点，最多有4个关键字和5个孩子。它在内存中的样子大概是这样：
[ Ptr₁ | Key₁ | Ptr₂ | Key₂ | Ptr₃ | Key₃ | Ptr₄ | Key₄ | Ptr₅ ]
Ptrᵢ 是指向子树根节点的指针（在磁盘上就是块地址）。
Keyᵢ 是关键字。
整个结构被存储在磁盘的一个“块”（Block）或“页”（Page）中，一次I/O操作会将整个节点读入内存。
6.2 B-树的基石：查找与遍历
B-树的查找操作是其所有更复杂操作的基础。其过程是二分查找思想在多路树上的自然延伸。
查找过程:
从根节点开始。
将目标值 k 与当前节点内的关键字 key₁, key₂, ..., keyₙ 进行比较。
如果在当前节点中找到了 k，查找成功。
如果在当前节点没找到 k，则需要确定下一步要进入哪个子树：
如果 k < key₁，则沿着 child₁ 指针进入下一层。
如果 keyᵢ < k < keyᵢ₊₁，则沿着 childᵢ₊₁ 指针进入下一层。
如果 k > keyₙ，则沿着 childₙ₊₁ 指针进入下一层。
在下一层节点中重复步骤2-4。
如果最终到达了叶子节点，并且在叶子节点中仍然没有找到 k，则说明该关键字在树中不存在。
由于每次进入下一层都需要一次磁盘读取，查找的总成本主要由树的高度决定。对于一个包含N个关键字，阶为m的B-树，其高度h的上限约为 log_⌈m/2⌉(N)。这是一个非常小的数字。例如，一个阶为1024，高度为3的B-树，可以存储超过10亿个关键字，而查找任何一个关键字最多只需要3次磁盘I/O。
6.3 B-树的生长：插入与节点分裂
B-树的插入操作永远遵循一个原则：总是向叶子节点插入。如果插入导致叶子节点“溢出”（关键字数量超过m-1），则会触发一个向上层传播的“分裂”过程。
插入过程:
查找: 首先，执行与查找操作类似的过程，找到新关键字 k 应该被插入的那个叶子节点。
插入: 将关键字 k 插入到该叶子节点的正确位置，保持节点内关键字的有序性。
检查溢出:
如果该叶子节点未满（插入后关键字数量 ≤ m-1），操作结束。
如果该叶子节点已满（插入后关键字数量 = m），则必须进行分裂（Split）。
节点分裂过程:
找到中位数: 在这个包含了m个关键字的溢出节点中，找到中间那个关键字 key_median。
创建新节点: 创建一个新的兄弟节点。
分配关键字:
所有小于 key_median 的关键字保留在原节点。
所有大于 key_median 的关键字移动到新的兄弟节点。
提升中位数: 将中位数关键字 key_median 向上提升到父节点中，插入到合适的位置。同时，将指向新创建的兄弟节点的指针也插入到父节点中。
递归检查: 提升操作可能会导致父节点也发生溢出。如果父节点也满了，则对父节点重复进行分裂操作。这个过程可能一直向上传播，直到根节点。
根节点分裂: 如果分裂过程一直传播到了根节点，导致根节点也需要分裂，那么分裂后提升的中位数将成为一个新的根节点，原根节点分裂成的两个节点将成为新根节点的子节点。这是B-树高度增加的唯一方式。
6.4 Python实现一个B-树
B-树的实现比我们之前接触过的任何树都更为复杂，因为它涉及在数组（节点内的关键字列表）层面的大量操作，以及递归的分裂逻辑。我们将以最小度 t 来定义B-树，这意味着每个节点最多有 2t-1 个关键字和 2t 个孩子，最少有 t-1 个关键字和 t 个孩子。
# b_tree.py
class BTreeNode:
"""定义一个B-树节点类。"""
def __init__(self, leaf=False):
self.leaf = leaf # 布尔值，标识是否为叶子节点
self.keys = [] # 节点中存储的关键字列表
self.children = [] # 指向子节点的指针列表
def __str__(self):
"""方便打印调试的字符串表示。"""
return f"Node(Keys:{
self.keys}, IsLeaf:{
self.leaf})"
class BTree:
"""定义一个B-树类，并实现其核心操作。"""
def __init__(self, t):
if t < 2: # 最小度t必须至少为2
raise ValueError("B-Tree minimum degree t must be at least 2")
self.root = BTreeNode(leaf=True) # 初始化根节点为一个空的叶子节点
self.t = t # B-树的最小度 (minimum degree)
def search(self, k):
"""
在B-树中查找关键字k。
返回一个元组 (node, index) 或 (None, None)。
"""
return self._search_recursive(self.root, k)
def _search_recursive(self, x, k):
"""查找的递归辅助函数。"""
i = 0
# 找到第一个大于等于k的关键字的索引
while i < len(x.keys) and k > x.keys[i]:
i += 1
# 如果找到了完全匹配的关键字
if i < len(x.keys) and k == x.keys[i]:
return (x, i) # 返回节点和在节点内的索引
# 如果当前是叶子节点，且没找到，说明不存在
if x.leaf:
return (None, None)
# 如果不是叶子节点，则递归地到合适的子节点中去查找
return self._search_recursive(x.children[i], k)
def insert(self, k):
"""向B-树中插入一个新关键字k。"""
root = self.root
# Case 1: 如果根节点已满 (有 2t-1 个关键字)
if len(root.keys) == (2 * self.t) - 1:
# 创建一个新的空根节点
new_root = BTreeNode()
self.root = new_root
# 新根节点的第一个孩子是旧的根节点
new_root.children.append(root)
# 对旧的满根节点进行分裂
self._split_child(new_root, 0)
# 分裂后，从新的根节点开始，为k找到正确的插入路径
self._insert_non_full(new_root, k)
else:
# Case 2: 如果根节点未满，直接从根开始插入
self._insert_non_full(root, k)
def _insert_non_full(self, x, k):
"""向一个未满的节点x中插入关键字k。"""
i = len(x.keys) - 1
# 如果当前是叶子节点
if x.leaf:
# 找到k应该插入的位置，并将所有更大的关键字向右移动
x.keys.append(0) # 临时扩展列表
while i >= 0 and k < x.keys[i]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k # 插入关键字
else:
# 如果是内部节点，找到k应该进入的子树
while i >= 0 and k < x.keys[i]:
i -= 1
i += 1
# 如果发现要进入的子节点是满的
if len(x.children[i].keys) == (2 * self.t) - 1:
self._split_child(x, i) # 那么先分裂这个子节点
# 分裂后，中间关键字被提升到父节点x，x多了一个孩子
# 决定k应该进入分裂后的哪个子节点
if k > x.keys[i]:
i += 1
# 递归地向未满的子节点中插入
self._insert_non_full(x.children[i], k)
def _split_child(self, x, i):
"""
分裂父节点x的第i个已满的孩子y。
x: 父节点
i: 满孩子在x.children中的索引
"""
t = self.t
y = x.children[i] # y是那个要被分裂的满孩子
z = BTreeNode(leaf=y.leaf) # z是分裂后产生的新兄弟节点
# 将y的后t-1个关键字移动到z
z.keys = y.keys[t:]
y.keys = y.keys[:t-1] # y保留前t-1个关键字
# 如果y不是叶子，将其后t个孩子指针移动到z
if not y.leaf:
z.children = y.children[t:]
y.children = y.children[:t]
# y的中间关键字 (原索引t-1) 需要被提升到父节点x
median_key = y.keys.pop()
# 在父节点x中为新孩子z腾出空间
x.children.insert(i + 1, z)
# 在父节点x中为提升的关键字腾出空间并插入
x.keys.insert(i, median_key)
def print_tree(self):
"""打印整棵B-树 (层序遍历)。"""
if not self.root:
print("The B-Tree is empty.")
return
queue = [self.root]
level = 0
while queue:
level_size = len(queue)
print(f"Level {
level}:")
for _ in range(level_size):
node = queue.pop(0)
print(f" {
node.keys}", end="")
if not node.leaf:
for child in node.children:
queue.append(child)
print("
" + "-"*30)
level += 1
# --- 使用我们自己实现的B-树 ---
# 创建一个最小度t=3的B-树。
# 这意味着每个节点最多有 2*3-1=5 个关键字，最少有 3-1=2 个关键字。
b_tree = BTree(3)
# 插入一系列值
values_to_insert = [10, 20, 5, 6, 12, 30, 7, 17, 50, 60, 80, 100, 4, 1, 2, 3]
print(f"Inserting values: {
values_to_insert}")
for val in values_to_insert:
b_tree.insert(val)
print("
--- Final B-Tree Structure ---")
b_tree.print_tree()
print("
--- Searching for values ---")
search_val_1 = 17
node, index = b_tree.search(search_val_1)
if node:
print(f"Found {
search_val_1} in node with keys {
node.keys} at index {
index}")
else:
print(f"Value {
search_val_1} not found.")
search_val_2 = 99
node, index = b_tree.search(search_val_2)
if node:
print(f"Found {
search_val_2} in node with keys {
node.keys} at index {
index}")
else:
print(f"Value {
search_val_2} not found.")
代码剖析:
BTreeNode: 核心数据结构，只包含关键字列表、孩子列表和一个叶子标记。
BTree: 主类，持有根节点和最小度t。
_split_child: 这是B-树实现中最关键的函数。它负责将一个满的子节点y分裂成两半，并将其- 中间关键字提升到父节点x中。这是树“向上生长”的唯一机制。
_insert_non_full: 这是一个“安全”的插入函数。它保证在递归下降的过程中，遇到的任何子节点都不会是满的。如果它发现将要进入的子节点是满的，它会先调用_split_child来处理，然后再安全地进入。
insert: 这是公共的插入接口。它的主要职责是处理一个特殊情况：根节点是满的。如果根节点满了，它会先创建一个新的根，将旧根作为其子节点，然后分裂旧根，最后再调用_insert_non_full。
6.5 数据库的基石：B+树
尽管B-树已经非常强大，但在实际的数据库系统（如MySQL的InnoDB、PostgreSQL）和文件系统（如NTFS、HFS+）中，你遇到更多的会是它的变体——B+树。B+树在B-树的基础上做了两处关键的、看似微小但影响深远的修改，使其更适合数据库的特性。
B+树与B-树的核心差异:
数据只在叶子节点: B+树的内部节点（非叶子节点）不再存储实际的数据记录（或者指向数据记录的指针），它们只存储用于导航的“路标”关键字。所有的数据记录都只存在于叶子节点中。
叶子节点串联: 所有的叶子节点通过指针被链接在一起，形成一个有序的双向链表。
这两处修改带来了巨大的优势:
更高的扇出（Fan-out）: 由于内部节点不再存储数据，只存储关键字，这意味着在同样大小的一个磁盘块（Page）中，B+树的内部节点可以容纳比B-树更多的关键字。更高的扇出意味着树可以变得更“矮胖”，进一步减少了查找时所需的磁盘I/O次数。
高效的范围查询: 这是B+树最显著的优点。在数据库中，“查询所有年龄在20到30岁之间的用户”或“获取上个月的所有订单”这类范围查询非常普遍。对于B-树，执行这样的查询可能需要在树的不同层级之间反复横跳。而对于B+树，你只需要：
a. 查找到范围的起始点（例如，年龄20）。
b. 然后，沿着叶子节点的链表，顺序地向后扫描，直到范围的结束点（年龄30）。
这个过程是纯粹的顺序磁盘读取，效率极高。
稳定的查询性能: 由于所有数据都在叶子节点，任何一次查找操作都必须走到叶子层，这使得所有查询的路径长度都是相同的（即树的高度），查询性能非常稳定。
一个B+树的结构示意图：
[Internal Node: Keys only]
/ |
[Internal Node] [Internal Node] [Internal Node]
/ | / | / |
[Leaf] <=> [Leaf] <=> [Leaf] <=> [Leaf] <=> [Leaf] <=> [Leaf]
(Data) (Data) (Data) (Data) (Data) (Data)
B-树及其变体B+树的设计哲学，是计算机科学中一个典型的例子，即算法设计必须深度适应其运行环境的物理限制。它们通过牺牲单节点内的比较成本，换取了I/O成本的巨大降低，完美地解决了外部存储中海量数据的索引和查询难题。
第七章：堆与优先队列 —— 数据的有序涌现
我们已经探索了诸多树形结构，从追求绝对平衡的AVL树，到为磁盘I/O量身定制的B-树。这些结构的核心目标，都是为了实现对集合中任意一个元素的快速增、删、查。然而，在许多现实场景中，我们的需求并非如此“民主”。我们往往只关心集合中的“极端分子”——那个最大或最小的元素。
在这些场景中，一个共同的需求模式浮现出来：我们需要一个能够高效支持以下两种操作的数据容器：
插入（Enqueue）: 快速地将一个带有特定优先级的新元素加入集合。
提取极值（Dequeue）: 快速地从集合中找到并移除那个优先级最高（或最低）的元素。
这种只已关注“极值”出队的抽象数据类型（ADT），被称为优先队列（Priority Queue）。
我们可以尝试用已知的数据结构来实现它吗？
无序数组/链表: 插入操作是O(1)，只需添加到末尾。但提取最大/小值需要遍历整个数组，成本是O(n).
有序数组: 提取最大/小值是O(1)，就在数组的一端。但插入一个新元素为了维持有序性，需要移动大量元素，成本是O(n).
平衡二叉搜索树（如AVL树）: 插入和删除（包括查找最大/小值）都是O(log n). 这当然可行，但平衡二叉搜索树为了维护全局的、严格的“左小右大”顺序，付出了相当大的实现复杂度和旋转开销。它做了许多“多余”的工作，因为我们根本不关心集合中非极值元素之间的相对顺序。
我们需要一种更“专注”的数据结构，它不必维护所有元素间的完整排序，只需要保证我们能随时快速定位到那个唯一的极值元素即可。这种结构就是堆（Heap）。堆是一种特殊的、弱序的树形结构，它以O(log n)的代价完美地实现了优先队列的两种核心操作，并且其实现可以异常地简洁和高效。
7.1 堆的核心属性：形态与内在
在众多堆的变体中，我们首先聚焦于最基础、最常用的一种：二叉堆（Binary Heap）。一个合法的二叉堆必须同时满足两个铁律：结构上的形态规则和元素间的内在规则。
1. 形态属性（Shape Property）：必须是完全二叉树
堆在结构上必须是一个完全二叉树（Complete Binary Tree）。我们在第四章已经介绍过这个概念：一棵树，除了最后一层外，其他所有层都是满的，并且最后一层的节点都尽可能地从左边开始连续填充。
这个看似简单的形态限制，是堆结构高效实现的第一块基石。它带来了一个无与伦比的优势：我们可以用一个简单的数组来紧凑地、不浪费任何空间地表示一棵完全二叉树。我们不需要像其他树结构那样使用显式的指针（left, right, parent）来连接节点。节点在树中的父子关系，可以通过简单的数组索引计算来隐式地确定。
数组与完全二叉树的映射关系:
假设一个元素的数组索引为 i（0-based indexing）：
其父节点的索引为: floor((i - 1) / 2)
其左子节点的索引为: 2 * i + 1
其右子节点的索引为: 2 * i + 2
示例: 数组 [10, 20, 30, 40, 50]
索引0的元素 10 是根。
10 的左孩子是 2*0+1=1，即 20。
10 的右孩子是 2*0+2=2，即 30。
20 的左孩子是 2*1+1=3，即 40。
20 的右孩子是 2*1+2=4，即 50。
30 的父节点是 floor((2-1)/2)=0，即 10。
这种隐式表示法极大地降低了内存开销，并提升了缓存局部性，是堆性能优越的一大秘密。
2. 堆属性（Heap Property）：父节点的支配地位
堆属性定义了节点值之间的关系。它分为两种：
最大堆（Max-Heap）: 对于除根节点以外的任意节点 i，其父节点的值都大于或等于 i 的值。即 A[parent(i)] >= A[i]。 这条规则的直接推论是：堆中最大的元素永远位于根节点。
最小堆（Min-Heap）: 对于除根节点以外的任意节点 i，其父节点的值都小于或等于 i 的值。即 A[parent(i)] <= A[i]。 这条规则的直接推论是：堆中最小的元素永远位于根节点。
请注意，堆属性没有对兄弟节点之间的关系做出任何规定。一个节点的左孩子可能比右孩子大，也可能比它小。这种“弱序”特性，正是堆相比于BST开销更小的根源。
7.2 堆的核心操作：上浮与下沉
一个堆的动态平衡，完全依赖于两种基本操作来维护堆属性：向上调整（Sift-up）和向下调整（Sift-down）。我们将以最小堆为例来详细讲解这些操作。
7.2.1 插入新元素：气泡的上浮（Sift-up）
当我们要向堆中插入一个新元素时，为了不破坏其“完全二叉树”的形态，最自然的选择是将其放置在数组的末尾。
添加至末尾: 将新元素添加到数组的最后。这保持了形态属性。
破坏与修复: 此时，新元素可能会比它的父节点小，从而违反了最小堆的属性。我们需要进行修复。
上浮过程: 将新元素与其父节点进行比较。如果它比父节点小，就交换它们的位置。交换后，继续将这个元素与它新的父节点比较，如果还是更小，就继续交换。这个过程就像一个轻的气泡在水中不断上浮，直到它遇到了一个比它更小的父节点，或者它自己成为了根节点。
这个向上修复的过程，路径长度最多为树的高度，即O(log n)。
7.2.2 提取最小元素：权威的下沉（Sift-down）
提取最小元素的操作总是从根节点开始，因为最小值就存放在那里。但移除根节点后，树的结构会出现一个空洞，我们需要一个优雅的方式来填补它，并恢复堆属性。
记录最小值: 保存根节点（数组索引0处）的值，这是我们要返回的结果。
移花接木: 将数组的最后一个元素移动到根节点的位置，并从数组末尾删除它。这个操作巧妙地维持了完全二叉树的形态。
破坏与修复: 此时，被移到根部的新元素很可能比它的子节点大，破坏了最小堆的属性。我们需要让这个新的“伪王”下沉到它应在的位置。
下沉过程: 将当前节点（开始时是根节点）与其两个子节点中较小的一个进行比较。如果当前节点比那个较小的子节点还要大，就交换它们的位置。交换后，继续将这个元素与它新位置上的子节点们比较，并与更小的那个交换。这个过程就像一个名不副实的权威在质疑声中不断“下沉”，直到它到了一个位置，它比它的所有子节点都小（或者它成为了叶子节点），从而重新建立起父节点的“权威”。
这个向下修复的过程，路径长度最多也是树的高度，即O(log n)。
7.3 从零开始实现一个最小堆
现在，我们将上述理论转化为具体的Python代码。
# min_heap.py
class MinHeap:
"""
使用Python列表实现一个最小堆。
"""
def __init__(self):
# 堆的内部存储，使用一个列表
self.heap = []
def get_parent_index(self, i):
"""根据子节点索引获取父节点索引。"""
return (i - 1) // 2
def get_left_child_index(self, i):
"""根据父节点索引获取左子节点索引。"""
return 2 * i + 1
def get_right_child_index(self, i):
"""根据父节点索引获取右子节点索引。"""
return 2 * i + 2
def has_parent(self, i):
"""检查一个节点是否有父节点。"""
return self.get_parent_index(i) >= 0
def has_left_child(self, i):
"""检查一个节点是否有左子节点。"""
return self.get_left_child_index(i) < len(self.heap)
def has_right_child(self, i):
"""检查一个节点是否有右子节点。"""
return self.get_right_child_index(i) < len(self.heap)
def parent(self, i):
"""获取父节点的值。"""
return self.heap[self.get_parent_index(i)]
def left_child(self, i):
"""获取左子节点的值。"""
return self.heap[self.get_left_child_index(i)]
def right_child(self, i):
"""获取右子节点的值。"""
return self.heap[self.get_right_child_index(i)]
def swap(self, i, j):
"""交换堆中两个元素的位置。"""
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, value):
"""向堆中插入一个新值 (上浮操作)。"""
self.heap.append(value) # 将新元素添加到数组末尾
self.sift_up() # 执行上浮操作来恢复堆属性
def sift_up(self):
"""向上调整，恢复堆属性。"""
index = len(self.heap) - 1 # 从最后一个元素开始
# 当该节点有父节点，且值小于父节点时，持续上浮
while self.has_parent(index) and self.heap[index] < self.parent(index):
parent_index = self.get_parent_index(index) # 获取父节点索引
self.swap(index, parent_index) # 与父节点交换
index = parent_index # 更新当前索引为父节点的索引，继续向上检查
def poll(self):
"""
提取并返回堆中的最小值 (下沉操作)。
poll是队列常用的术语，意为提取队首元素。
"""
if len(self.heap) == 0: # 如果堆为空，则无法提取
raise IndexError("poll from an empty heap")
item_to_return = self.heap[0] # 记录根节点（最小值）
self.heap[0] = self.heap[-1] # 将最后一个元素移动到根
del self.heap[-1] # 删除最后一个元素
self.sift_down() # 执行下沉操作来恢复堆属性
return item_to_return # 返回最小值
def sift_down(self):
"""向下调整，恢复堆属性。"""
index = 0 # 从根节点开始
# 只要节点有左孩子，就可能需要下沉 (有左必有右或无右)
while self.has_left_child(index):
smaller_child_index = self.get_left_child_index(index) # 先假设左孩子是较小的那个
# 如果存在右孩子，并且右孩子比左孩子还小
if self.has_right_child(index) and self.right_child(index) < self.left_child(index):
smaller_child_index = self.get_right_child_index(index) # 更新较小孩子的索引
# 如果当前节点的值已经小于或等于其较小的孩子，则堆属性已满足，停止下沉
if self.heap[index] <= self.heap[smaller_child_index]:
break
else:
# 否则，与较小的孩子交换
self.swap(index, smaller_child_index)
# 更新当前索引，继续向下检查
index = smaller_child_index
def peek(self):
"""查看堆顶的最小值，但不移除它。"""
if len(self.heap) == 0:
raise IndexError("peek from an empty heap")
return self.heap[0] # 返回根节点的值
def is_empty(self):
"""检查堆是否为空。"""
return len(self.heap) == 0
# --- 使用我们自己实现的最小堆 ---
heap = MinHeap()
print(f"Is heap empty? {
heap.is_empty()}") # 检查是否为空
# 插入元素
values_to_insert = [10, 4, 15, 20, 0, 30, 1]
print(f"
Inserting values: {
values_to_insert}")
for val in values_to_insert:
heap.insert(val)
print(f" Inserted {
val}, heap is now: {
heap.heap}")
print(f"
Is heap empty? {
heap.is_empty()}") # 再次检查
print(f"Peek at minimum value: {
heap.peek()}") # 查看最小值
# 提取元素
print("
Polling values from heap:")
while not heap.is_empty():
min_val = heap.poll() # 提取最小值
print(f" Polled {
min_val}, heap is now: {
heap.heap}")
7.4 高效建堆：O(n)的魔法（Heapify）
如果我们已经有了一个无序的数组，想要把它转换成一个合法的堆，最直接的方法是什么？我们可以创建一个空堆，然后遍历数组，将每个元素逐一insert。每次insert的成本是O(log n)，总共n个元素，所以总成本是O(n log n).
这个方法可行，但不是最优的。存在一种更高效的、自底向上的建堆算法，其时间复杂度可以达到惊人的**O(n)。这个算法通常被称为Heapify**。
Heapify算法思想:
找到起点: 我们知道，堆中的所有叶子节点，天然地满足堆属性（因为它们没有子节点）。所以我们不需要对叶子节点做任何操作。算法的起点是最后一个非叶子节点。在数组表示中，最后一个元素的索引是n-1，其父节点就是最后一个非叶- 子节点，索引为 floor((n-1 - 1) / 2) = floor(n/2) - 1。
自底向上: 从这个最后一个非叶子节点开始，向前遍历到根节点（索引0）。
下沉调整: 对遍历到的每一个节点，都执行一次**sift_down**操作。
为什么这是O(n)的？
直觉上看，n/2个节点，每个都做sift_down（成本O(log n)），总成本似乎还是O(n log n)。但这是一个经典的误区。关键在于，sift_down的成本与节点的高度成正比，而堆中绝大多数节点都集中在底层，它们的高度非常低。
树的最底层（约n/2个节点），高度为0，sift_down成本为O(1)。
倒数第二层（约n/4个节点），高度为1，sift_down成本为O(1)。
倒数第三层（约n/8个节点），高度为2，sift_down成本为O(2)。
…
根节点（1个），高度为log n，成本为O(log n)。
将所有节点的成本加起来，会得到一个收敛的级数，其总和的渐进上界是O(n)。这证明了Heapify算法的线性时间复杂度。
Heapify的Python实现
我们可以将Heapify作为我们MinHeap类的一个构造函数或一个独立的方法。
# (继续在 min_heap.py 中添加)
# ... 在MinHeap类内部 ...
def __init__(self, items=None):
"""
构造函数，可以接受一个可选的列表来初始化堆。
如果提供了列表，将使用O(n)的heapify算法建堆。
"""
if items is None:
self.heap = []
else:
self.heap = list(items) # 复制列表
self.heapify() # 调用heapify
def heapify(self):
"""O(n)的建堆算法。"""
if len(self.heap) < 2: # 如果堆中元素少于2个，无需操作
return
# 从最后一个非叶子节点开始，向前遍历到根
start_index = (len(self.heap) // 2) - 1
for i in range(start_index, -1, -1):
self._sift_down_from(i) # 对每个节点执行下沉
def _sift_down_from(self, index):
"""
一个可指定起始索引的下沉函数，是heapify的核心。
(这个函数与之前的sift_down几乎一样，只是参数不同)
"""
# 只要节点有左孩子，就可能需要下沉
while self.has_left_child(index):
smaller_child_index = self.get_left_child_index(index)
if self.has_right_child(index) and self.right_child(index) < self.left_child(index):
smaller_child_index = self.get_right_child_index(index)
if self.heap[index] <= self.heap[smaller_child_index]:
break
else:
self.swap(index, smaller_child_index)
index = smaller_child_index
# --- 使用Heapify建堆 ---
print("
--- Testing Heapify O(n) constructor ---")
unsorted_list = [23, 17, 14, 6, 13, 10, 1, 5, 7, 12]
print(f"Original unsorted list: {
unsorted_list}")
heap_from_list = MinHeap(unsorted_list)
print(f"Heapified list: {
heap_from_list.heap}")
print("
Polling from heapified list to verify order:")
while not heap_from_list.is_empty():
print(f" Polled {
heap_from_list.poll()}", end="")
print()
7.5 Python标准库中的heapq
Python的强大之处在于其“自带电池”的哲学。对于堆和优先队列，标准库提供了一个高度优化的heapq模块。heapq直接在一- 个普通的Python列表上进行操作，它实现了我们刚才讨论的所有核心算法。
heapq.heappush(heap_list, item): 向列表heap_list中插入item，并维持堆属性。等同于我们的insert。
heapq.heappop(heap_list): 从列表heap_list中弹出并返回最小值。等同于我们的poll。
heapq.heapify(list): 将一个普通列表原地转换成一个最小堆。等同于我们的heapify方法。
heapq.heappushpop(heap_list, item): 先推入item，再弹出最小值。比先heappush再heappop更高效。
heapq.heapreplace(heap_list, item): 先弹出最小值，再推入item。
使用heapq实现最大堆
heapq默认只实现了最小堆。如果我们需要一个最大堆怎么办？一个非常聪明的技巧是：在存入数据时，存入其相反数（或对于复杂对象，存入一个带相反数优先级的元组）。
import heapq
# --- 使用heapq ---
print("
--- Using Python's built-in heapq module ---")
# 最小堆
min_heap_pq = []
heapq.heappush(min_heap_pq, 10)
heapq.heappush(min_heap_pq, 4)
heapq.heappush(min_heap_pq, 15)
print(f"Min heap list: {
min_heap_pq}")
print(f"Popped min value: {
heapq.heappop(min_heap_pq)}")
# 最大堆 (通过存储相反数)
max_heap_pq = []
heapq.heappush(max_heap_pq, -1 * 10) # 存入 -10
heapq.heappush(max_heap_pq, -1 * 4) # 存入 -4
heapq.heappush(max_heap_pq, -1 * 15) # 存入 -15
print(f"
Max heap list (stored as negatives): {
max_heap_pq}")
# 弹出时，-15是最小值，代表15是最大值
max_val = -1 * heapq.heappop(max_heap_pq)
print(f"Popped max value: {
max_val}")
# 使用heapify
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
print(f"
Original data: {
data}")
heapq.heapify(data)
print(f"Data after heapify: {
data}")
7.6 堆的杀手级应用：堆排序（Heap Sort）
我们已经看到，堆结构能够以O(log n)的效率插入元素和提取极值。这一特性使其成为实现高效排序算法的理想工具。堆排序（Heap Sort）是一种精妙的、基于比较的排序算法，它利用堆的特性，在不使用额外主存储空间（即原地排序，In-place）的情况下，达到了O(n log n)的时间复杂度。
堆排序的过程分为两个主要阶段：
建堆阶段: 将待排序的无序数组，原地构建成一个最大堆（或最小堆）。
排序阶段: 不断地从堆顶取出最大（或最小）元素，并将其放置到数组末尾的已排序部分。
我们将以升序排序为例，因此我们需要构建一个最大堆。
堆排序详细步骤（升序）:
构建最大堆:
使用我们之前学到的O(n)的Heapify算法，将整个无序数组原地转换成一个最大堆。
经过此步骤后，数组中最大的元素已经被移动到了数组的第一个位置（即堆顶）。
循环提取与交换:
交换: 将堆顶元素（当前数组中的最大值）与堆的最后一个元素（即数组当前有效范围的末尾元素）进行交换。
“隔离”最大值: 经过交换，当前已知的最大值被正确地放置在了数组的最末端。我们将堆的有效大小减一，将这个已排序好的元素“隔离”出堆的范围。
恢复堆属性: 交换到堆顶的新元素很可能会破坏最大堆的属性。因此，我们需要对新的根节点执行一次**sift_down**操作，使其下沉到合适的位置，从而让剩余的n-1个元素重新构成一个合法的最大堆。
重复: 不断重复“交换-隔离-下沉”这个过程，每次都将当前堆中的最大元素移动到已排序区域的前端。直到堆的大小变为1，排序完成。
堆排序的魅力:
原地排序: 除了少数用于存储临时变量的空间外，它不需要额外的数组来辅助排序，空间复杂度为O(1).
性能稳定: 无论是最好、最坏还是平均情况，其时间复杂度都是O(n log n). 建堆阶段是O(n)，之后循环n-1次，每次sift_down是O(log n)，所以总复杂度为O(n + (n-1)log n) = O(n log n). 它不像快速排序那样在最坏情况下会退化到O(n²).
堆排序的Python实现
# heap_sort.py
def sift_down_max(arr, start_node_index, heap_size):
"""
最大堆的下沉操作。
这是一个辅助函数，它将一个子树调整为最大堆。
arr: 存储堆的数组
start_node_index: 需要下沉的节点的索引 (子树的根)
heap_size: 堆的有效大小 (因为排序过程中堆会不断缩小)
"""
largest_index = start_node_index # 假设当前节点是最大的
left_child_index = 2 * start_node_index + 1 # 左孩子的索引
right_child_index = 2 * start_node_index + 2 # 右孩子的索引
# 检查左孩子是否存在，并且是否比当前最大节点还大
if left_child_index < heap_size and arr[left_child_index] > arr[largest_index]:
largest_index = left_child_index # 如果是，更新最大节点的索引
# 检查右孩子是否存在，并且是否比当前最大节点还大
if right_child_index < heap_size and arr[right_child_index] > arr[largest_index]:
largest_index = right_child_index # 如果是，更新最大节点的索引
# 如果最大的节点不是原来的起始节点，说明需要交换和继续下沉
if largest_index != start_node_index:
# 交换位置
arr[start_node_index], arr[largest_index] = arr[largest_index], arr[start_node_index]
# 交换后，以原先较大孩子为根的子树可能被破坏，所以需要递归地对那个子树进行下沉
sift_down_max(arr, largest_index, heap_size)
def heap_sort(arr):
"""
对一个列表进行原地堆排序 (升序)。
"""
n = len(arr) # 获取数组的长度
# --- 阶段一: 构建最大堆 ---
# 从最后一个非叶子节点开始，向前遍历到根节点
# 对每个非叶子节点执行sift_down，将其所在的子树调整为最大堆
# 遍历结束后，整个数组就构成了一个最大堆
start_of_heapify = (n // 2) - 1
for i in range(start_of_heapify, -1, -1):
sift_down_max(arr, i, n) # 调用下沉函数，此时堆的大小是整个数组n
print(f"Max Heap Built: {
arr}") # 打印建堆后的结果
# --- 阶段二: 循环提取元素并排序 ---
# 从数组的最后一个元素开始，向前遍历到第二个元素
for i in range(n - 1, 0, -1):
# 将堆顶元素 (当前最大值) 与当前堆的最后一个元素交换
arr[i], arr[0] = arr[0], arr[i]
# 交换后，将已排序好的元素arr[i]排除在堆外
# 对缩小后的堆 (大小为i)，从根节点0开始执行下沉操作，以恢复最大堆属性
sift_down_max(arr, 0, i)
# --- 使用我们自己实现的堆排序 ---
my_list = [12, 11, 13, 5, 6, 7, 30, 2, 9]
print(f"Original list: {
my_list}")
heap_sort(my_list)
print(f"Sorted list: {
my_list}")
another_list = [3, 2, 1, 5, 6, 4, 9, 8, 7]
print(f"
Original list: {
another_list}")
heap_sort(another_list)
print(f"Sorted list: {
another_list}")
7.7 更多应用场景：Top-K 问题
堆的另一个经典应用场景是解决“Top-K 问题”，即从一个巨大的数据集中，找出最大或最小的 K 个元素。例如，从数百万条用户评论中，找出点赞数最多的100条；或者从一个实时数据流中，持续追踪流量最高的10个IP地址。
如果数据集非常大，无法一次性载入内存，那么先完整排序再取前K个的方法是不可行的。而堆提供了一种内存友好且高效的解决方案。
算法思想：寻找最大的K个元素
维护一个大小为K的最小堆: 我们创建一个最小堆，这个堆将用来存储我们“目前为止”找到的最大的K个元素。
初始化: 首先，从数据集中读取前 K 个元素，用它们构建这个最小堆。此时，堆顶的元素是这K个元素中最小的那个。
遍历剩余数据: 继续遍历数据集中的剩余元素（从第 K+1 个开始）。对于每一个新元素 x：
将 x 与堆顶元素（即当前已发现的Top-K元素中的最小值）进行比较。
如果 x 比堆顶元素还要小，说明 x 不可能成为Top-K之一，直接忽略它。
如果 x 比堆顶元素大，说明 x 有潜力成为新的Top-K之一，而当前的堆顶元素则应该被“淘汰”。我们执行一次**heapreplace**操作（或先heappop再heappush）：移除堆顶的旧最小值，并将新元素x插入堆中。
最终结果: 当遍历完整个数据集后，这个大小为K的最小堆里剩下的，就是整个数据集中最大的K个元素。
为什么这个方法如此高效？
内存占用恒定: 无论原始数据集有多大，我们始终只需要维护一个大小为K的堆，内存占用为O(K).
时间复杂度: 遍历N个元素，对于每个元素，最多进行一次堆操作（比较和可能的替换），成本为O(log K). 因此，总时间复杂度为O(N log K). 这远远优于对整个数据集排序的O(N log N)。
Top-K问题的Python实现
import heapq
def find_top_k_largest(data_stream, k):
"""
从一个数据流或迭代器中找到最大的K个元素。
data_stream: 一个可迭代对象，如列表、文件句柄等
k: 需要找出的元素数量
"""
# 创建一个大小为k的最小堆
min_heap = []
# 首先处理数据流中的前k个元素
for item in data_stream:
if len(min_heap) < k:
# 如果堆还没满，直接将元素推入
heapq.heappush(min_heap, item)
else:
# 如果堆已满，且当前元素比堆顶(当前k个中的最小值)还大
if item > min_heap[0]:
# 使用heapreplace来替换堆顶元素，这比pop再push更高效
heapq.heapreplace(min_heap, item)
# 此时，min_heap中存储的就是最大的k个元素
# 它们在堆中是无序的，如果需要有序的结果，可以再进行一次排序
return sorted(min_heap, reverse=True)
# --- 使用Top-K算法 ---
# 模拟一个巨大的数据流
large_dataset = [99, 12, 34, 56, 78, 1, 3, 5, 23, 45, 87, 65, 43, 21, 88, 102, 130, 55, 66, 77]
K = 5
print(f"Finding top {
K} largest elements in the dataset.")
top_k_elements = find_top_k_largest(large_dataset, K)
print(f"The {
K} largest elements are: {
top_k_elements}")
# 验证一下
large_dataset.sort(reverse=True)
print(f"Verification using full sort: {
large_dataset[:K]}")
第八章：图论基础 —— 连接万物的网络
我们即将开启一段全新的旅程，进入一个更加普适、更能代表现实世界复杂关系的数据结构领域——图（Graph）。如果说树形结构为我们描绘了清晰的层级关系，那么图则为我们展现了万物互联的复杂网络。
从本质上讲，树是一种特殊的图，是一种无环的连通图。而图论的范畴则要广阔得多。它研究的不再是父子之间的单向依赖，而是节点之间任意复杂的连接关系。思考一下我们身边的世界：
社交网络: 每个人是一个节点，好友关系是一条边，构成了一张巨大的社交图。
城市交通: 每个路口是一个节点，每条街道是一条边，构成了城市的交通图。边的“权重”可以是街道的长度或拥堵状况。
互联网: 每个路由器或服务器是一个节点，物理或逻辑链路是一条边，构成了互联网的拓扑图。
项目依赖: 每个任务是一个节点，如果任务A必须在任务B之前完成，就有一条从A到B的有向边，构成了项目的依赖图（关键路径分析的基础）。
知识图谱: 每个概念是一个节点，概念之间的关系（如“属于”、“包含”、“作者是”）是一条边，构成了庞大的知识网络。
图论算法是计算机科学的支柱之一，是解决路径规划、网络流量分析、资源分配、推荐系统等无数核心问题的理论基石。
8.1 图的语言：基本概念与分类
一个图 G 是由一个顶点集合 V (Vertex Set) 和一个边集合 E (Edge Set) 组成的。我们通常记为 G = (V, E)。一条边 e 连接了两个顶点 u 和 v，我们记为 e = (u, v)。
图的分类学:
无向图 (Undirected Graph):
边是没有方向的。边 (u, v) 和 (v, u) 代表的是同一条边。
例子：Facebook的好友关系是双向的，你是我好友，我也是你好友。
有向图 (Directed Graph or Digraph):
边是有方向的。边 (u, v) 代表一条从 u 指向 v 的边，这与从 v 指向 u 的边是不同的。
在有向图中，u 被称为边的起点 (tail)，v 被称为边的终点 (head)。
例子：Twitter的已关注关系是单向的，我已关注了你，但你未必已关注我。
未加权图 (Unweighted Graph):
所有的边都被认为是等价的，没有与之关联的成本或距离。
我们只关心节点之间是否存在连接，不关心连接的“代价”。
加权图 (Weighted Graph):
每条边 e 都有一个与之关联的数值，称为权重 (weight) 或 成本 (cost)，记为 w(e).
权重可以代表距离、时间、费用、带宽等任何可量化的度量。
例子：地图应用中，两个地点之间的权重可以是实际的驾车距离或预计的通行时间。
更多图论术语:
邻接 (Adjacent): 如果两个顶点 u 和 v 之间存在一条边，我们称它们是邻接的。
度 (Degree):
在无向图中，一个顶点的度是指与它相连的边的数量。
在有向图中，一个顶点的度分为出度 (Out-degree)（从该顶点出发的边的数量）和入度 (In-degree)（指向该顶点的边的数量）。
路径 (Path): 从顶点 u到顶点 v 的一条路径，是一个顶点序列 (v₀, v₁, ..., vₖ)，其中 v₀=u，vₖ=v，且对于任意 0 <= i < k，(vᵢ, vᵢ₊₁) 都是图中的一条边。
路径长度 (Path Length): 路径中边的数量。在加权图中，通常指路径上所有边的权重之和。
环 (Cycle): 一条起点和终点是同一个顶点的路径。
无环图 (Acyclic Graph): 不包含任何环的图。
有向无环图 (Directed Acyclic Graph, DAG): 一种非常重要的图结构，常用于表示依赖关系和任务调度。
连通图 (Connected Graph): 在一个无向图中，如果对于任意两个不同的顶点 u 和 v，都存在一条从 u 到 v 的路径，那么这个图是连通的。
强连通图 (Strongly Connected Graph): 在一个有向图中，如果对于任意两个不同的顶点 u 和 v，既存在从 u 到 v 的路径，也存在从 v 到 u 的路径，那么这个图是强连通的。
子图 (Subgraph): 一个图 G' 是 G 的子图，如果 G' 的顶点集和边集都是 G 的子集。
8.2 图的编码表示：邻接矩阵与邻接表
要在计算机程序中处理图，我们首先需要一种方式来存储它的结构。最主流的两种表示方法是邻接矩阵 (Adjacency Matrix) 和 邻接表 (Adjacency List)。选择哪种方法，取决于图的特性（主要是边的密度）和我们期望高效执行的操作类型。
8.2.1 邻接矩阵 (Adjacency Matrix)
邻接矩阵使用一个二维数组（或矩阵）来表示图。如果图有 |V| 个顶点，我们就创建一个 |V| x |V| 的矩阵 M。
表示方法:
对于未加权图，如果顶点 i 和顶点 j 之间存在一条边，则 M[i][j] = 1；否则 M[i][j] = 0。
对于加权图，M[i][j] 可以存储从 i 到 j 的边的权重。如果边不存在，可以用一个特殊值（如 0, ∞ 或 None）来表示。
对于无向图，矩阵是对称的，即 M[i][j] = M[j][i]。
示例: 一个无向未加权图
(A) --- (B)
| |
| |
| (D) |
| |
(C) --- /
顶点: A=0, B=1, C=2, D=3
邻接矩阵:
A B C D
A[0,1,1,1]
B[1,0,1,0]
C[1,1,0,0]
D[1,0,0,0]
邻接矩阵的优缺点:
优点:
快速检查邻接性: 检查任意两个顶点 i 和 j 之间是否存在边，只需要 O(1) 的时间复杂度，直接访问 M[i][j] 即可。
实现简单: 概念直观，易于用二维数组实现。
缺点:
空间成本高: 无论图中有多少条边，都需要 O(|V|²) 的空间。对于稀疏图（Sparse Graph，即边的数量 |E| 远小于 |V|²），这是巨大的空间浪费。
遍历邻居效率低: 要找出某个顶点的所有邻居，需要遍历矩阵的一整行，时间复杂度为 O(|V|).
8.2.2 邻接表 (Adjacency List)
邻接表是表示稀疏图的更高效的方式。它由一个包含 |V| 个链表（或动态数组）的数组构成。数组的第 i 个位置存储了一个链表，该链表包含了所有与顶点 i 邻接的顶点。
表示方法:
Adj[i] 是一个列表，包含了所有满足 (i, v) 是一条边的顶点 v。
对于加权图，这个列表可以存储元组 (v, weight)，表示邻接顶点和边的权重。
对于无向图，如果存在边 (u, v)，那么 v 会出现在 Adj[u] 的列表中，同时 u 也会出现在 Adj[v] 的列表中。
示例 (同一个图):
(A) --- (B)
| |
| |
| (D) |
| |
(C) --- /
顶点: A=0, B=1, C=2, D=3
邻接表:
A (0) -> [B(1), C(2), D(3)]
B (1) -> [A(0), C(2)]
C (2) -> [A(0), B(1)]
D (3) -> [A(0)]
邻接表的优缺点:
优点:
空间效率高: 只需要 O(|V| + |E|) 的空间。|V| 用于存储数组的头部，|E| 用于存储所有的邻接关系（在无向图中是 2*|E|）。这对于稀疏图来说非常节省空间。
遍历邻居效率高: 找出某个顶点的所有邻居，只需要遍历其对应的链表，时间复杂度为 O(degree(v))，即该顶点的度。
缺点:
检查邻接性较慢: 检查任意两个顶点 u 和 v 之间是否存在边，需要遍历 u 的邻接表来查找 v，最坏情况下的时间复杂度为 O(degree(u))。
8.2.3 Python代码实现图的表示
# graph_representations.py
from collections import defaultdict
class Graph:
"""
一个通用的图的基类，定义了图的基本接口。
这个实现使用邻接表，因为它在大多数情况下更高效。
"""
def __init__(self, directed=False):
# 使用defaultdict(list)可以简化添加边的操作
# 当我们第一次访问一个新顶点时，它会自动创建一个空列表作为其邻接表
self._adjacency_list = defaultdict(list)
self._vertex_count = 0
self._edge_count = 0
self.directed = directed # 标记图是否为有向图
def add_vertex(self, vertex_key):
"""向图中添加一个顶点。"""
# defaultdict的存在使得这个操作隐式完成，但我们可以显式调用以清晰表达
# 如果顶点已存在，defaultdict不会做任何事
if vertex_key not in self._adjacency_list:
self._adjacency_list[vertex_key] # 确保顶点存在于字典中
self._vertex_count += 1
def add_edge(self, from_vertex, to_vertex, weight=1):
"""向图中添加一条边。"""
# 首先确保两个顶点都存在于图中
self.add_vertex(from_vertex)
self.add_vertex(to_vertex)
# 添加从 from_vertex 到 to_vertex 的边
# 存储为元组 (邻接顶点, 权重)
self._adjacency_list[from_vertex].append((to_vertex, weight))
self._edge_count += 1
# 如果是无向图，需要同时添加一条反向的边
if not self.directed:
self._adjacency_list[to_vertex].append((from_vertex, weight))
# 注意：在无向图中，一条边被存储了两次，但我们只算作一条边
def get_neighbors(self, vertex_key):
"""获取一个顶点的所有邻居及其权重。"""
return self._adjacency_list.get(vertex_key, [])
def get_vertices(self):
"""获取图中的所有顶点。"""
return list(self._adjacency_list.keys())
@property
def vertex_count(self):
"""返回图的顶点数。"""
return len(self._adjacency_list)
@property
def edge_count(self):
"""返回图的边数。"""
if self.directed:
return self._edge_count
# 对于无向图，每条边被记录了两次，所以需要除以2
return self._edge_count // 2
def __str__(self):
"""返回图的字符串表示。"""
output = ""
for vertex in self.get_vertices():
neighbors = self.get_neighbors(vertex)
neighbor_str = ", ".join([f"{
n}(w:{
w})" for n, w in neighbors])
output += f"{
vertex} -> [ {
neighbor_str} ]
"
return output
# --- 使用我们实现的图类 ---
print("--- Building a Directed Weighted Graph ---")
directed_graph = Graph(directed=True)
directed_graph.add_edge('A', 'B', 5) # 添加从A到B的边，权重为5
directed_graph.add_edge('A', 'C', 3) # 添加从A到C的边，权重为3
directed_graph.add_edge('B', 'C', 2) # 添加从B到C的边，权重为2
directed_graph.add_edge('B', 'D', 6) # 添加从B到D的边，权重为6
directed_graph.add_edge('C', 'D', 7) # 添加从C到D的边，权重为7
directed_graph.add_edge('C', 'E', 4) # 添加从C到E的边，权重为4
directed_graph.add_edge('D', 'E', 1) # 添加从D到E的边，权重为1
directed_graph.add_edge('E', 'A', 9) # 添加从E到A的边，权重为9
print(directed_graph)
print(f"Vertices: {
directed_graph.get_vertices()}")
print(f"Number of vertices: {
directed_graph.vertex_count}")
print(f"Number of edges: {
directed_graph.edge_count}")
print(f"Neighbors of C: {
directed_graph.get_neighbors('C')}")
print("
--- Building an Undirected Unweighted Graph ---")
undirected_graph = Graph() # 默认是无向图
undirected_graph.add_edge('Alice', 'Bob') # 权重默认为1
undirected_graph.add_edge('Alice', 'Charlie')
undirected_graph.add_edge('Bob', 'David')
undirected_graph.add_edge('Charlie', 'David')
undirected_graph.add_edge('Charlie', 'Eve')
print(undirected_graph)
print(f"Vertices: {
undirected_graph.get_vertices()}")
print(f"Number of vertices: {
undirected_graph.vertex_count}")
print(f"Number of edges: {
undirected_graph.edge_count}")
print(f"Neighbors of Charlie: {
undirected_graph.get_neighbors('Charlie')}")
8.3 图的遍历：探索网络的脉络
我们已经学会了如何用代码来构建一张图，但一个静态的图结构本身意义有限。图的真正威力在于我们能够在其上执行算法，而几乎所有高级图算法的起点，都是图的遍历（Graph Traversal）。
图遍历是指从图的某个顶点出发，系统性地访问图中所有可达的顶点，并且保证每个顶点只被访问一次。这就像在一个错综复杂的城市路网中，找到一种方法，确保你能走遍所有与起点连通的路口，且不重复走冤枉路。
图遍历是解决许多基础图问题的核心：
连通性判断: 从一个顶点出发，看能访问到多少其他顶点，从而可以判断图的连通分量。
路径搜索: 寻找从A点到B点是否存在路径。
拓扑排序: 在有向无环图中，为所有顶点排出一个线性的次序，满足所有依赖关系。
最短路径: 作为更复杂的最短路径算法（如Dijkstra算法）的基础。
与树的遍历（前序、中序、后序）不同，图的结构更加自由，甚至可能包含环（Cycle）。这就带来了一个关键的挑战：我们必须有一种机制来记录哪些顶点已经被访问过，以避免在环里无限循环，或者对同一个顶点进行重复处理。这个机制通常是一个名为visited的集合或哈希表。
我们将深入学习两种最基本、最强大的图遍历策略：广度优先搜索（Breadth-First Search, BFS）和深度优先搜索（Depth-First Search, DFS）。它们探索图的方式截然不同，也因此各自适用于不同的问题场景。
8.4 广度优先搜索（BFS）：如水波般蔓延
广度优先搜索（BFS）是一种“广”字当头的遍历策略。它的核心思想可以比作向平静的湖面投下一颗石子，激起的涟SHI波会从中心点开始，一层一层地、均匀地向外扩散。
BFS从一个指定的源顶点 s 开始，首先访问所有与 s 直接相邻的顶点（距离为1的邻居）。然后，它再访问所有与这些邻居相邻的、尚未被访问过的顶点（距离为2的邻居），以此类推，一层一层地向外探索，直到所有从 s 可达的顶点都被访问过。
8.4.1 BFS的算法核心：队列
为了实现这种“先到先服务”式的分层探索，BFS完美地利用了**队列（Queue）**这种数据结构。队列的先进先出（FIFO）特性，保证了我们总是在处理完当前层的所有顶点之后，才会开始处理下一层的顶点。
BFS算法的机械舞步:
初始化:
创建一个队列 Q，并将源顶点 s 入队。
创建一个集合 visited，用来记录已访问或已在队列中等待访问的顶点。将 s 加入 visited。
循环探索:
当队列 Q 不为空时，持续循环：
a. 出队: 从队列头部取出一个顶点 u。
b. 处理: 对顶点 u 进行你需要的操作（例如，打印它，检查它是否是目标顶点等）。
c. 探索邻居: 遍历 u 的所有邻居 v。
d. 检查与入队: 对于每一个邻居 v，如果它没有在 visited 集合中：
i. 将其加入 visited 集合。
ii. 将其加入队列 Q 的尾部。
8.4.2 BFS的超能力：寻找最短路径
BFS最引人注目的特性是：在未加权图中，它找到的从源顶点 s 到任何其他可达顶点 v 的路径，必然是最短路径（即包含边数最少的路径）。
为什么？因为BFS是按“距离”逐层探索的。它首先找到所有距离为1的顶点，然后是所有距离为2的顶点，以此类推。所以，当它第一次到达某个顶点 v 时，必然是通过一条包含最少边数的路径到达的。如果存在一条更短的路径，那么 v 按理说应该在更早的层级就被发现了，这与算法的执行顺序相矛盾。
这个特性使得BFS成为解决“最少步骤”、“最少换乘”等问题的利器。
8.4.3 BFS的实现与分析
我们将为之前创建的Graph类添加一个bfs方法。
# graph_algorithms.py
# (假设Graph类已在graph_representations.py中定义)
from graph_representations import Graph
from collections import deque # 使用deque作为高效的队列
class GraphAlgorithms(Graph):
"""
一个继承自Graph的类，用于封装图算法。
"""
def bfs(self, start_vertex):
"""
执行广度优先搜索。
start_vertex: 搜索的起始顶点。
返回一个列表，包含按BFS顺序访问的顶点。
"""
if start_vertex not in self._adjacency_list: # 检查起始顶点是否存在
print(f"Error: Start vertex '{
start_vertex}' not in graph.")
return []
visited = set() # 创建一个集合来存储已访问的顶点，提供O(1)的查找效率
queue = deque([start_vertex]) # 创建一个双端队列，并将起始顶点放入
visited.add(start_vertex) # 将起始顶点标记为已访问
traversal_path = [] # 用来记录遍历的路径
while queue: # 当队列不为空时，循环继续
current_vertex = queue.popleft() # 从队列头部取出一个顶点
traversal_path.append(current_vertex) # 将当前顶点加入遍历路径
# 遍历当前顶点的所有邻居
for neighbor, weight in self.get_neighbors(current_vertex):
if neighbor not in visited: # 如果邻居还未被访问
visited.add(neighbor) # 将邻居标记为已访问
queue.append(neighbor) # 将邻居加入队列尾部，等待未来访问
return traversal_path
def bfs_shortest_path(self, start_vertex, end_vertex):
"""
使用BFS寻找未加权图中最短路径。
返回一个元组 (路径长度, 路径列表)。
"""
if start_vertex not in self._adjacency_list or end_vertex not in self._adjacency_list:
return -1, [] # 如果起点或终点不存在，返回错误
visited = {
start_vertex} # 记录已访问的节点
# 队列中存储的不再只是顶点，而是到达该顶点的路径
queue = deque([[start_vertex]])
while queue:
path = queue.popleft() # 取出一条路径
current_vertex = path[-1] # 路径的最后一个节点是当前节点
if current_vertex == end_vertex: # 如果到达终点
return len(path) - 1, path # 返回路径长度(边数)和路径本身
for neighbor, _ in self.get_neighbors(current_vertex):
if neighbor not in visited:
visited.add(neighbor) # 标记为已访问
new_path = list(path) # 创建一条新路径
new_path.append(neighbor) # 将邻居追加到新路径上
queue.append(new_path) # 将新路径入队
return -1, [] # 如果队列为空还没找到，说明不连通
# --- 使用BFS算法 ---
# 创建一个无向图用于演示
social_net = GraphAlgorithms()
social_net.add_edge('A', 'B')
social_net.add_edge('A', 'C')
social_net.add_edge('B', 'D')
social_net.add_edge('B', 'E')
social_net.add_edge('C', 'F')
social_net.add_edge('E', 'F')
social_net.add_edge('E', 'G')
social_net.add_edge('F', 'H')
social_net.add_edge('G', 'H')
print("--- BFS Traversal ---")
start_node = 'A'
bfs_path = social_net.bfs(start_node)
print(f"BFS traversal starting from '{
start_node}': {
' -> '.join(bfs_path)}")
print("
--- BFS Shortest Path ---")
start, end = 'A', 'H'
distance, shortest_path = social_net.bfs_shortest_path(start, end)
if distance != -1:
print(f"Shortest path from '{
start}' to '{
end}' has {
distance} edges.")
print(f"Path: {
' -> '.join(shortest_path)}")
else:
print(f"No path found from '{
start}' to '{
end}'.")
start, end = 'A', 'D'
distance, shortest_path = social_net.bfs_shortest_path(start, end)
if distance != -1:
print(f"
Shortest path from '{
start}' to '{
end}' has {
distance} edges.")
print(f"Path: {
' -> '.join(shortest_path)}")
复杂度分析:
时间复杂度: O(|V| + |E|)。每个顶点最多入队和出队一次，这部分是O(|V|)。在整个过程中，我们遍历了每个顶点的邻接表，对于整个图来说，所有邻接表的总长度在有向图中是|E|，在无向图中是2|E|。所以总的时间复杂度是线性的。
空间复杂度: O(|V|)。在最坏的情况下（例如一个星形图），队列中可能需要存储|V|-1个顶点。visited集合也需要O(|V|)的空间。
8.5 深度优先搜索（DFS）：不撞南墙不回头
与BFS的广度探索相反，深度优先搜索（DFS）的策略是“一路走到黑”。它从源顶点 s 开始，选择一个邻居，然后深入探索这个邻居，再选择该邻居的一个邻居继续深入… 这个过程会一直持续下去，直到到达一个没有未访问邻居的“死胡同”顶点。这时，算法会**回溯（Backtrack）**到上一个顶点，并尝试探索其另一条尚未走过的分支。
DFS的探索路径就像在解一个迷宫：你总是沿着一条路走到尽头，碰壁了再退回来，换条路继续走。
8.5.1 DFS的算法核心：栈
为了实现这种“后进先出”的回溯行为，DFS天然地与**栈（Stack）**这种数据结构相契合。DFS的实现通常有两种方式：
递归实现: 利用系统内置的函数调用栈来隐式地管理回溯过程。这是最自然、最简洁的实现方式。
迭代实现: 使用一个显式的栈数据结构来模拟递归过程，避免在图很深时可能出现的栈溢出问题。
DFS算法的机械舞步（递归版）:
主函数 dfs(start_vertex):
创建一个 visited 集合。
调用辅助函数 _dfs_recursive(start_vertex, visited)。
辅助函数 _dfs_recursive(u, visited):
a. 标记与处理: 将当前顶点 u 加入 visited 集合，并立即处理它（例如，打印）。
b. 探索邻居: 遍历 u 的所有邻居 v。
c. 递归深入: 如果邻居 v 没有在 visited 集合中，则对 v 递归调用 _dfs_recursive(v, visited)。
8.5.2 DFS的应用：拓扑排序与环路检测
DFS的“深入探索”特性使其非常适合解决涉及路径、连通性和依赖关系的问题。
连通分量: 在非连通图中，可以通过多次调用DFS（每次选择一个未访问过的节点作为起点）来找出所有的连通分量。
环路检测: 在DFS的遍历过程中，如果我们遇到了一个已经被访问过、但它不是我们直接的父节点的顶点（在无向图中），或者我们遇到了一个正在当前递归路径上（即在函数调用栈中）的顶点（在有向图中），那就意味着我们发现了一个环。
拓扑排序: 对于一个有向无环图（DAG），DFS遍历完成的“完成时间”的逆序，就是该图的一个拓扑排序。这对于解决任务调度等依赖性问题至关重要。
8.5.3 DFS的实现与分析
我们将继续在GraphAlgorithms类中添加DFS的实现。
# (继续在 graph_algorithms.py 中添加)
class GraphAlgorithms(Graph):
# ... (之前的bfs等方法) ...
def dfs(self, start_vertex):
"""
深度优先搜索的公共接口。
它处理图可能不连通的情况。
返回一个列表，包含按DFS顺序访问的顶点。
"""
if not self._adjacency_list: # 如果图为空
return []
traversal_path = [] # 记录完整的遍历路径
visited = set() # 记录所有已访问的顶点
# 首先处理指定的起始顶点
if start_vertex in self._adjacency_list:
self._dfs_recursive(start_vertex, visited, traversal_path)
# 然后，处理图中可能存在的、与start_vertex不连通的其他组件
for vertex in self.get_vertices():
if vertex not in visited:
self._dfs_recursive(vertex, visited, traversal_path)
return traversal_path
def _dfs_recursive(self, u, visited, path):
"""DFS的递归辅助函数。"""
visited.add(u) # 将当前顶点标记为已访问
path.append(u) # 将当前顶点加入遍历路径
# 遍历当前顶点的所有邻居
for neighbor, weight in self.get_neighbors(u):
if neighbor not in visited: # 如果邻居还未被访问
# 对该邻居进行递归调用，深入探索
self._dfs_recursive(neighbor, visited, path)
def has_cycle_directed(self):
"""
使用DFS检测有向图中是否存在环。
返回 True 如果有环，否则 False。
"""
visited = set() # 记录已访问过的节点
# recursion_stack 记录当前DFS递归路径上的节点
recursion_stack = set()
for vertex in self.get_vertices():
if vertex not in visited:
# 对每个未访问过的节点启动一次DFS环检测
if self._has_cycle_directed_util(vertex, visited, recursion_stack):
return True
return False
def _has_cycle_directed_util(self, u, visited, recursion_stack):
"""有向图环检测的递归辅助函数。"""
visited.add(u) # 标记当前节点为已访问
recursion_stack.add(u) # 将当前节点加入当前递归路径
for neighbor, _ in self.get_neighbors(u):
if neighbor not in visited: # 如果邻居未被访问过
if self._has_cycle_directed_util(neighbor, visited, recursion_stack):
return True # 如果在更深的递归中发现了环，直接返回True
elif neighbor in recursion_stack:
# 如果邻居已被访问，并且还在当前的递归路径上，说明找到了一个“返祖边”，即环
return True
# 当从节点u出发的所有路径都探索完毕后，将其从递归路径中移除
recursion_stack.remove(u)
return False
# --- 使用DFS算法 ---
# 使用之前创建的社交网络图
print("
--- DFS Traversal ---")
dfs_path = social_net.dfs('A')
print(f"DFS traversal starting from 'A': {
' -> '.join(dfs_path)}")
# 创建一个有向图用于环检测
cyclic_graph = GraphAlgorithms(directed=True)
cyclic_graph.add_edge('A', 'B')
cyclic_graph.add_edge('B', 'C')
cyclic_graph.add_edge('C', 'A') # 形成了 A -> B -> C -> A 的环
cyclic_graph.add_edge('C', 'D')
acyclic_graph = GraphAlgorithms(directed=True)
acyclic_graph.add_edge('A', 'B')
acyclic_graph.add_edge('B', 'C')
acyclic_graph.add_edge('C', 'D')
print("
--- Cycle Detection in Directed Graphs ---")
print(f"Does cyclic_graph have a cycle? {
cyclic_graph.has_cycle_directed()}")
print(f"Does acyclic_graph have a cycle? {
acyclic_graph.has_cycle_directed()}")
复杂度分析: DFS的复杂度分析与BFS完全相同。每个顶点和每条边都只被访问一次。
时间复杂度: O(|V| + |E|)。
空间复杂度: O(|V|)。在递归实现中，空间主要消耗在函数调用栈上，最坏情况下（一条链状的图），栈的深度可以达到|V|。
8.6 BFS vs. DFS：如何选择正确的工具
| 特性 | 广度优先搜索 (BFS) | 深度优先搜索 (DFS) |
|---|---|---|
| 数据结构 | 队列 (Queue) | 栈 (Stack)，可以是隐式的递归栈或显式栈 |
| 探索模式 | 一层一层地向外扩展，像水波。 | 一条路走到黑，不撞南墙不回头。 |
| 路径结果 | 找到的从起点到终点的路径是最短的（在未加权图中）。 | 找到的路径不一定是最短的，但能找到一条路径。 |
| 适用场景 | 最短路径问题（未加权图）、社交网络中寻找“N度好友”、网络爬虫（分层爬取）。 | 环路检测、拓扑排序、寻找连通分量、解决迷宫或路径存在性问题。 |
| 空间使用 | 对于“又宽又浅”的图，队列可能变得很大。 | 对于“又窄又深”的图，递归栈可能变得很深。 |
理解BFS和DFS的内在逻辑和行为差异，是掌握更高级图算法的第一步。它们是解决无数图论问题的基本“词汇”，后续我们将学习的Dijkstra、Prim、Kruskal等算法，都或多或少地带有它们的影子。
暂无评论内容