Hello 算法

动画图解、一键运行的数据结构与算法教程

Computer Science
Python
Author

Shitao5

Published

2023-09-14

Modified

2023-10-07

Progress

Learning Progress: 46.25%.

Learning Source

1 初识算法

  • 实际上，许多算法并不涉及复杂数学，而是更多地依赖于基本逻辑，这些逻辑在我们的日常生活中处处可见。

  • 「算法 algorithm」是在有限时间内解决特定问题的一组指令或操作步骤，它具有以下特性。

    • 问题是明确的，包含清晰的输入和输出定义。

    • 具有可行性，能够在有限步骤、时间和内存空间下完成。

    • 各步骤都有确定的含义，相同的输入和运行条件下，输出始终相同。

  • 「数据结构 data structure」是计算机中组织和存储数据的方式，具有以下设计目标。

    • 空间占用尽量减少，节省计算机内存。

    • 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。

    • 提供简洁的数据表示和逻辑信息，以便使得算法高效运行。

  • 数据结构与算法高度相关、紧密结合，具体表现以下三个方面。

    • 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及用于操作数据的方法。

    • 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。

    • 算法通常可以基于不同的数据结构进行实现，但执行效率可能相差很大，选择合适的数据结构是关键。

  • 数据结构与算法是独立于编程语言的。

  • 在实际讨论时，我们通常会将“数据结构与算法”简称为“算法”。比如众所周知的 LeetCode 算法题目，实际上同时考察了数据结构和算法两方面的知识。

2 复杂度分析

2.1 算法与效率评估

  • 复杂度分析体现算法运行所需的时间（空间）资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。这个定义有些拗口，我们可以将其分为三个重点来理解。

    • “时间和空间资源”分别对应「时间复杂度 time complexity」和「空间复杂度 space complexity」。

    • “随着输入数据大小的增加”意味着复杂度反映了算法运行效率与输入数据体量之间的关系。

    • “时间和空间的增长趋势”表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的“快慢”。

  • 复杂度分析克服了实际测试方法的弊端，体现在以下两个方面。

    • 它独立于测试环境，分析结果适用于所有运行平台。

    • 它可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。

2.2 迭代与递归

在数据结构与算法中，重复执行某个任务是很常见的，其与算法的复杂度密切相关。而要重复执行某个任务，我们通常会选用两种基本的程序结构：迭代和递归。

2.2.1 迭代

「迭代 iteration」是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。

import collections

def for_loop(n: int) -> int:
    """for 循环"""
    res = 0
    # 循环求和 1, 2, ..., n-1, n
    for i in range(1, n + 1):
        res += i
    return res

def while_loop(n: int) -> int:
    """while 循环"""
    res = 0
    i = 1   # 初始化条件变量
    # 循环球和 1, 2, ..., n-1, n
    while i <= n:
        res += i
        i += 1  # 更新条件变量
    return res

在 while 循环中，由于初始化和更新条件变量的步骤是独立在循环结构之外的，因此它比 for 循环的自由度更高。例如在以下代码中，条件变量 \(i\) 每轮进行了两次更新，这种情况就不太方便用 for 循环实现。

def while_loop_li(n: int) -> int:
    """while 循环（两次更新）"""
    res = 0
    i = 1
    # 循环求和 1, 4, ...
    while i <= n:
        res += i
        i += 1
        i *= 2
    return res

总的来说，for 循环的代码更加紧凑，while 循环更加灵活，两者都可以实现迭代结构。选择使用哪一个应该根据特定问题的需求来决定。

def nested_for_loop(n: int) -> str:
    """双层 for 循环"""
    res = ""
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            res += f"({i}, {j}), "
    return res

2.2.2 递归

「递归 recursion」是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段。

  1. 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。

  2. 归：触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

而从实现的角度看，递归代码主要包含三个要素。

  1. 终止条件：用于决定什么时候由“递”转“归”。

  2. 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。

  3. 返回结果：对应“归”，将当前递归层级的结果返回至上一层。

def recur(n: int) -> int:
    """递归"""
    # 终止条件
    if n == 1:
        return 1
    # 递：递归调用
    res = recur(n - 1)
    # 归：返回结果
    return n + res

虽然从计算角度看，迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范式。

  • 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。

  • 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。

以上述的求和函数为例，设问题 \(f(n) = 1 + 2 + \dots + n\) 。

  • 迭代：在循环中模拟求和过程，从 \(1\) 遍历到 \(n\) ，每轮执行求和操作，即可求得 \(f(n)\) 。

  • 递归：将问题分解为子问题 \(f(n) = n + f(n-1)\) ，不断（递归地）分解下去，直至基本情况 \(f(0) = 0\) 时终止。

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。这将导致两方面的结果。

  • 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。

  • 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。

在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出报错。有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为「尾递归 tail recursion」。

  • 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。

  • 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无需继续执行其他操作，因此系统无需保存上一层函数的上下文。

def tail_recur(n, res):
    """尾递归"""
    # 终止条件
    if n == 0:
        return res
    # 尾递归调用
    return tail_recur(n - 1, res + n)

对比普通递归和尾递归，求和操作的执行点是不同的。

  • 普通递归：求和操作是在“归”的过程中执行的，每层返回后都要再执行一次求和操作。

  • 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。

def fib(n: int) -> int:
    """菲波那切数列"""
    # 终止条件 f(1) = 0, f(2) = 1
    if n == 1 or n == 2:
        return n - 1
    # 递归调用 f(n) = f(n-1) + f(n-2)
    res = fib(n - 1) + fib(n - 2)
    # 返回结果 f(n)
    return res

本质上看，递归体现“将问题分解为更小子问题”的思维范式，这种分治策略是至关重要的。

  • 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略都直接或间接地应用这种思维方式。

  • 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

那么，迭代和递归具有什么内在联系呢？以上述的递归函数为例，求和操作在递归的“归”阶段进行。这意味着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则是异曲同工的。

事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。

  1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、返回地址等数据。

  2. 归：当函数完成执行并返回时，对应的栈帧会从“调用栈”上被移除，恢复之前函数的执行环境。

因此，我们可以使用一个显式的栈来模拟调用栈的行为，从而将递归转化为迭代形式：

def for_loop_recur(n: int) -> int:
    """使用迭代模拟递归"""
    # 使用一个显式的栈来模拟系统调用栈
    stack = []
    res = 0
    # 递：递归调用
    for i in range(n, 0, -1):
        # 通过“入栈操作”模拟“递”
        stack.append(i)
    # 归：返回结果
    while stack:
        # 通过“出栈操作”模拟“归”
        res += stack.pop()
    # res = 1 + 2 + 3 + ... + n
    return res

2.3 时间复杂度

时间复杂度分析本质上是计算“操作数量函数 \(T(n)\)”的渐近上界，其具有明确的数学定义：

若存在正实数 \(c\) 和实数 \(n_0\) ，使得对于所有的 \(n > n_0\) ，均有 \(T(n) \leq c \cdot f(n)\) ，则可认为 \(f(n)\) 给出了 \(T(n)\) 的一个渐近上界，记为 \(T(n) = O(f(n))\) 。

计算渐近上界就是寻找一个函数 \(f(n)\) ，使得当 \(n\) 趋向于无穷大时，\(T(n)\) 和 \(f(n)\) 处于相同的增长级别，仅相差一个常数项 \(c\) 的倍数。

时间复杂度由多项式 \(T(n)\) 中最高阶的项来决定。这是因为在 \(n\) 趋于无穷大时，最高阶的项将发挥主导作用，其他项的影响都可以被忽略。

2.4 空间复杂度

「空间复杂度 space complexity」用于衡量算法占用内存空间随着数据量变大时的增长趋势。这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”。

算法在运行过程中使用的内存空间主要包括以下几种。

  • 输入空间：用于存储算法的输入数据。

  • 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。

    • 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。

    • 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。

    • 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

  • 输出空间：用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。在分析一段程序的空间复杂度时，我们通常统计暂存数据、栈帧空间和输出数据三部分。

与时间复杂度不同的是，我们通常只关注最差空间复杂度。这是因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留。

观察以下代码，最差空间复杂度中的“最差”有两层含义。

  1. 以最差输入数据为准：当 \(n < 10\) 时，空间复杂度为 \(O(1)\) ；但当 \(n > 10\) 时，初始化的数组 nums 占用 \(O(n)\) 空间；因此最差空间复杂度为 \(O(n)\) 。

  2. 以算法运行中的峰值内存为准：例如，程序在执行最后一行之前，占用 \(O(1)\) 空间；当初始化数组 nums 时，程序占用 \(O(n)\) 空间；因此最差空间复杂度为 \(O(n)\) 。

在递归函数中，需要注意统计栈帧空间。例如在以下代码中：

def function() -> int:
    # 执行某些操作
    return 0

def loop(n: int):
    """循环 O(1) """
    for _ in range(n):
        function()

def recur(n: int) -> int:
    """递归 O(n)"""
    if n == 1: return
    return recur(n - 1)

  • 函数 loop() 在循环中调用了 \(n\) 次 function() ，每轮中的 function() 都返回并释放了栈帧空间，因此空间复杂度仍为 \(O(1)\) 。

  • 递归函数 recur() 在运行过程中会同时存在 \(n\) 个未返回的 recur() ，从而占用 \(O(n)\) 的栈帧空间。

理想情况下，我们希望算法的时间复杂度和空间复杂度都能达到最优。然而在实际情况中，同时优化时间复杂度和空间复杂度通常是非常困难的。

降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为“以空间换时间”；反之，则称为“以时间换空间”。

选择哪种思路取决于我们更看重哪个方面。在大多数情况下，时间比空间更宝贵，因此“以空间换时间”通常是更常用的策略。当然，在数据量很大的情况下，控制空间复杂度也是非常重要的。

3 数据结构

3.1 数据结构分类

3.1.1 逻辑结构：线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中，数据按照顺序依次排列，体现了数据之间的线性关系；而在树中，数据从顶部向下按层次排列，表现出祖先与后代之间的派生关系；图则由节点和边构成，反映了复杂的网络关系。

Figure 3.1: 线性与非线性数据结构

  • 线性数据结构：数组、链表、栈、队列、哈希表。

  • 树形结构：树、堆、哈希表，元素之间是一对多的关系。

  • 网状结构：图，元素之间是多对多的关系。

3.1.2 物理结构：连续与离散

在算法运行过程中，相关数据都存储在内存中，系统通过内存地址来访问目标位置的数据。

内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。比如，算法所占用的内存峰值不应超过系统剩余空闲内存；如果缺少连续大块的内存空间，那么所选用的数据结构必须能够存储在离散的内存空间内。

物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（数组）和离散空间存储（链表）。物理结构从底层决定了数据的访问、更新、增删等操作方法，同时在时间效率和空间效率方面呈现出互补的特点。

Figure 3.2: 连续空间存储与离散空间存储

所有数据结构都是基于数组、链表或二者的组合实现的。例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

  • 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度 \(\geq 3\) 的数组）等。

  • 基于链表可实现：栈、队列、哈希表、树、堆、图等。

基于数组实现的数据结构也被称为“静态数据结构”，这意味着此类数据结构在初始化后长度不可变。相对应地，基于链表实现的数据结构被称为“动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中对其长度进行调整。

4 数组与链表

4.1 数组

4.1.1 数组常用操作

我们可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。在未指定初始值的情况下，大多数编程语言会将数组元素初始化为 \(0\) 。

# 初始化数组
arr: list[int] = [0] * 5
nums: list[int] = [1, 3, 2, 5, 4]
import random

def random_access(nums: list[int]) -> int:
    """随机访问元素"""
    random_index = random.randint(0, len(nums) - 1)
    random_num = nums[random_index]
    return random_num

def insert(nums: list[int], num: int, index: int):
    """在数组的索引 index 处插入元素 num"""
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    # 将 num 赋给 index 处元素
    nums[index] = num

数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。如果想要在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素的“丢失”。

同理，若想要删除索引 \(i\) 处的元素，则需要把索引 \(i\) 之后的元素都向前移动一位。

def remove(nums: list[int], index: int):
    """在数组的索引 index 处插入元素 num"""
    # 把索引 index 之后的所有元素向前移动一位
    for i in range(index, len(nums) - 1):
        nums[i] = nums[i + 1]

删除元素完成后，原先末尾的元素变得“无意义”了，所以我们无须特意去修改它。

总的来看，数组的插入与删除操作有以下缺点。

  • 时间复杂度高：数组的插入和删除的平均时间复杂度均为 \(O(n)\) ，其中 \(n\) 为数组长度。

  • 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。

  • 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做也会造成部分内存空间的浪费。

def traverse(num: list[int]):
    """遍历数组"""
    count = 0
    # 通过索引遍历数组
    for i in range(len(nums)):
        count += 1
    # 直接遍历数组
    for num in nums:
        count += 1
    # 同时遍历数据索引和元素
    for i, num in enumerate(nums):
        count += 1

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。

def find(nums: list[int], target: int) -> int:
    """在数组中查找指定元素"""
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。因此在大多数编程语言中，数组的长度是不可变的。

如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次拷贝到新数组。这是一个 \(O(n)\) 的操作，在数组很大的情况下是非常耗时的。

# 请注意，Python 的 list 是动态数组，可以直接扩展
# 为了方便学习，本函数将 list 看作是长度不可变的数组
def extend(nums: list[int], enlarge: int) -> list[int]:
    """扩展数组长度"""
    # 初始化一个长度后的数组
    res = 0 * (len(nums) + enlarge)
    # 将原数组中的所有元素复制到新数组
    for i in range(len(nums)):
        res[i] = nums[i]
    # 返回扩展后的新数组
    return res

4.1.2 数组优点与局限性

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。

  • 空间效率高: 数组为数据分配了连续的内存块，无须额外的结构开销。

  • 支持随机访问: 数组允许在 \(O(1)\) 时间内访问任何元素。

  • 缓存局部性: 当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑，其存在以下缺点。

  • 插入与删除效率低:当数组中元素较多时，插入与删除操作需要移动大量的元素。

  • 长度不可变: 数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。

  • 空间浪费: 如果数组分配的大小超过了实际所需，那么多余的空间就被浪费了。

4.1.3 数组典型应用

数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。

  • 随机访问：如果我们想要随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现样本的随机抽取。

  • 排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。

  • 查找表：当我们需要快速查找一个元素或者需要查找一个元素的对应关系时，可以使用数组作为查找表。假如我们想要实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。

  • 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。

  • 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

4.2 链表

class ListNode:
    """链表节点类"""
    def __init__(self, val: int):
        self.val: int = val                    # 节点值
        self.next: Optional[ListNode] = None   # 指向下一节点的引用

4.2.1 链表常用操作

## 初始化链表 1 -> 3 -> 2 -> 5 -> 4
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 构建引用指向
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

数组整体是一个变量，比如数组 nums 包含元素 nums[0] 和 nums[1] 等，而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以上代码中的链表可被记做链表 n0 。

def insert(n0: ListNode, P: ListNode):
    """在链表的节点 n0 之后插入节点 P"""
    n1 = n0.next
    P.next = n1
    n0.next = P

def remove(n0: ListNode):
    """删除链表的节点 n0 之后的首个节点"""
    if not n0.next:
        return
    # n0 -> P -n1
    P = n0.next
    n1 = P.next
    n0.next = n1

尽管在删除操作完成后节点 P 仍然指向 n1 ，但实际上遍历此链表已经无法访问到 P ，这意味着 P 已经不再属于该链表了。

def access(head: ListNode, index: int) -> ListNode | None:
    """访问链表中索引为 index 的节点"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

def find(head: ListNode, target: int) -> int:
    """在链表中查找值为 target 的首个节点"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

在链表访问节点的效率较低。如上节所述，我们可以在 \(O(1)\) 时间下访问数组中的任意元素。链表则不然，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 \(i\) 个节点需要循环 \(i - 1\) 轮，时间复杂度为 \(O(n)\) 。

4.2.2 数组 VS 链表

Table 4.1: 数组与链表的效率对比
数组 链表
存储方式 连续内存空间 离散内存空间
缓存局部性 友好 不友好
容量扩展 长度不可变 可灵活扩展
内存效率 占用内存少、浪费部分空间 占用内存多
访问元素 \(O(1)\) \(O(n)\)
添加元素 \(O(n)\) \(O(1)\)
删除元素 \(O(n)\) \(O(1)\)

4.2.3 常见链表类型

常见的链表类型包括三种：

  • 单向链表：即上述介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 \(\text{None}\) 。

  • 环形链表：如果我们令单向链表的尾节点指向头节点（即首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

  • 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

class ListNode:
    """双向链表节点类"""
    def __init__(self, val: int):
        self.val: int = val                   # 节点值
        self.next: Optional[ListNode] = None  # 指向后继节点的引用
        self.prev: Optional[ListNode] = None  # 指向前驱节点的引用

4.2.4 链表典型应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

  • 栈与队列：当插入和删除操作都在链表的一端进行时，它表现出先进后出的的特性，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性，对应队列。

  • 哈希表：链地址法是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。

  • 图：邻接表是表示图的一种常用方式，在其中，图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常被用于需要快速查找前一个和下一个元素的场景。

  • 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。

  • 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。

  • LRU 算法：在缓存淘汰算法（LRU）中，我们需要快速找到最近最少使用的数据，以及支持快速地添加和删除节点。这时候使用双向链表就非常合适。

循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度。

  • 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环的操作就可以通过循环链表来实现。

  • 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用到循环链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个循环链表，以便实现无缝播放。

4.3 列表

数组长度不可变导致实用性降低。在实际中，我们可能事先无法确定需要存储多少数据，这使数组长度的选择变得困难。若长度过小，需要在持续添加数据时频繁扩容数组；若长度过大，则会造成内存空间的浪费。

为解决此问题，出现了一种被称为「动态数组 dynamic array」的数据结构，即长度可变的数组，也常被称为「列表 list」。列表基于数组实现，继承了数组的优点，并且可以在程序运行过程中动态扩容。我们可以在列表中自由地添加元素，而无须担心超过容量限制。

4.3.1 列表常用操作

## 初始化列表
# 无初始值的空列表
list1: list = []
# 有初始值的列表
list: list = [1, 3, 2, 5, 4]

列表本质上是数组，因此可以在 \(O(1)\) 时间内访问和更新元素，效率很高。

# 访问元素
num: int = list[1]

# 更新元素
list[1] = 0

相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 \(O(1)\) ，但插入和删除元素的效率仍与数组相同，时间复杂度为 \(O(n)\) 。

# 清空列表
list.clear()

# 尾部添加元素
list.append(1)
list.append(3)
list.append(2)
list.append(5)
list.append(4)

# 中间插入元素
list.insert(3, 6)  # 在索引 3 处插入数字 6

# 删除元素
list.pop(3)        # 删除索引 3 处的元素

## 遍历列表
# 通过索引遍历列表
count = 0
for i in range(len(list)):
    count += 1

# 直接遍历列表元素
count = 0
for n in list:
    count += 1

# 拼接列表
list1 = [6, 8, 7, 10, 9]
list += list1  # 将列表 list1 拼接到 list 后

# 排序列表
list.sort()

4.3.2 列表实现

许多编程语言都提供内置的列表，例如 Java、C++、Python 等。它们的实现比较复杂，各个参数的设定也非常有考究，例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。

为了加深对列表工作原理的理解，我们尝试实现一个简易版列表，包括以下三个重点设计。

  • 初始容量：选取一个合理的数组初始容量。在本示例中，我们选择 10 作为初始容量。

  • 数量记录：声明一个变量 size，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。

  • 扩容机制：若插入元素时列表容量已满，则需要进行扩容。首先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。在本示例中，我们规定每次将数组扩容至之前的 2 倍。

Code 
class MyList:
    """列表类简易实现"""

    def __init__(self):
        """构造方法"""
        self.__capacity: int = 10  # 列表容量
        self.__nums: list[int] = [0] * self.__capacity  # 数组（存储列表元素）
        self.__size: int = 0  # 列表长度（即当前元素数量）
        self.__extend_ratio: int = 2  # 每次列表扩容的倍数

    def size(self) -> int:
        """获取列表长度（即当前元素数量）"""
        return self.__size

    def capacity(self) -> int:
        """获取列表容量"""
        return self.__capacity

    def get(self, index: int) -> int:
        """访问元素"""
        # 索引如果越界则抛出异常，下同
        if index < 0 or index >= self.__size:
            raise IndexError("索引越界")
        return self.__nums[index]

    def set(self, num: int, index: int):
        """更新元素"""
        if index < 0 or index >= self.__size:
            raise IndexError("索引越界")
        self.__nums[index] = num

    def extend_capacity(self):
        """列表扩容"""
        # 新建一个长度为原数组 _extend_ratio 倍的新数组，并将原数组拷贝到新数组
        self.__nums = self.__nums + [0] * self.capacity() * (self.__extend_ratio - 1)
        # 更新列表容量
        self.__capacity = len(self.__nums)

    def add(self, num: int):
        """尾部添加元素"""
        # 元素数量超出容量时，触发扩容机制
        if self.size() == self.capacity():
            self.extend_capacity()
        self.__nums[self.__size] = num
        self.__size += 1

    def insert(self, num: int, index: int):
        """中间插入元素"""
        if index < 0 or index >= self.__size:
            raise IndexError("索引越界")
        # 元素数量超出容量时，触发扩容机制
        if self.size() == self.capacity():
            self.extend_capacity()
        # 将索引 index 以及之后的元素都向后移动一位
        for j in range(self.__size - 1, index - 1, -1):
            self.__nums[j + 1] = self.__nums[j]
        self.__nums[index] = num
        # 更新元素数量
        self.__size += 1

    def remove(self, index: int) -> int:
        """删除元素"""
        if index < 0 or index >= self.__size:
            raise IndexError("索引越界")
        num = self.__nums[index]
        # 索引 index 之后的元素都向前移动一位
        for j in range(index, self.__size - 1):
            self.__nums[j] = self.__nums[j + 1]
        # 更新元素数量
        self.__size -= 1
        # 返回被删除的元素
        return num

    def to_array(self):
        """返回有效长度的列表"""
        return self.__nums[: self.__size]
# 初始化列表
my_list = MyList()

# 尾部添加元素
my_list.add(1)
my_list.add(3)
my_list.add(2)
my_list.add(5)
my_list.add(4)

print(
    f"列表 my_list = {my_list.to_array()}，容量 = {my_list.capacity()}，长度 = {my_list.size()}"
)

# 中间插入元素
my_list.insert(6, index=3)
print("在索引 3 处插入数字 6，得到 my_list =", my_list.to_array())

# 删除元素
my_list.remove(3)
print("删除索引 3 处的元素，得到 my_list =", my_list.to_array())

# 访问元素
num = my_list.get(1)
print("访问索引 1 处的元素，得到 num=", num)

# 更新元素
my_list.set(0, 1)
print("将索引 1 处的元素更新为 0，得到 my_list=", my_list.to_array())

# 测试扩容机制
for i in range(10):
    # 在 i = 5 时，列表长度将超出列表容量，触发扩容机制
    my_list.add(i)
print(
    f"扩容后的列表 {my_list.to_array()}，容量 = {my_list.capacity()}，长度 = {my_list.size()}"
)
列表 my_list = [1, 3, 2, 5, 4]，容量 = 10，长度 = 5
在索引 3 处插入数字 6，得到 my_list = [1, 3, 2, 6, 5, 4]
删除索引 3 处的元素，得到 my_list = [1, 3, 2, 5, 4]
访问索引 1 处的元素，得到 num= 3
将索引 1 处的元素更新为 0，得到 my_list= [1, 0, 2, 5, 4]
扩容后的列表 [1, 0, 2, 5, 4, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]，容量 = 20，长度 = 15
Note

与许多语言不同的是，在 Python 中数字也被包装为对象，列表中存储的不是数字本身，而是对数字的引用。因此，我们会发现两个数组中的相同数字拥有同一个 id ，并且这些数字的内存地址是无须连续的。

5 栈与队列

5.1 栈

「栈 stack」是一种遵循先入后出的逻辑的线性数据结构。

我们可以将栈类比为桌面上的一摞盘子，如果需要拿出底部的盘子，则需要先将上面的盘子依次取出。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈数据结构。

我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫做“入栈”，删除栈顶元素的操作叫做“出栈”。

5.1.1 栈常用操作

# 初始化栈
# Python 没有内置的栈类，可以把 List 当作栈来使用
stack: list = []

# 元素入栈
stack.append(1)
stack.append(3)
stack.append(2)
stack.append(5)
stack.append(4)

# 访问栈顶元素
peek: int = stack[-1]

# 元素出栈
pop: int = stack.pop()

# 获取栈的长度
size: int = len(stack)

# 判断是否为空
is_empty: bool = len(stack) == 0

5.1.2 栈的实现

为了深入了解栈的运行机制，我们来尝试自己实现一个栈类。

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以被视为一种受限制的数组或链表。换句话说，我们可以“屏蔽”数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。

5.1.2.1 基于链表的实现

使用链表来实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。而对于出栈操作，只需将头节点从链表中删除即可。

Code 
class LinkedListStack:
    """基于链表实现的栈"""

    def __init__(self):
        """构造方法"""
        self.__peek: ListNode | None = None
        self.__size: int = 0

    def size(self) -> int:
        """获取栈的长度"""
        return self.__size

    def is_empty(self) -> bool:
        """判断栈是否为空"""
        return not self.__peek

    def push(self, val: int):
        """入栈"""
        node = ListNode(val)
        node.next = self.__peek
        self.__peek = node
        self.__size += 1

    def pop(self) -> int:
        """出栈"""
        num: int = self.peek()
        self.__peek = self.__peek.next
        self.__size -= 1
        return num

    def peek(self) -> int:
        """访问栈顶元素"""
        # 判空处理
        if not self.__peek:
            return None
        return self.__peek.val

    def to_list(self) -> list:
        """转为列表用于打印"""
        arr = []
        node = self.__peek
        while node:
            arr.append(node.val)
            node = node.next
        arr.reverse()
        return arr
# 初始化栈
stack = LinkedListStack()

# 元素入栈
stack.push(1)
stack.push(3)
stack.push(2)
stack.push(5)
stack.push(4)
print("栈 stack =", stack.to_list())

# 访问栈顶元素
peek: int = stack.peek()
print("栈顶元素 peek =", peek)

# 元素出栈
pop: int = stack.pop()
print("出栈元素 pop =", pop)
print("出栈后 stack =", stack.to_list())

# 获取栈的长度
size: int = stack.size()
print("栈的长度 size =", size)

# 判断是否为空
is_empty: bool = stack.is_empty()
print("栈是否为空 =", is_empty)
栈 stack = [1, 3, 2, 5, 4]
栈顶元素 peek = 4
出栈元素 pop = 4
出栈后 stack = [1, 3, 2, 5]
栈的长度 size = 4
栈是否为空 = False

5.1.2.2 基于数组的实现

使用数组实现栈时，我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素，时间复杂度都为 \(O(1)\) 。由于入栈的元素可能会源源不断地增加，因此我们可以使用动态数组，这样就无须自行处理数组扩容问题。

Code 
class ArrayStack:
    """基于数组实现的栈"""

    def __init__(self):
        """构造方法"""
        self.__stack: list = []

    def size(self) -> int:
        """获取栈的长度"""
        return len(self.__stack)

    def is_empty(self) -> bool:
        """判断栈是否为空"""
        return self.__stack == []

    def push(self, item: int):
        """入栈"""
        self.__stack.append(item)

    def pop(self) -> int:
        """出栈"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.__stack.pop()

    def peek(self) -> int:
        """访问栈顶元素"""
        if self.is_empty():
            raise IndexError("栈为空")
        return self.__stack[-1]

    def to_list(self) -> list:
        """返回列表用于打印"""
        return self.__stack
# 初始化栈
stack = ArrayStack()

# 元素入栈
stack.push(1)
stack.push(3)
stack.push(2)
stack.push(5)
stack.push(4)
print("栈 stack =", stack.to_list())

# 访问栈顶元素
peek: int = stack.peek()
print("栈顶元素 =", peek)

# 元素出栈
pop: int = stack.pop()
print("出栈元素 pop =", pop)
print("出栈后 stack =", stack.to_list())

# 获取栈的长度
size: int = stack.size()
print("栈的长度 stack =", size)

# 判断是否为空
is_empty: bool = stack.is_empty()
print("栈是否为空 =", is_empty)
栈 stack = [1, 3, 2, 5, 4]
栈顶元素 = 4
出栈元素 pop = 4
出栈后 stack = [1, 3, 2, 5]
栈的长度 stack = 4
栈是否为空 = False

5.1.3 两种实现对比

5.1.3.1 支持操作

两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。

5.1.3.2 时间效率

在基于数组的实现中，入栈和出栈操作都是在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为 \(O(n)\) 。

在链表实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。

综上所述，当入栈与出栈操作的元素是基本数据类型时，例如 int 或 double ，我们可以得出以下结论。

  • 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。

  • 基于链表实现的栈可以提供更加稳定的效率表现。

5.1.3.3 空间效率

在初始化列表时，系统会为列表分配“初始容量”，该容量可能超过实际需求。并且，扩容机制通常是按照特定倍率（例如 2 倍）进行扩容，扩容后的容量也可能超出实际需求。因此，基于数组实现的栈可能造成一定的空间浪费。

然而，由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。

综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。

5.1.4 栈典型应用

  • 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会将上一个网页执行入栈，这样我们就可以通过后退操作回到上一页面。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。

  • 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会执行出栈操作。

5.2 队列

「队列 queue」是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列的尾部，而位于队列头部的人逐个离开。我们将队列的头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

5.2.1 队列常用操作

from collections import deque

# 初始化队列
# 在 Python 中，我们一般将双向队列类 deque 看作队列使用
# 虽然 queue.Queue() 是纯正的队列类，但不太好用，因此不建议
que: deque[int] = deque()

# 元素入队
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)
print("队列 que =", que)

# 访问队首元素
front: int = que[0]
print("队首元素 front =", front)

# 元素出队
pop: int = que.popleft()
print("出队元素 pop =", pop)
print("出队后 que =", que)

# 获取队列长度
size: int = len(que)
print("队列长度 size =", size)

# 判断 队列是否为空
is_empty: bool = len(que) == 0
print("队列是否为空 =", is_empty)
队列 que = deque([1, 3, 2, 5, 4])
队首元素 front = 1
出队元素 pop = 1
出队后 que = deque([3, 2, 5, 4])
队列长度 size = 4
队列是否为空 = False

5.2.2 队列实现

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素。因此，链表和数组都可以用来实现队列。

5.2.2.1 基于链表的实现

我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

Code 
class LinkedListQueue:
    """基于链表实现的队列"""

    def __init__(self):
        """构造方法"""
        self.__front: ListNode | None = None  # 头节点 front
        self.__rear: ListNode | None = None   # 尾节点 rear
        self.__size: int = 0

    def size(self) -> int:
        """获取队列长度"""
        return self.__size

    def is_empty(self) -> bool:
        """判断队列是否为空"""
        return not self.__front

    def push(self, num: int):
        """入队"""
        # 尾结点后添加 num
        node = ListNode(num)
        # 如果队列为空，则令头尾节点都指向该节点
        if self.__front is None:
            self.__front = node
            self.__rear = node
        # 如果队列不为空，则将该节点添加到尾结点后
        else:
            self.__rear.next = node
            self.__rear = node
        self.__size += 1

    def peek(self) -> int:
        """访问队首元素"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.__front.val

    def pop(self) -> int:
        """出队"""
        num = self.peek()
        # 删除头节点
        self.__front = self.__front.next
        self.__size -= 1
        return num

    def to_list(self) -> list:
        """转为列表用于打印"""
        queue = []
        temp = self.__front
        while temp:
            queue.append(temp.val)
            temp = temp.next
        return queue
# 初始化队列
queue = LinkedListQueue()

# 元素入队
queue.push(1)
queue.push(3)
queue.push(2)
queue.push(5)
queue.push(4)
print("队列 queue =", queue.to_list())

# 访问队首元素
peek: int = queue.peek()
print("队首元素 front =", peek)

# 元素出队
pop_front: int = queue.pop()
print("出队元素 pop =", pop_front)
print("出队后 queue =", queue.to_list())

# 获取队列的长度
size: int = queue.size()
print("队列长度 size =", size)

# 判断队列是否为空
is_empty: bool = queue.is_empty()
print("队列是否为空 =", is_empty)
队列 queue = [1, 3, 2, 5, 4]
队首元素 front = 1
出队元素 pop = 1
出队后 queue = [3, 2, 5, 4]
队列长度 size = 4
队列是否为空 = False

5.2.2.2 基于数组的实现

由于数组删除首元素的时间复杂度为 \(O(n)\) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。基于此设计，数组中包含元素的有效区间为 [front, rear - 1]。

  • 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。

  • 出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 \(O(1)\) 。

你可能会发现一个问题：在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现，代码如下所示。

Code 
class ArrayQueue:
    """基于环形数组实现的队列"""

    def __init__(self, size: int):
        """构造方法"""
        self.__nums: list = [0] * size  # 用于存储队列元素的数组
        self.__front: int = 0           # 队首指针，指向队首元素
        self.__size: int = 0            # 队列长度

    def capacity(self) -> int:
        """获取队列的容量"""
        return len(self.__nums)

    def size(self) -> int:
        """获取队列的长度"""
        return self.__size

    def is_empty(self) -> bool:
        """判断队列是否为空"""
        return self.__size == 0

    def push(self, num: int):
        """入队"""
        if self.__size == self.capacity():
            raise IndexError("队列已满")
        # 计算尾指针，指向对位索引 + 1
        # 通过取余操作，实现 rear 越过数组尾部后回到头部
        rear: int = (self.__front + self.__size) % self.capacity()
        # 将 num 添加至队尾
        self.__nums[rear] = num
        self.__size += 1

    def pop(self) -> int:
        """出队"""
        num: int = self.peek()
        # 队首指针向后移动一位，若越过尾部则返回到数组头部
        self.__front = (self.__front + 1) % self.capacity()
        self.__size -= 1
        return num

    def peek(self) -> int:
        """访问队首元素"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self.__nums[self.__front]

    def to_list(self) -> list:
        """返回列表用于打印"""
        res = [0] * self.size()
        j: int = self.__front
        for i in range(self.size()):
            res[i] = self.__nums[(j % self.capacity())]
            j += 1
        return res
# 初始化队列
queue = ArrayQueue(10)

# 元素入队
queue.push(1)
queue.push(3)
queue.push(2)
queue.push(5)
queue.push(4)
print("队列 queue =", queue.to_list())

# 访问队首元素
print("队首元素 peek =", queue.peek())

# 元素出队
print("出队元素 pop =", queue.pop())
print("出队后 queue =", queue.to_list())

# 获取队列长度
print("队列长度 size =", queue.size())

# 判断队列是否为空
print("队列是否为空 =", queue.is_empty())

# 测试循环数组
for i in range(10):
    queue.push(i)
    queue.pop()
    print("第", i, "轮入队 + 出队后 queue =", queue.to_list())
队列 queue = [1, 3, 2, 5, 4]
队首元素 peek = 1
出队元素 pop = 1
出队后 queue = [3, 2, 5, 4]
队列长度 size = 4
队列是否为空 = False
第 0 轮入队 + 出队后 queue = [2, 5, 4, 0]
第 1 轮入队 + 出队后 queue = [5, 4, 0, 1]
第 2 轮入队 + 出队后 queue = [4, 0, 1, 2]
第 3 轮入队 + 出队后 queue = [0, 1, 2, 3]
第 4 轮入队 + 出队后 queue = [1, 2, 3, 4]
第 5 轮入队 + 出队后 queue = [2, 3, 4, 5]
第 6 轮入队 + 出队后 queue = [3, 4, 5, 6]
第 7 轮入队 + 出队后 queue = [4, 5, 6, 7]
第 8 轮入队 + 出队后 queue = [5, 6, 7, 8]
第 9 轮入队 + 出队后 queue = [6, 7, 8, 9]

5.2.3 队列典型应用

  • 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序依次处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。

  • 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等。队列在这些场景中可以有效地维护处理顺序。

5.3 双向队列

在队列中，我们仅能在头部删除或在尾部添加元素。「双向队列 deque」提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

5.3.1 双向队列常用操作

我们可以直接使用编程语言中已实现的双向队列类。

# 初始化双向队列
deq = collections.deque()

# 元素入队
deq.append(2)      # 添加至队尾
deq.append(5)
deq.append(4)
deq.appendleft(3)  # 添加至队首
deq.appendleft(1)
print("双向队列 deque =", deq)

# 访问元素
print("队首元素 front =", deq[0])
print("队尾元素 read =", deq[-1])

# 元素出队
print("队首出队元素 pop_front =", deq.popleft())
print("队首出队后 deque =", deq)
print("队尾出队元素 pop_rear =", deq.pop())
print("队尾出队后 deque =", deq)

# 获取双向队列的长度
print("双向队列长度 size =", len(deq))

# 判断双向队列是否为空
print("双向队列是否为空 =", len(deq) == 0)
双向队列 deque = deque([1, 3, 2, 5, 4])
队首元素 front = 1
队尾元素 read = 4
队首出队元素 pop_front = 1
队首出队后 deque = deque([3, 2, 5, 4])
队尾出队元素 pop_rear = 4
队尾出队后 deque = deque([3, 2, 5])
双向队列长度 size = 3
双向队列是否为空 = False

5.3.2 双向队列实现 *

双向队列的实现与队列类似，可以选择链表或数组作为底层数据结构。

5.3.2.1 基于双向链表的实现

我们使用普通单向链表来实现队列，因为它可以方便地删除头节点（对应出队操作）和在尾节点后添加新节点（对应入队操作）。对于双向队列而言，头部和尾部都可以执行入队和出队操作。换句话说，双向队列需要实现另一个对称方向的操作。为此，我们采用“双向链表”作为双向队列的底层数据结构。

我们将双向链表的头节点和尾节点视为双向队列的队首和队尾，同时实现在两端添加和删除节点的功能。

Code 
class ListNode:
    """双向链表节点"""

    def __init__(self, val: int):
        """构造方法"""
        self.val: int = val
        self.next: ListNode | None = None  # 后继节点引用
        self.prev: ListNode | None = None  # 前驱节点引用


class LinkedListDeque:
    """基于双向链表实现的双向队列"""

    def __init__(self):
        """构造方法"""
        self.front: ListNode | None = None  # 头结点 front
        self.rear: ListNode | None = None   # 尾结点 rear
        self.__size: int = 0                # 双向队列的长度

    def size(self) -> int:
        """获取双向队列的长度"""
        return self.__size

    def is_empty(self) -> bool:
        """判断双向队列是否为空"""
        return self.size() == 0

    def push(self, num: int, is_front: bool):
        """入队操作"""
        node = ListNode(num)
        # 若链表为空，则令 front，rear 都指向 node
        if self.is_empty():
            self.front = self.rear = node
        # 队首入队操作
        elif is_front:
            # 将 node 添加至链表头部
            self.front.prev = node
            node.next = self.front
            self.front = node  # 更新头节点
        # 队尾入队操作
        else:
            # 将 node 添加至链表尾部
            self.rear.next = node
            node.prev = self.rear
            self.rear = node  # 更新尾节点
        self.__size += 1

    def push_first(self, num: int):
        """队首入队"""
        self.push(num, True)

    def push_last(self, num: int):
        """队尾入队"""
        self.push(num, False)

    def pop(self, is_front: bool) -> int:
        """出队操作"""
        # 若队列为空，直接返回 None
        if self.is_empty():
            return None
        # 队首出队操作
        if is_front:
            val: int = self.front.val  # 暂存头节点值
            # 删除头节点
            fnext: ListNode | None = self.front.next
            if fnext != None:
                fnext.prev = None
                self.front.next = None
            self.front = fnext  # 更新头节点
        # 队尾出队操作
        else:
            val: int = self.rear.val  # 暂存尾节点值
            # 删除尾节点
            rprev: ListNode | None = self.rear.prev
            if rprev != None:
                rprev.next = None
                self.rear.prev = None
            self.rear = rprev  # 更新尾节点
        self.__size -= 1  # 更新队列商都
        return val

    def pop_first(self) -> int:
        """队首出队"""
        return self.pop(True)

    def pop_last(self) -> int:
        """队尾出队"""
        return self.pop(False)

    def peek_first(self) -> int:
        """访问队首元素"""
        return None if self.is_empty() else self.front.val

    def peek_last(self) -> int:
        """访问队尾元素"""
        return None if self.is_empty() else self.rear.val

    def to_array(self) -> list:
        """返回数组用于打印"""
        node = self.front
        res = [0] * self.size()
        for i in range(self.size()):
            res[i] = node.val
            node = node.next
        return res
# 初始化双向队列
deque = LinkedListDeque()
deque.push_last(3)
deque.push_last(2)
deque.push_last(5)
print("双向队列 deque =", deque.to_array())

# 访问元素
peek_first: int = deque.peek_first()
print("队首元素 peek_first =", peek_first)
peek_last: int = deque.peek_last()
print("队尾元素 peek_last =", peek_last)

# 元素入队
deque.push_last(4)
print("元素 4 队尾入队后 deque =", deque.to_array())
deque.push_first(1)
print("元素 1 队首入队后 deque =", deque.to_array())

# 元素出队
pop_last: int = deque.pop_last()
print("队尾出队元素 =", pop_last, "，队尾出队后 deque =", deque.to_array())
pop_first: int = deque.pop_first()
print("队首出队元素 =", pop_first, "，队首出队后 deque =", deque.to_array())

# 获取双向队列的长度
size: int = deque.size()
print("双向队列长度 size =", size)

# 判断双向队列是否为空
is_empty: bool = deque.is_empty()
print("双向队列是否为空 =", is_empty)
双向队列 deque = [3, 2, 5]
队首元素 peek_first = 3
队尾元素 peek_last = 5
元素 4 队尾入队后 deque = [3, 2, 5, 4]
元素 1 队首入队后 deque = [1, 3, 2, 5, 4]
队尾出队元素 = 4 ，队尾出队后 deque = [1, 3, 2, 5]
队首出队元素 = 1 ，队首出队后 deque = [3, 2, 5]
双向队列长度 size = 3
双向队列是否为空 = False

5.3.2.2 基于数组的实现

与基于数组实现队列类似，我们也可以使用环形数组来实现双向队列。在队列的实现基础上，仅需增加“队首入队”和“队尾出队”的方法。

Code 
class ArrayDeque:
    """基于环形数组实现的双向队列"""

    def __init__(self, capacity: int):
        """构造方法"""
        self.__nums: list = [0] * capacity
        self.__front: int = 0           # 队首指针，指向队首元素
        self.__size: int = 0            # 队列长度

    def capacity(self) -> int:
        """获取双向队列的容量"""
        return len(self.__nums)

    def size(self) -> int:
        """获取双向队列的长度"""
        return self.__size

    def is_empty(self) -> bool:
        """判断双向队列是否为空"""
        return self.__size == 0

    def index(self, i: int) -> int:
        """计算环形数组索引"""
        # 通过取余操作实现数组收尾相连
        # 当 i 越过数组尾部后，回到头部
        # 当 i 越过数组头部后，回到尾部
        return (i + self.capacity()) % self.capacity()

    def push_first(self, num: int):
        """队首入队"""
        if self.__size == self.capacity():
            print("双向队列已满")
            return
        # 队首指针向左移动一位
        # 通过取余操作，实现 front 越过数组头部后回到尾部
        self.__front = self.index(self.__front - 1)
        # 将 num 添加至队首
        self.__nums[self.__front] = num
        self.__size += 1

    def push_last(self, num: int):
        """队尾入队"""
        if self.__size == self.capacity():
            print("双向队列已满")
            return
        # 计算尾指针，指向队尾索引 + 1
        rear = self.index(self.__front + self.__size)
        # 将 num 添加至队尾
        self.__nums[rear] = num
        self.__size += 1

    def peek_first(self) -> int:
        """访问队首元素"""
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self.__nums[self.__front]

    def peek_last(self) -> int:
        """访问队尾元素"""
        if self.is_empty():
            raise IndexError("双向队列为空")
        # 计算尾元素索引
        last = self.index(self.__front + self.__size - 1)
        return self.__nums[last]

    def pop_first(self) -> int:
        """队首出队"""
        num = self.peek_first()
        # 队首指针向后移动一位
        self.__front = self.index(self.__front + 1)
        self.__size -= 1
        return num

    def pop_last(self) -> int:
        """队尾出队"""
        num = self.peek_last()
        self.__size -= 1
        return num

    def to_array(self) -> list:
        """返回数组用于打印"""
        # 仅转换有效长度范围内的列表元素
        res = []
        for i in range(self.__size):
            res.append(self.__nums[self.index(self.__front + i)])
        return res
# 初始化双向队列
deque = ArrayDeque(10)
deque.push_last(3)
deque.push_last(2)
deque.push_last(5)
print("双向队列 deque =", deque.to_array())

# 访问元素
peek_first: int = deque.peek_first()
print("队首元素 peek_first =", peek_first)
peek_last: int = deque.peek_last()
print("队尾元素 peek_last =", peek_last)

# 元素入队
deque.push_last(4)
print("元素 4 队尾入队后 deque =", deque.to_array())
deque.push_first(1)
print("元素 1 队首入队后 deque =", deque.to_array())

# 元素出队
pop_last: int = deque.pop_last()
print("队尾出队元素 =", pop_last, "，队尾出队后 deque =", deque.to_array())
pop_first: int = deque.pop_first()
print("队首出队元素 =", pop_first, "，队首出队后 deque =", deque.to_array())

# 获取双向队列的长度
size: int = deque.size()
print("双向队列长度 size =", size)

# 判断双向队列是否为空
is_empty: bool = deque.is_empty()
print("双向队列是否为空 =", is_empty)
双向队列 deque = [3, 2, 5]
队首元素 peek_first = 3
队尾元素 peek_last = 5
元素 4 队尾入队后 deque = [3, 2, 5, 4]
元素 1 队首入队后 deque = [1, 3, 2, 5, 4]
队尾出队元素 = 4 ，队尾出队后 deque = [1, 3, 2, 5]
队首出队元素 = 1 ，队首出队后 deque = [3, 2, 5]
双向队列长度 size = 3
双向队列是否为空 = False

5.3.3 双向队列应用

双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。

我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 \(50\) 步）。当栈的长度超过 \(50\) 时，软件需要在栈底（即队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。

6 哈希表

6.1 哈希表

「哈希表 hash table」，又称「散列表」，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表输入一个键 key ，则可以在 \(O(1)\) 时间内获取对应的值 value 。

除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如 Table 6.1 所示。

Table 6.1: 元素查询效率对比
数组 链表 哈希表
查找元素 \(O(n)\) \(O(n)\) \(O(1)\)
添加元素 \(O(1)\) \(O(1)\) \(O(1)\)
删除元素 \(O(n)\) \(O(n)\) \(O(1)\)

6.1.1 哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等。

# 初始化哈希表
hmap: dict = {}

# 添加操作
# 在哈希表中添加键值对 (key, value)
hmap[12836] = "小哈"
hmap[15937] = "小啰"
hmap[16750] = "小算"
hmap[13276] = "小法"
hmap[10583] = "小鸭"

# 查询操作
# 向哈希表输入键 key ，得到值 value
name: str = hmap[15937]

# 删除操作
# 在哈希表中删除键值对 (key, value)
hmap.pop(10583)
'小鸭'

6.1.2 哈希表简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为「桶 bucket」，每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 来定位对应的桶呢？这是通过「哈希函数 hash function」实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步。

  1. 通过某种哈希算法 hash() 计算得到哈希值。

  2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

index = hash(key) % capacity

随后，我们就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100。Figure 6.1 以 key 学号和 value 姓名为例，展示了哈希函数的工作原理。

Figure 6.1: 哈希函数工作原理

以下代码实现了一个简单哈希表。其中，我们将 key 和 value 封装成一个类 Pair ，以表示键值对。

Code 
class Pair:
    """键值对"""

    def __init__(self, key: int, val: str):
        self.key = key
        self.val = val


class ArrayHashMap:
    """基于数组简易实现的哈希表"""

    def __init__(self):
        """构造方法"""
        # 初始化数组，包含 100 个桶
        self.buckets: list[Pair | None] = [None] * 100

    def hash_func(self, key: int) -> int:
        """哈希函数"""
        index = key % 100
        return index

    def get(self, key: int) -> int:
        """查询操作"""
        index: int = self.hash_func(key)
        pair: Pair = self.buckets[index]
        if pair is None:
            return None
        return pair.val

    def put(self, key: int, val: str):
        """添加操作"""
        pair = Pair(key, val)
        index: int = self.hash_func(key)
        self.buckets[index] = pair

    def remove(self, key: int):
        """删除操作"""
        index: int = self.hash_func(key)
        # 置为 None，代表删除
        self.buckets[index] = None

    def entry_set(self) -> list:
        """获取所有键值对"""
        result: list[Pair] = []
        for pair in self.buckets:
            if pair is not None:
                result.append(pair)
        return result

    def key_set(self) -> list:
        """获取所有键"""
        result: list = []
        for pair in self.buckets:
            if pair is not None:
                result.append(pair.key)
        return result

    def value_set(self) -> list:
        """获取所有值"""
        result: list = []
        for pair in self.buckets:
            if pair is not None:
                result.append(pair.val)
        return result

    def print(self):
        """打印哈希表"""
        for pair in self.buckets:
            if pair is not None:
                print(pair.key, "->", pair.val)
# 初始化哈希表
hmap = ArrayHashMap()

# 添加操作
# 在哈希表中添加键值对 (key, value)
hmap.put(12836, "小哈")
hmap.put(15937, "小啰")
hmap.put(16750, "小算")
hmap.put(13276, "小法")
hmap.put(10583, "小鸭")
print("\n添加完成后，哈希表为\nKey -> Value")
hmap.print()

添加完成后，哈希表为
Key -> Value
12836 -> 小哈
15937 -> 小啰
16750 -> 小算
13276 -> 小法
10583 -> 小鸭
# 查询操作
# 向哈希表输入键 key ，得到值 value
name = hmap.get(15937)
print("\n输入学号 15937 ，查询到姓名：" + name)

输入学号 15937 ，查询到姓名：小啰
# 删除操作
# 在哈希表中删除键值对 (key, value)
hmap.remove(10583)
print("\n删除 10583 后，哈希表为\nKey -> Value")
hmap.print()

删除 10583 后，哈希表为
Key -> Value
12836 -> 小哈
15937 -> 小啰
16750 -> 小算
13276 -> 小法
# 遍历哈希表
print("\n遍历键值对 Key->Value")
for pair in hmap.entry_set():
    print(pair.key, "->", pair.val)

遍历键值对 Key->Value
12836 -> 小哈
15937 -> 小啰
16750 -> 小算
13276 -> 小法
print("\n单独遍历键 Key")
for key in hmap.key_set():
    print(key)

单独遍历键 Key
12836
15937
16750
13276
print("\n单独遍历值 Value")
for val in hmap.value_set():
    print(val)

单独遍历值 Value
小哈
小啰
小算
小法

6.1.3 哈希冲突与扩容

本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：

12836 % 100 = 36
20336 % 100 = 36

两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为「哈希冲突 hash collision」。

容易想到，哈希表容量 \(n\) 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

如 Figure 6.2 所示，扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失。

Figure 6.2: 哈希表扩容

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时。并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步提高了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常被作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 \(0.75\) 时，系统会将哈希表容量扩展为原先的 \(2\) 倍。

6.2 哈希冲突

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为解决该问题，我们可以每当遇到哈希冲突时就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

  1. 改良哈希表数据结构，使得哈希表可以在存在哈希冲突时正常工作。

  2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

6.2.1 链式寻址

在原始哈希表中，每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。Figure 6.3 展示了一个链式地址哈希表的例子。

Figure 6.3: 链式地址哈希表

哈希表在链式地址下的操作方法发生了一些变化。

  • 查询元素：输入 key ，经过哈希函数得到数组索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对。

  • 添加元素：先通过哈希函数访问链表头节点，然后将节点（即键值对）添加到链表中。

  • 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点，并将其删除。

链式地址存在以下局限性。

  • 占用空间增大，链表包含节点指针，它相比数组更加耗费内存空间。

  • 查询效率降低，因为需要线性遍历链表来查找对应元素。

以下代码给出了链式地址哈希表的简单实现，需要注意两点。

  • 使用列表（动态数组）代替链表，从而简化代码。在这种设定下，哈希表（数组）包含多个桶，每个桶都是一个列表。

  • 以下实现包含哈希表扩容方法。当负载因子超过 \(0.75\) 时，我们将哈希表扩容至 \(2\) 倍。

Code 
class HashMapChaining:
    """链式地址哈希表"""

    def __init__(self):
        """构造方法"""
        self.size = 0  # 键值对数量
        self.capacity = 4  # 哈希表容量
        self.load_thres = 2 / 3  # 触发扩容的负载因子阈值
        self.extend_ratio = 2  # 扩容倍数
        self.buckets = [[] for _ in range(self.capacity)]  # 桶数组

    def hash_func(self, key: int) -> int:
        """哈希函数"""
        return key % self.capacity

    def load_factor(self) -> float:
        """负载因子"""
        return self.size / self.capacity

    def get(self, key: int) -> str:
        """查询操作"""
        index = self.hash_func(key)
        bucket = self.buckets[index]
        # 遍历桶，若找到 key 则返回对应 val
        for pair in bucket:
            if pair.key == key:
                return pair.val
        # 若未找到 key 则返回 None
        return None

    def put(self, key: int, val: str):
        """添加操作"""
        # 当负载因子超过阈值时，执行扩容
        if self.load_factor() > self.load_thres:
            self.extend()
        index = self.hash_func(key)
        bucket = self.buckets[index]
        # 遍历桶，若遇到 key，则更新对应 val 并返回
        for pair in bucket:
            if pair.key == key:
                pair.val = val
                return
        # 若无该 key，则将键值对添加至尾部
        pair = Pair(key, val)
        bucket.append(pair)
        self.size += 1

    def remove(self, key: int):
        """删除操作"""
        index = self.hash_func(key)
        bucket = self.buckets[index]
        # 遍历桶，从众删除键值对
        for pair in bucket:
            if pair.key == key:
                bucket.remove(pair)
                self.size -= 1
                break

    def extend(self):
        """扩容哈希表"""
        # 暂存原哈希表
        buckets = self.buckets
        # 初始化扩容后新的哈希表
        self.capacity *= self.extend_ratio
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        # 将键值对从原哈希表搬运至新哈希表
        for bucket in buckets:
            for pair in bucket:
                self.put(pair.key, pair.val)

    def print(self):
        """打印哈希表"""
        for bucket in self.buckets:
            res = []
            for pair in bucket:
                res.append(str(pair.key) + " -> " + pair.val)
            print(res)
# 测试代码
hashmap = HashMapChaining()

# 添加操作
# 在哈希表中添加键值对 (key, value)
hashmap.put(12836, "小哈")
hashmap.put(15937, "小啰")
hashmap.put(16750, "小算")
hashmap.put(13276, "小法")
hashmap.put(10583, "小鸭")
print("\n添加完成后，哈希表为\n[Key1 -> Value1, Key2 -> Value2, ...]")
hashmap.print()

添加完成后，哈希表为
[Key1 -> Value1, Key2 -> Value2, ...]
[]
['15937 -> 小啰']
[]
[]
['12836 -> 小哈', '13276 -> 小法']
[]
['16750 -> 小算']
['10583 -> 小鸭']
# 查询操作
# 向哈希表输入键 key ，得到值 value
name = hashmap.get(13276)
print("\n输入学号 13276 ，查询到姓名 " + name)

输入学号 13276 ，查询到姓名 小法
# 删除操作
# 在哈希表中删除键值对 (key, value)
hashmap.remove(12836)
print("\n删除 12836 后，哈希表为\n[Key1 -> Value1, Key2 -> Value2, ...]")
hashmap.print()

删除 12836 后，哈希表为
[Key1 -> Value1, Key2 -> Value2, ...]
[]
['15937 -> 小啰']
[]
[]
['13276 -> 小法']
[]
['16750 -> 小算']
['10583 -> 小鸭']

值得注意的是，当链表很长时，查询效率 \(O(n)\) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 \(O(\log n)\) 。

6.2.2 开放寻址

「开放寻址 open addressing」不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突，探测方式主要包括线性探测、平方探测、多次哈希等。

6.2.2.1 线性探测

线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

  • 插入元素：通过哈希函数计算数组索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 \(1\) ），直至找到空位，将元素插入其中。

  • 查找元素：若发现哈希冲突，则使用相同步长向后线性遍历，直到找到对应元素，返回 value 即可；如果遇到空位，说明目标键值对不在哈希表中，返回 \(\text{None}\) 。

然而，线性探测存在以下缺陷。

  • 不能直接删除元素。删除元素会在数组内产生一个空位，当查找该空位之后的元素时，该空位可能导致程序误判元素不存在。为此，通常需要借助一个标志位来标记已删除元素。

  • 容易产生聚集。数组内连续被占用位置越长，这些连续位置发生哈希冲突的可能性越大，进一步促使这一位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

以下代码实现了一个简单的开放寻址（线性探测）哈希表。

  • 我们使用一个固定的键值对实例 removed 来标记已删除元素。也就是说，当一个桶内的元素为 \(\text{None}\) 或 removed 时，说明这个桶是空的，可用于放置键值对。

  • 在线性探测时，我们从当前索引 index 向后遍历；而当越过数组尾部时，需要回到头部继续遍历。

Code 
class HashMapOpenAddressing:
    """开放寻址哈希表"""

    def __init__(self):
        """构造方法"""
        self.size = 0  # 键值对数量
        self.capacity = 4  # 哈希表容量
        self.load_thres = 2 / 3  # 触发扩容的负载因子阈值
        self.extend_ratio = 2  # 扩容倍数
        self.buckets: list[Pair | None] = [None] * self.capacity  # 桶数组
        self.removed = Pair(-1, "-1")  # 删除标记

    def hash_func(self, key: int) -> int:
        """哈希函数"""
        return key % self.capacity

    def load_factor(self) -> float:
        """负载因子"""
        return self.size / self.capacity

    def get(self, key: int) -> str:
        """查询操作"""
        index = self.hash_func(key)
        # 线性探测，从 index 开始向后遍历
        for i in range(self.capacity):
            # 计算桶索引，越过尾部返回头部
            j = (index + i) % self.capacity
            # 若遇到空桶，说明无此 key，则返回 None
            if self.buckets[j] is None:
                return None
            # 若遇到制定 key，则返回对应 val
            if self.buckets[j].key == key and self.buckets[j] != self.removed:
                return self.buckets[i].val

    def put(self, key: int, val: str):
        """添加操作"""
        # 当负载因子超过阈值，执行扩容
        if self.load_factor() > self.load_thres:
            self.extend()
        index = self.hash_func(key)
        # 线性探测，从 index 开始向后遍历
        for i in range(self.capacity):
            j = (index + i) % self.capacity
            # 若遇到空桶、或带有删除标记的桶，则将键值对放入该桶
            if self.buckets[j] in [None, self.removed]:
                self.buckets[j] = Pair(key, val)
                self.size += 1
                return
            # 若遇到指定 key，则更新对应 val
            if self.buckets[j].key == key:
                self.buckets[j].val = val
                return

    def remove(self, key: int):
        """删除操作"""
        index = self.hash_func(key)
        # 线性探测，从 index 开始向后遍历
        for i in range(self.capacity):
            # 计算桶索引，越过尾部返回头部
            j = (index + i) % self.capacity
            # 若遇到空桶，说明无此 key，则直接返回
            if self.buckets[j] is None:
                return
            # 若遇到指定 key，则标记删除并返回
            if self.buckets[j].key == key:
                self.buckets[j] = self.removed
                self.size -= 1
                return

    def extend(self):
        """扩容哈希表"""
        # 暂存原哈希表
        buckets_tmp = self.buckets
        # 初始化扩容后的新哈希表
        self.capacity *= self.extend_ratio
        self.buckets = [None] * self.capacity
        self.size = 0
        # 将键值对从原哈希表搬运至新哈希表
        for pair in buckets_tmp:
            if pair not in [None, self.removed]:
                self.put(pair.key, pair.val)

    def print(self):
        """打印哈希表"""
        for pair in self.buckets:
            if pair is not None:
                print(pair.key, "->", pair.val)
            else:
                print("None")
# 测试代码
hashmap = HashMapOpenAddressing()

# 添加操作
hashmap.put(12836, "小哈")
hashmap.put(15937, "小啰")
hashmap.put(16750, "小算")
hashmap.put(13276, "小法")
hashmap.put(10583, "小鸭")
print("\n添加完成后，哈希表为\nKey -> Value")
hashmap.print()

添加完成后，哈希表为
Key -> Value
None
15937 -> 小啰
None
None
12836 -> 小哈
13276 -> 小法
16750 -> 小算
10583 -> 小鸭
# 查询操作
print("\n输出学号 13276，查询到姓名", hashmap.get(13276))

输出学号 13276，查询到姓名 小啰
# 删除操作
hashmap.remove(16750)
print("\n删除 16750 后，哈希表为\nKey -> Value")
hashmap.print()

删除 16750 后，哈希表为
Key -> Value
None
15937 -> 小啰
None
None
12836 -> 小哈
13276 -> 小法
-1 -> -1
10583 -> 小鸭

6.2.2.2 多次哈希

顾名思义，多次哈希方法是使用多个哈希函数 \(f_1(x)\)、\(f_2(x)\)、\(f_3(x)\)、\(\dots\) 进行探测。

  • 插入元素：若哈希函数 \(f_1(x)\) 出现冲突，则尝试 \(f_2(x)\) ，以此类推，直到找到空位后插入元素。

  • 查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；或遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回 \(\text{None}\) 。

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会增加额外的计算量。

6.2.3 编程语言的选择

Java 采用链式地址。自 JDK 1.8 以来，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会被转换为红黑树以提升查找性能。

Python 采用开放寻址。字典 dict 使用伪随机数进行探测。

Golang 采用链式地址。Go 规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作，以确保性能。

6.3 哈希算法

无论是开放寻址还是链地址法，它们只能保证哈希表可以在发生冲突时正常工作，但无法减少哈希冲突的发生。如果哈希冲突过于频繁，哈希表的性能则会急剧劣化。对于链地址哈希表，理想情况下键值对平均分布在各个桶中，达到最佳查询效率；最差情况下所有键值对都被存储到同一个桶中，时间复杂度退化至 \(O(n)\) 。

键值对的分布情况由哈希函数决定。当哈希表容量 capacity 固定时，哈希算法 hash() 决定了输出值，进而决定了键值对在哈希表中的分布情况。这意味着，为了减小哈希冲突的发生概率，我们应当将注意力集中在哈希算法 hash() 的设计上。

6.4 哈希算法的目标

为了实现“既快又稳”的哈希表数据结构，哈希算法应包含以下特点。

  • 确定性：对于相同的输入，哈希算法应始终产生相同的输出。这样才能确保哈希表是可靠的。

  • 效率高：计算哈希值的过程应该足够快。计算开销越小，哈希表的实用性越高。

  • 均匀分布：哈希算法应使得键值对平均分布在哈希表中。分布越平均，哈希冲突的概率就越低。

实际上，哈希算法除了可以用于实现哈希表，还广泛应用于其他领域中。

  • 密码存储：为了保护用户密码的安全，系统通常不会直接存储用户的明文密码，而是存储密码的哈希值。当用户输入密码时，系统会对输入的密码计算哈希值，然后与存储的哈希值进行比较。如果两者匹配，那么密码就被视为正确。

  • 数据完整性检查：数据发送方可以计算数据的哈希值并将其一同发送；接收方可以重新计算接收到的数据的哈希值，并与接收到的哈希值进行比较。如果两者匹配，那么数据就被视为完整的。

对于密码学的相关应用，为了防止从哈希值推导出原始密码等逆向工程，哈希算法需要具备更高等级的安全特性。

  • 抗碰撞性：应当极其困难找到两个不同的输入，使得它们的哈希值相同。

  • 雪崩效应：输入的微小变化应当导致输出的显著且不可预测的变化。

请注意，“均匀分布”与“抗碰撞性”是两个独立的概念，满足均匀分布不一定满足抗碰撞性。例如，在随机输入 key 下，哈希函数 key % 100 可以产生均匀分布的输出。然而该哈希算法过于简单，所有后两位相等的 key 的输出都相同，因此我们可以很容易地从哈希值反推出可用的 key ，从而破解密码。

6.5 哈希算法的设计

哈希算法的设计是一个需要考虑许多因素的复杂问题。然而对于某些要求不高的场景，我们也能设计一些简单的哈希算法。

  • 加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值。

  • 乘法哈希：利用了乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中。

  • 异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。

  • 旋转哈希：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作。

Code 
def add_hash(key: str) -> int:
    """加法哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash += ord(c)
    return hash % modulus

def mul_hash(key: str) -> int:
    """乘法哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = 31 * hash + ord(c)
    return hash % modulus

def xor_hash(key: str) -> int:
    """异或哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash ^= ord(c)
    return hash % modulus

def rot_hash(key: str):
    """旋转哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = (hash << 4) ^ (hash >> 28) ^ ord(c)
    return hash % modulus
key = "Hello 算法"
print("加法哈希：" + str(add_hash(key)))
print("乘法哈希：" + str(mul_hash(key)))
print("异或哈希：" + str(xor_hash(key)))
print("旋转哈希：" + str(rot_hash(key)))
加法哈希：60032
乘法哈希：742108061
异或哈希：5920
旋转哈希：999636245

观察发现，每种哈希算法的最后一步都是对大质数 \(1000000007\) 取模，以确保哈希值在合适的范围内。当我们使用大质数作为模数时，可以最大化地保证哈希值的均匀分布。因为质数不会与其他数字存在公约数，可以减少因取模操作而产生的周期性模式，从而避免哈希冲突。

举个例子，假设我们选择合数 \(9\) 作为模数，它可以被 \(3\) 整除。那么所有可以被 \(3\) 整除的 key 都会被映射到 \(0\)、\(3\)、\(6\) 这三个哈希值。

6.5.1 数据结构的哈希值

哈希表的 key 可以是整数、小数或字符串等数据类型。编程语言通常会为这些数据类型提供内置的哈希算法，用于计算哈希表中的桶索引。以 Python 为例，我们可以调用 hash() 函数来计算各种数据类型的哈希值。

  • 整数和布尔量的哈希值就是其本身。

  • 浮点数和字符串的哈希值计算较为复杂，有兴趣的同学请自行学习。

  • 元组的哈希值是对其中每一个元素进行哈希，然后将这些哈希值组合起来，得到单一的哈希值。

  • 对象的哈希值基于其内存地址生成。通过重写对象的哈希方法，可实现基于内容生成哈希值。

print("整数 3 的哈希值为", hash(3))
print("布尔值 True 的哈希值为", hash(True))
print("小数 3.14159 的哈希值为", hash(3.14159))
print("字符串 ‘Hello 算法’ 的哈希值为", hash("Hello 算法"))
print("元组 (12836, '小哈') 的哈希值为", hash((12836, "小哈")))
print("节点对象 ListNode(0) 的哈希值为", hash(ListNode(0)))
整数 3 的哈希值为 3
布尔值 True 的哈希值为 1
小数 3.14159 的哈希值为 326484311674566659
字符串 ‘Hello 算法’ 的哈希值为 -7116537846116201184
元组 (12836, '小哈') 的哈希值为 4778916433467386242
节点对象 ListNode(0) 的哈希值为 148094634285

在许多编程语言中，只有不可变对象才可作为哈希表的 key 。假如我们将列表（动态数组）作为 key ，当列表的内容发生变化时，它的哈希值也随之改变，我们就无法在哈希表中查询到原先的 value 了。

虽然自定义对象（比如链表节点）的成员变量是可变的，但它是可哈希的。这是因为对象的哈希值通常是基于内存地址生成的，即使对象的内容发生了变化，但它的内存地址不变，哈希值仍然是不变的。

细心的你可能发现在不同控制台中运行程序时，输出的哈希值是不同的。这是因为 Python 解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（Salt）值。这种做法可以有效防止 HashDoS 攻击，提升哈希算法的安全性。

7 树

7.1 二叉树

「二叉树 binary tree」是一种非线性数据结构，代表着祖先与后代之间的派生关系，体现着“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含：值、左子节点引用、右子节点引用。

class TreeNode:
    """二叉树节点类"""

    def __init__(self, val: int):
        self.val: int = val                    # 节点值
        self.left: Optional[TreeNode] = None   # 左子节点引用
        self.right: Optional[TreeNode] = None  # 右子节点引用

每个节点都有两个引用（指针），分别指向「左子节点 left-child node」和「右子节点 right-child node」，该节点被称为这两个子节点的「父节点 parent node」。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树 left subtree」，同理可得「右子树 right subtree」。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

7.1.1 二叉树常见术语

  • 「根节点 root node」：位于二叉树顶层的节点，没有父节点。

  • 「叶节点 leaf node」：没有子节点的节点，其两个指针均指向 \(\text{None}\) 。

  • 「边 edge」：连接两个节点的线段，即节点引用（指针）。

  • 节点所在的「层 level」：从顶至底递增，根节点所在层为 1 。

  • 节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。

  • 二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量。

  • 节点的「深度 depth」：从根节点到该节点所经过的边的数量。

  • 节点的「高度 height」：从最远叶节点到该节点所经过的边的数量。

7.1.2 二叉树基本操作

from modules import *

## 初始化二叉树
# 初始化节点
n1 = TreeNode(1)
n2 = TreeNode(2)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5)
# 构建引用指向（指针）
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
print("\n初始化二叉树\n")
print_tree(n1)

初始化二叉树

    /——— 3
——— 1
   |    /——— 5
    \——— 2
        \——— 4
# 在 n1 -> n2 中间插入节点 P
P = TreeNode(0)
n1.left = P
P.left = n2
print("\n插入节点 P 后\n")
print_tree(n1)

插入节点 P 后

    /——— 3
——— 1
    \——— 0
       |    /——— 5
        \——— 2
            \——— 4
# 删除节点
n1.left = n2
print("\n删除节点 P 后\n")
print_tree(n1)

删除节点 P 后

    /——— 3
——— 1
   |    /——— 5
    \——— 2
        \——— 4

7.1.3 常见二叉树类型

  • 「完美二叉树 perfect binary tree」除了最底层外，其余所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 \(0\) ，其余所有节点的度都为 \(2\) ；若树高度为 \(h\) ，则节点总数为 \(2^{h+1} - 1\) ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。完美二叉树常被称为「满二叉树」。

  • 「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。

  • 「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。

  • 「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

7.1.4 二叉树的退化

当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

  • 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。

  • 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 \(O(n)\) 。

7.2 二叉树遍历

从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

7.2.1 层序遍历

「层序遍历 level-order traversal」从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。层序遍历本质上属于「广度优先遍历 breadth-first traversal」，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。

from collections import deque

def lever_order(root: TreeNode | None) -> list:
    """层序遍历"""
    # 初始化队列，加入根节点
    queue: deque[TreeNode] = deque()
    queue.append(root)
    # 初始化一个列表，用于保存遍历序列
    res = []
    while queue:
        node: TreeNode = queue.popleft()  # 队列出队
        res.append(node.val)  # 保存节点值
        if node.left is not None:
            queue.append(node.left)  # 左子节点入队
        if node.right is not None:
            queue.append(node.right)  # 右子节点入队
    return res
# 初始化二叉树
# 借助从数组直接生成二叉树的函数
root: TreeNode = list_to_tree(arr = [1, 2, 3, 4, 5, 6, 7])
print("\n初始化二叉树\n")
print_tree(root)

初始化二叉树

        /——— 7
    /——— 3
   |    \——— 6
——— 1
   |    /——— 5
    \——— 2
        \——— 4
# 层序遍历
res: list = lever_order(root)
print("层序遍历的节点打印序列 =", res)
层序遍历的节点打印序列 = [1, 2, 3, 4, 5, 6, 7]

  • 时间复杂度 \(O(n)\) ：所有节点被访问一次，使用 \(O(n)\) 时间，其中 \(n\) 为节点数量。

  • 空间复杂度 \(O(n)\) ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 \((n + 1) / 2\) 个节点，占用 \(O(n)\) 空间。

7.2.2 前序、中序、后序遍历

相应地，前序、中序和后序遍历都属于「深度优先遍历 depth-first traversal」，它体现了一种“先走到尽头，再回溯继续”的遍历方式。Figure 7.1 展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整个二叉树的外围“走”一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后序遍历。

Figure 7.1: 二叉搜索树的前、中、后序遍历

深度优先搜索通常基于递归实现：

def pre_order(root: TreeNode | None):
    """前序遍历"""
    if root is None:
        return
    # 访问优先级：根节点 -> 左子树 -> 右子树
    res.append(root.val)
    pre_order(root = root.left)
    pre_order(root = root.right)

def in_order(root: TreeNode | None):
    """中序遍历"""
    if root is None:
        return
    # 访问优先级：左子树 -> 根节点 -> 右子树
    in_order(root = root.left)
    res.append(root.val)
    in_order(root = root.right)

def post_order(root: TreeNode | None):
    """后序遍历"""
    if root is None:
        return
    # 访问优先级：左子树 -> 右子树 -> 根节点
    post_order(root = root.left)
    post_order(root = root.right)
    res.append(root.val)
# 前序遍历
res = []
pre_order(root)
print("\n前序遍历的节点打印序列 =", res)

# 中序遍历
res.clear()
in_order(root)
print("\n中序遍历的节点打印序列 =", res)

# 后序遍历
res.clear()
post_order(root)
print("\n后序遍历的节点打印序列 =", res)

前序遍历的节点打印序列 = [1, 2, 4, 5, 3, 6, 7]

中序遍历的节点打印序列 = [4, 2, 5, 1, 6, 3, 7]

后序遍历的节点打印序列 = [4, 5, 2, 6, 7, 3, 1]

  • 时间复杂度 \(O(n)\) ：所有节点被访问一次，使用 \(O(n)\) 时间。

  • 空间复杂度 \(O(n)\) ：在最差情况下，即树退化为链表时，递归深度达到 \(n\) ，系统占用 \(O(n)\) 栈帧空间。

7.3 二叉树数组表示

7.3.1 表示完美二叉树

给定一个完美二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。根据层序遍历的特性，我们可以推导出父节点索引与子节点索引之间的“映射公式”：若节点的索引为 \(i\) ，则该节点的左子节点索引为 \(2i + 1\) ，右子节点索引为 \(2i + 2\) 。下图展示了各个节点索引之间的映射关系。

Figure 7.2: 完美二叉树的数组表示

映射公式的角色相当于链表中的指针。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右）子节点。

7.3.2 表示任意二叉树

完美二叉树是一个特例，在二叉树的中间层通常存在许多 \(\text{None}\) 。由于层序遍历序列并不包含这些 \(\text{None}\) ，因此我们无法仅凭该序列来推测 \(\text{None}\) 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。

为了解决此问题，我们可以考虑在层序遍历序列中显式地写出所有 \(\text{None}\) 。如 Figure 7.3 所示，这样处理后，层序遍历序列就可以唯一表示二叉树了。

Figure 7.3: 任意类型二叉树的数组表示

值得说明的是，完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，\(\text{None}\) 只出现在最底层且靠右的位置，因此所有 \(\text{None}\) 一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时，可以省略存储所有 \(\text{None}\) ，非常方便。

以下代码实现了一个基于数组表示的二叉树，包括以下几种操作。

  • 给定某节点，获取它的值、左（右）子节点、父节点。

  • 获取前序遍历、中序遍历、后序遍历、层序遍历序列。

Code 
class ArraryBinaryTree:
    """数组表示下的二叉树类"""

    def __init__(self, arr):
        """构造方法"""
        self.__tree = arr

    def size(self):
        """节点数量"""
        return len(self.__tree)

    def val(self, i: int) -> int:
        """获取索引为 i 节点的值"""
        if i < 0 or i >= self.size():
            return None
        return self.__tree[i]

    def left(self, i: int) -> int:
        """获取索引为 i 节点的左子节点的索引"""
        return 2 * i + 1

    def right(self, i: int) -> int:
        """获取索引为 i 节点的右子节点的索引"""
        return 2 * i + 2

    def parent(self, i: int) -> int:
        """获取索引为 i 节点的父节点的索引"""
        return (i - 1) // 2

    def level_order(self) -> list:
        """层序遍历"""
        self.res = []
        # 直接遍历数组
        for i in range(self.size()):
            if self.val(i) is not None:
                self.res.append(self.val(i))
        return self.res

    def __dfs(self, i: int, order: str):
        """深度优先遍历"""
        if self.val(i) is None:
            return
        # 前序遍历
        if order == "pre":
            self.res.append(self.val(i))
        self.__dfs(self.left(i), order)
        # 中序遍历
        if order == "in":
            self.res.append(self.val(i))
        self.__dfs(self.right(i), order)
        # 后序遍历
        if order == "post":
            self.res.append(self.val(i))

    def pre_order(self) -> list:
        """前序遍历"""
        self.res = []
        self.__dfs(0, order = "pre")
        return self.res

    def in_order(self) -> list:
        """中序遍历"""
        self.res = []
        self.__dfs(0, order = "in")
        return self.res

    def post_order(self) -> list:
        """后序遍历"""
        self.res = []
        self.__dfs(0, order = "post")
        return self.res
# 初始化二叉树
# 这里借助了一个从数组直接生成二叉树的函数
arr = [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]
root = list_to_tree(arr)
print("\n初始化二叉树\n")
print(f"二叉树的数组表示：")
print(arr)

初始化二叉树

二叉树的数组表示：
[1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]
print(f"二叉树的链表表示：")
print_tree(root)
二叉树的链表表示：
            /——— 15
        /——— 7
    /——— 3
   |    \——— 6
   |        \——— 12
——— 1
    \——— 2
       |    /——— 9
        \——— 4
            \——— 8
# 数组表示
abt = ArraryBinaryTree(arr)
# 访问节点
i = 1
l, r, p = abt.left(i), abt.right(i), abt.parent(i)
print(f"\n当前节点的索引为 {i} ，值为 {abt.val(i)}")
print(f"其左子节点的索引为 {l} ，值为 {abt.val(l)}")
print(f"其右子节点的索引为 {r} ，值为 {abt.val(r)}")
print(f"其父节点的索引为 {p} ，值为 {abt.val(p)}")

当前节点的索引为 1 ，值为 2
其左子节点的索引为 3 ，值为 4
其右子节点的索引为 4 ，值为 None
其父节点的索引为 0 ，值为 1
# 遍历树
res = abt.level_order()
print("\n层序遍历为：", res)
res = abt.pre_order()
print("前序遍历为：", res)
res = abt.in_order()
print("中序遍历为：", res)
res = abt.post_order()
print("后序遍历为：", res)

层序遍历为： [1, 2, 3, 4, 6, 7, 8, 9, 12, 15]
前序遍历为： [1, 2, 4, 8, 9, 3, 6, 12, 7, 15]
中序遍历为： [8, 4, 9, 2, 1, 12, 6, 3, 7, 15]
后序遍历为： [8, 9, 4, 2, 12, 6, 15, 7, 3, 1]

7.3.3 优势与局限性

二叉树的数组表示主要有以下优点。

  • 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。

  • 不需要存储指针，比较节省空间。

  • 允许随机访问节点。

然而，数组表示也存在一些局限性。

  • 数组存储需要连续内存空间，因此不适合存储数据量过大的树。

  • 增删节点需要通过数组插入与删除操作实现，效率较低。

  • 当二叉树中存在大量 \(\text{None}\) 时，数组中包含的节点数据比重较低，空间利用率较低。

7.4 二叉搜索树

7.4.1 二叉搜索树的操作

「二叉搜索树 binary search tree」满足以下条件。

  1. 对于根节点，左子树中所有节点的值 \(<\) 根节点的值 \(<\) 右子树中所有节点的值。

  2. 任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。

在代码实现中，需要注意以下几点：

  • 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。

  • 我们需要根据目标节点的子节点数量，共分为 0、1 和 2 这三种情况，执行对应的删除节点操作。

    • 当待删除节点的度为 \(0\) 时，表示该节点是叶节点，可以直接删除。

    • 当待删除节点的度为 \(1\) 时，将待删除节点替换为其子节点即可。

    • 当待删除节点的度为 \(2\) 时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左 \(<\) 根 \(<\) 右”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。

二叉树的中序遍历遵循“左 \(\rightarrow\) 根 \(\rightarrow\) 右”的遍历顺序，而二叉搜索树满足“左子节点 \(<\) 根节点 \(<\) 右子节点”的大小关系。

这意味着在二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要性质：二叉搜索树的中序遍历序列是升序的。

利用中序遍历升序的性质，我们在二叉搜索树中获取有序数据仅需 \(O(n)\) 时间，无须进行额外的排序操作，非常高效。

Code 
class BinarySearchTree:
    """二叉搜索树"""

    def __init__(self):
        """构造方法"""
        # 初始化空树
        self.__root = None

    def get_root(self) -> TreeNode | None:
        """获取二叉树根节点"""
        return self.__root

    def search(self, num: int) -> TreeNode | None:
        """查找节点"""
        cur = self.__root
        # 循环查找，越过叶节点后跳出
        while cur is not None:
            # 目标节点在 cur 的右子树中
            if cur.val < num:
                cur = cur.right
            # 目标节点在 cur 的左子树中
            elif cur.val > num:
                cur = cur.left
            # 找到目标节点，跳出循环
            else:
                break
        return cur

    def insert(self, num: int):
        """插入节点"""
        # 若树为空，则初始化根节点
        if self.__root is None:
            self.__root = TreeNode(num)
            return
        # 循环查找，越过叶节点后跳出
        cur, pre = self.__root, None
        while cur is not None:
            # 找到重复节点，直接返回
            if cur.val == num:
                return
            pre = cur
            # 插入位置在 cur 的右子树中
            if cur.val < num:
                cur = cur.right
            # 插入位置在 cur 的左子树中
            else:
                cur = cur.left
        # 插入节点
        node = TreeNode(num)
        if pre.val < num:
            pre.right = node
        else:
            pre.left = node

    def remove(self, num: int):
        """删除节点"""
        # 若树为空，直接提前返回
        if self.__root is None:
            return
        # 循环查找，越过叶节点后跳出
        cur, pre = self.__root, None
        while cur is not None:
            # 找到待删除节点，跳出循环
            if cur.val == num:
                break
            pre = cur
            # 待删除节点在 cur 的右子树中
            if cur.val < num:
                cur = cur.right
            # 待删除节点在 cur 的左子树中
            else:
                cur = cur.left
        # 若无待删除节点，则直接返回
        if cur is None:
            return

        # 子节点数量 = 0 or 1
        if cur.left is None or cur.right is None:
            # 当子节点数量 = 0 / 1 时，child = null / 该节点
            child = cur.left or cur.right
            # 删除节点 cur
            if cur != self.__root:
                if pre.left == cur:
                    pre.left = child
                else:
                    pre.right = child
            else:
                # 若删除节点为根节点，则重新指定根节点
                self.__root = child
        # 子节点数量为 2
        else:
            # 获取中序遍历中 cur 的下一个节点
            tmp: TreeNode = cur.right
            while tmp.left is not None:
                tmp = tmp.left
            # 递归删除节点 tmp
            self.remove(tmp.val)
            # 用 tmp 覆盖 cur
            cur.val = tmp.val
# 初始化二叉搜索树
bst = BinarySearchTree()
nums = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
# 请注意，不同的插入顺序会生成不同的二叉树，该序列可以生成一个完美二叉树
for num in nums:
    bst.insert(num)
print("\n初始化的二叉树为\n")
print_tree(bst.get_root())

初始化的二叉树为

            /——— 15
        /——— 14
       |    \——— 13
    /——— 12
   |   |    /——— 11
   |    \——— 10
   |        \——— 9
——— 8
   |        /——— 7
   |    /——— 6
   |   |    \——— 5
    \——— 4
       |    /——— 3
        \——— 2
            \——— 1
# 查找节点
node = bst.search(7)
print("\n查找到的节点对象为: {}，节点值 = {}".format(node, node.val))

查找到的节点对象为: <modules.tree_node.TreeNode object at 0x00000227B21ABB90>，节点值 = 7
# 插入节点
bst.insert(16)
print("\n插入节点 16 后，二叉树为\n")
print_tree(bst.get_root())

插入节点 16 后，二叉树为

                /——— 16
            /——— 15
        /——— 14
       |    \——— 13
    /——— 12
   |   |    /——— 11
   |    \——— 10
   |        \——— 9
——— 8
   |        /——— 7
   |    /——— 6
   |   |    \——— 5
    \——— 4
       |    /——— 3
        \——— 2
            \——— 1
# 删除节点
bst.remove(1)
print("\n删除节点 1 后，二叉树为\n")
print_tree(bst.get_root())

删除节点 1 后，二叉树为

                /——— 16
            /——— 15
        /——— 14
       |    \——— 13
    /——— 12
   |   |    /——— 11
   |    \——— 10
   |        \——— 9
——— 8
   |        /——— 7
   |    /——— 6
   |   |    \——— 5
    \——— 4
       |    /——— 3
        \——— 2
bst.remove(2)
print("\n删除节点 2 后，二叉树为\n")
print_tree(bst.get_root())

删除节点 2 后，二叉树为

                /——— 16
            /——— 15
        /——— 14
       |    \——— 13
    /——— 12
   |   |    /——— 11
   |    \——— 10
   |        \——— 9
——— 8
   |        /——— 7
   |    /——— 6
   |   |    \——— 5
    \——— 4
        \——— 3
bst.remove(4)
print("\n删除节点 4 后，二叉树为\n")
print_tree(bst.get_root())

删除节点 4 后，二叉树为

                /——— 16
            /——— 15
        /——— 14
       |    \——— 13
    /——— 12
   |   |    /——— 11
   |    \——— 10
   |        \——— 9
——— 8
   |        /——— 7
   |    /——— 6
    \——— 5
        \——— 3

7.4.2 二叉搜索树常见应用

  • 用作系统中的多级索引，实现高效的查找、插入、删除操作。

  • 作为某些搜索算法的底层数据结构。

  • 用于存储数据流，以保持其有序状态。

To be continued
Back to top