数据结构与算法1-7

数据结构与算法

1.算法

1.算法定义

• 算法 （algorithm）是在有限时间内解决特定问题的一组指令或操作步骤

2.特性

• 问题是明确的，包含清晰的输入和输出定义。
• 具有可行性，能够在有限步骤、时间和内存空间下完成。
• 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。

3.与数据结构的关系

• 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
• 算法为数据结构注入生命力。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
• 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。

# 常将数据结构与算法简称为算法

2.复杂度分析

1.算法效率评估

1.算法设计目标

1.找到问题解法

• 算法需要在规定的输入范围内可靠地求得问题的正确解。

2.寻求最优解法

• 同一个问题可能存在多种解法，找到尽可能高效的算法

2.算法评估指标

1.时间效率

• 算法运行时间的长短。

2.空间效率

• 算法占用内存空间的大小

3.效率评估方法

1.实际测试

• 在同一台计算机上运行两种不同的算法，监控它们运行的时间和占用的空间

# 但是存在两种问题：

1.测试环境：在不同的硬件上的测试可能会有不同的结果

2.耗费资源：有时候输入数据量的变化也可能会导致效率不同，而要测试所有规模的数据量会浪费大量计算资源

2.理论估计

• 由于实际测试具有较大的局限性，因此可以考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析 （asymptotic complexity analysis），简称复杂度分析 。

• 它描述了随着输入数据大小的增加，算法执行所需时间（时间复杂度（time complexity））和空间（空间复杂度（space complexity））的增长趋势

2.迭代与递归

1.迭代

• 迭代 （iteration）是一种重复执行某个任务的控制结构。自下而上 解决问题

1.for循环

• 适用于预先知道迭代次数时

2.while循环

• 相比于for循环可以自由设计条件变量和更新步骤

# for循环就是加了语法糖的while循环

# 语法糖：更加便捷的写法

3.嵌套循环

• 在一个循环结构内嵌套另一个循环结构

2.递归

• 递归（recursion）是一种算法策略，通过函数调用自身来解决问题。自上而下 解决问题，将问题分解为子问题，与原问题具有相同的形式，再将子问题分解为更小的子问题。它主要包含两个阶段：
  • 递 ：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到终止条件 。
  • 归 ：触发终止条件 后，程序从最深层的递归函数开始逐层返回 ，汇聚每一层的结果

# 例如：

int recur(int n) 
{
	// 终止条件
	if (n == 1)
		return 1;
	// 递：递归调用
	int res = recur(n - 1);
	// 归：返回结果
	return n + res;
}

用于求累加的函数

# 例如求1到5的累加，先调用recur（5），由于n=5，不等于1，所以先暂停计算recur（5）继续调用这个函数recur（4），一直到recur（1）（在recur（1）之前都是递 的过程），然后满足终止条件 直接返回1，res=1再返回n+res的值=2，计算recur（2）的值返回3，再依次返回到recur（5）得出最终结果

1.调用栈

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

  • 上下文数据都存储在栈帧空间 的内存区域中，因此递归比迭代更耗费内存空间

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

• 在上述的代码中，在到达recur（1）之前（触发终止条件之前 ），前面有5-2共4个未返回的递归函数 ，此时的递归深度为4 ，通常编程语言允许的递归深度是有限的，过深的递归可能会导致栈溢出错误

2.尾递归

int tailRecur(int n, int res) 
{
	if (n == 0) // 终止条件
    {
		return res; // 尾递归调用
    }
	return tailRecur(n - 1, res + n);
}

# 用这段代码求累加，1-5的值，n=5，这里的res设置为0，tailRecur（5，0）未达到终止条件，就会返回tailRecur（4，0+5），依次返回tailRecur（3，（0+5）+4），tailRecur（2，（（0+5）+4）+3），tailRecur（1，（（（0+5）+4）+3）+2），tailRecur（0，（（（0+5）+4）+3）+2）+1）至此到达终止条件，直接返回res的值也就是（（（0+5）+4）+3）+2）+1

• 函数在返回前的最后一步才进行递归调用 ，部分 编译器或解释器会将函数优化，使其在空间效率上与迭代相当，这种情况被称为尾递归 （tail recursion）

# 例如python中就不支持尾递归优化，仍然会有栈溢出的问题

• 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
  • 求和操作是在归 的过程中执行的，每次返回一层都进行一次求和
• 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。
  • 求和操作是在递 的过程中执行的，归 则直接返回结果

3.递归树

int fib(int n)
{
    if (n == 1 || n == 2)// 终止条件 f(1) = 0, f(2) = 1
    {
        return n - 1;
	}
   
    int res = fib(n - 1) + fib(n - 2); // 递归调用 f(n) = f(n-1) + f(n-2)
    
    return res; // 返回结果 f(n)
}

# 这是一个求斐波拉契数列的递归函数，斐波拉契数列的前两个数是0，1，从第三个数开始是前面两个数的和，所以这里将终止条件设置为1，2，然后返回0，1。例如计算其第5项为几，则fib（5），未到达终止条件就会返回fib（4）和fib（3），分别返回（fib（3），fib（2））和（fib（2），fib（1）），此时fib（2）和fib（1）都已经到达终止条件，返回0，1，而fib（3）继续分解为fib（2），fib（1）再返回值0，1

# 每一次调用都生成了两个调用分支，这样就形成了一个类似于树状图的结构

        fib(5)
        /     \
   fib(4)     fib(3)
   /    \      /    \
fib(3) fib(2) fib(2) fib(1)
/    \
fib(2) fib(1)

# 称其为层数为4的递归树 （recursion tree）

• 从本质上看，递归体现了“将问题分解为更小子问题”的思维范式，这种分治策略至关重要
  • 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用了这种思维方式。
  • 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

3.对比

	迭代	递归
实现方式	循环结构	函数调用自身
时间效率	效率通常较高，无函数调用开销	每次函数调用都会产生开销
内存使用	通常使用固定大小的内存空间	累积函数调用可能使用大量的栈帧空间
适用问题	适用于简单循环任务，代码直观、可读性好	适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、清晰

4.联系

• 从栈 的角度来分析

  • 递：当函数被调用时 ，系统会在调用栈 上为该函数分配新的栈帧 ，用于存储函数的局部变量、参数、返回地址等数据
  • 归：当函数完成执行并返回时 ，对应的栈帧会被从调用栈 上移除 ，恢复之前函数的执行环境。

• 尽管迭代和递归在很多情况下可以互相转化，但不一定值得这样做，有以下两点原因。

  • 转化后的代码可能更加难以理解，可读性更差。
  • 对于某些复杂问题，模拟系统调用栈的行为可能非常困难

# 在实际编程中需要权衡两者

3.时间复杂度

• 通常不会去具体考虑硬件配置，环境等因素，然后将每一步操作的耗时相加，这种做法不合理也不现实

1.统计时间增长趋势

• 统计算法运行时间随着数据量变大时的增长趋势

// 算法 A 的时间复杂度：常数阶，与n的大小无关
void algorithm_A(int n) 
{
	printf("%d", 0);
}
// 算法 B 的时间复杂度：线性阶，运行时间随n的增大而增大
void algorithm_B(int n) 
{
	for (int i = 0; i < n; i++)
    {
		printf("%d", 0);
	}
}
// 算法 C 的时间复杂度：常数阶，与n的大小无关
void algorithm_C(int n) 
{
	for (int i = 0; i < 1000000; i++) 
	{
		printf("%d", 0);
	}
}

• 这种方法将统计时间 转化为统计操作数量

• 但也存在局限性 ：A和C因为都是常数阶，所以复杂度相同，但是运行时间肯定不相同。同时B是线性阶但是其运行时间随n的大小而变化，较小时B算法就会优于C算法

2.函数渐近上界

void algorithm(int n) 
{
	int a = 1; // +1
	a = a + 1; // +1
	a = a * 2; // +1
	// 循环 n 次
	for (int i = 0; i < n; i++) { // +1（每轮都执行 i ++）
		printf("%d", 0); // +1
	}
}

• 例如上述代码，先进行三次赋值运算，再进行一次循环，这个循环有两个步骤

• 因此将上述代码的操作数量记为一个与输入数据大小n相关的函数T（n）：T（n）=3+2n

• T（n）函数是线性函数，复杂度是线性阶

• 将线性阶的时间复杂度记为𝑂(𝑛) ，这个数学符号称为大 𝑂 记号 （big‑𝑂 notation），表示函数 𝑇(𝑛) 的渐近上界 （asymptotic upper bound）：𝑛 > 𝑛0时 ，均有 𝑇(𝑛) ≤ 𝑐 ⋅ 𝑓(𝑛)，记为 𝑇(𝑛) = 𝑂(𝑓(𝑛))

• 时间复杂度分析本质 上是计算“操作数量 𝑇(𝑛)”的渐近上界

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

3.推算方法

1.统计操作数量

1.忽略 𝑇(𝑛) 中的常数项

• 与n无关，对时间复杂度不产生影响

2.省略所有系数

• 系数对时间复杂度没有影响

3.循环嵌套时使用乘法

• 总操作数量等于外层循环和内层循环操作数量之积，每一层循环依然遵循前两点

void algorithm(int n) 
{
	int a = 1; // +0（技巧 1）
	a = a + n; // +0（技巧 1）
	// +n（技巧 2）
	for (int i = 0; i < 5 * n + 1; i++) {
		printf("%d", 0)
	}
	// +n*n（技巧 3）
	for (int i = 0; i < 2 * n; i++) {
		for (int j = 0; j < n + 1; j++) {
			printf("%d", 0);
		}
	}
}

• T（n）=n^2+n

2.判断渐近上界

• 时间复杂度由𝑇(𝑛) 中最高阶的项来决定 。这是因为在 𝑛 趋于无穷大时，最高阶的项将发挥主导 作用，其他

项的影响都可以忽略

4.常见类型

• 𝑂(1) < 𝑂(log 𝑛) < 𝑂(𝑛) < 𝑂(𝑛 log 𝑛) < 𝑂(𝑛2 ) < 𝑂(2𝑛) < 𝑂(𝑛!）
• 常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶

1.常数阶 𝑂(1）

• 常数阶的操作数量与输入数据大小 𝑛 无关，即不随着 𝑛 的变化而变化

2.线性阶𝑂(n）

• 线性阶的操作数量相对于输入数据大小 𝑛 以线性级别增长。线性阶通常出现在单层循环中

# 例如遍历数组和链表

• 输入数据大小𝑛需根据输入数据的类型来具体确定，可以是数据大小，也可以是数组长度

3.平方阶𝑂(n^2）

• 平方阶的操作数量相对于输入数据大小 𝑛 以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层

  循环的时间复杂度都为 𝑂(𝑛) ，因此总体的时间复杂度为 𝑂(𝑛^2 )

4.指数阶𝑂(2^n）

• 在实际算法中，指数阶常出现于递归函数 中

• 例如上述的递归数中的斐波拉契数列，每一次调用都生成了两个调用分支

# 对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心算法等来解决。

5.对数阶𝑂(log n）

• 对数阶反映了每轮缩减到一半 的情况。
• 时间复杂度为 𝑂(log2 𝑛) ，简记为 𝑂(log 𝑛)
• 与指数阶类似，对数阶也常出现于递归函数 中。
• 体现了一分为多 和化繁为简 的算法思想。

# 准确来说，一分为 𝑚 对应的时间复杂度是 𝑂(log𝑚 𝑛) 。

𝑂(log𝑚 𝑛) = 𝑂(log𝑘 𝑛/ log𝑘 𝑚) = 𝑂(log𝑘 𝑛)

底数 𝑚 可以在不影响复杂度的前提下转换。因此我们通常会省略底数 𝑚 ，将对数阶直接记为 𝑂(log 𝑛) 。

6.线性对数阶𝑂(n*log n）

• 线性对数阶常出现于嵌套循环 中，两层循环的时间复杂度分别为𝑂(log 𝑛) 和𝑂(𝑛) 。

int linearLogRecur(int n) 
{
	if (n <= 1)
		return 1;
	int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
	for (int i = 0; i < n; i++) {
		count++;
	}
	return count;
}

• 主流排序算法的时间复杂度通常为 𝑂(𝑛*log 𝑛) ，例如快速排序、归并排序、堆排序等

7.阶乘阶𝑂(n！）

• 乘阶对应数学上的全排列 问题。给定 𝑛 个互不重复的元素，求其所有可能的排列方案，方案数量为:
• n! = 𝑛 × (𝑛 − 1) × (𝑛 − 2) × ⋯ × 2 × 1
• 阶乘通常使用递归 实现

           *
        /     \
       *       *
   /    \        \
  *      *        *
/    \     \        \
*      *     *        *
|  \     \     \        \
*    *     *     *        *

# 形成这样的树状图，每次分裂后其中一个不再分裂

5.最差，最佳，平均时间复杂度

• 算法的时间效率往往不是固定的，而是与输入数据的分布有关 。

# 例如有两个数组，现在要返回数字1的索引

a1=[5,4,3,2,1]，需要遍历整个数组，达到最差复杂度𝑂(𝑛) ，其对应函数的渐近上界。

a2=[1,2,3,4,5]，不需要继续遍历后面的数字，达到最佳时间复杂度Ω(1) ，其对应函数的渐近下界。

• 实际中很少使用最佳时间复杂度，因为通常只有在很小概率下才能达到，可能会带来一定的误导性。而最差时间复杂度更为实用，因为它给出了一个效率安全值，让我们可以放心地使用算法。

• 平均时间复杂度可以体现算法在随机输入数据下的运行效率，用 Θ（theta） 记号来表示（有时候也会用𝑂(𝑛)表示）

# 部分算法较为简单可以直接计算平均时间复杂度，但是对于较为复杂的算法则直接用最差时间复杂度来作为评判标准

4.空间复杂度

• 空间复杂度 （space complexity）用于衡量算法占用内存空间 随着数据量变大时的增长趋势。

1.算法相关空间

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

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

  • 暂存数据 ：用于保存算法运行过程中的各种常量、变量、对象等。
  • 栈帧空间 ：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
  • 指令空间 ：用于保存编译后的程序指令，在实际统计中通常忽略不计。

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

• 在分析一段程序的空间复杂度时，我们通常统计暂存数据、栈帧空间和输出数据三部分 ，但是一般统计暂存空间 加上输出空间

2.推算方法

• 与时间复杂度类似，将统计操作数量 转为使用空间大小

• 但是不同于时间复杂度的是，通常只关注最差空间复杂度 ，必须确保在所有输入数据下都有足够的内存空间预留。

• 其中最差的含义：

  • 以最差输入数据为准 ：对于不同的数据量会有不同的空间复杂度，以最差的为准
  • 以算法运行中的峰值内存为准

• 在递归函数中，需要统计栈帧空间

int func() 
{
	return 0;
}

void loop(int n) 
{
	for (int i = 0; i < n; i++) 
    {
		func();
	}
}

void recur(int n) 
{
	if (n == 1) return;
	return recur(n - 1);
}

# 例如在这个代码中，loop函数中虽然在循环，但是每次调用后都会返回，会释放掉栈帧空间，空间复杂度为𝑂(1)

而recur递归函数，在归之前会有n个未返回的递归函数，会占用𝑂(n)的空间复杂度

3.常见类型

• 𝑂(1) < 𝑂(log 𝑛) < 𝑂(𝑛) < 𝑂(𝑛^2 ) < 𝑂(2^𝑛)

• 常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶

1.常数阶𝑂(1）

• 常数阶常见于数量与输入数据大小 𝑛 无关 的常量、变量、对象

# 需要注意的是，在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为 𝑂(1)

2.线性阶𝑂(n）

• 线性阶常见于元素数量与 𝑛 成正比 的数组、链表、栈、队列等

# n就是这些表和数组的长度

• 在递归函数 中，同时有多个未返回的函数，也使用 𝑂(𝑛) 大小的栈帧空间

3.平方阶𝑂(n^2）

• 平方阶常见于矩阵 （二维列表）和图 （由点（nodes）和线（边（edges））组成），元素数量与 𝑛 成平方关系

• 在递归函数 中，如递归深度为n，每个递归中又定义了一个数组，总体也占用 𝑂(𝑛^2 ) 空间

4.指数阶𝑂(2^n）

• 指数阶常见于二叉树，层数为 𝑛 的“满二叉树”的节点数量为 2^𝑛 − 1,占用 𝑂(2^n ) 空间

5.对数阶𝑂(log n）

• 对数阶常见于分治算法。例如归并排序，输入长度为 𝑛 的数组，每轮递归将数组从中点处划分为两半，形成高度为 log 𝑛 的递归树，使用 𝑂(log 𝑛) 栈帧空间。

5.权衡时间与空间

• 理想情况下，我们希望算法的时间复杂度和空间复杂度都能达到最优。然而在实际情况中，同时优化时间复杂度和空间复杂度通常非常困难
• 降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为以空间换时间 ；反之，则称为以时间换空间 。
• 选择哪种思路取决于我们更看重哪个方面。在大多数情况下 ，时间比空间更宝贵 ，因此以空间换时间 通常是更常用的策略。当然，在数据量很大 的情况下，控制空间复杂度 也非常重要

3.数据结构

1.数据结构定义

• 数据结构 （data structure）是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法

2.设计目标

• 空间占用 尽量少，以节省计算机内存。
• 数据操作 尽可能快速，涵盖数据访问、添加、删除、更新等。
• 提供简洁的数据表示和逻辑信息 ，以便算法高效运行。

# 通常来说这三者无法同时做到最好，只能相互权衡

3.与算法的关系

• 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。
• 算法为数据结构注入生命力。数据结构本身仅存储数据信息，结合算法才能解决特定问题。
• 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。

4.数据结构分类

• 常见的数据结构包括：
  • 数组
  • 链表
  • 栈
  • 队列
  • 哈希表
  • 树
  • 堆
  • 图
• 可以分为逻辑结构 和物理结构

1.逻辑结构

• 逻辑结构揭示了数据元素之间的逻辑关系 。
• 逻辑结构又可以分为两类
  • 线性数据结构
    • 数组
    • 链表
    • 栈
    • 队列
    • 哈希表
      • 元素之间是一对一的顺序关系
  • 非线性数据结构又可以分为两类
    • 树状结构
      • 树
      • 堆
      • 哈希表
        • 元素之间是一对多的关系
    • 网状结构
      • 图
        • 元素之间是多对多的关系

2.物理结构

• 算法程序中正在处理的数据主要存储在内存中，系统通过内存地址 来访问目标位置的数据

• 每个内存空间都有唯一 的内存地址

• 当一块内存被一个程序占用时，通常无法被其他程序同时使用

• 因此，在算法设计中，内存资源 是一个重要的考虑因素

• 物理结构反映了数据在计算机内存中的存储方式

• 可以分为

  • 连续空间存储（数组）
  • 分散空间存储（链表）

# 两种结构在时间效率 和空间效率 方面呈现互补

• 所有的数据结构都是基于数组，链表或二者的组合实现的
  • 基于数组可实现
    • 栈
    • 队列
    • 哈希表
    • 树
    • 堆
    • 图
    • 矩阵
    • 张量（维度>=3的数组）
    • 等
  • 基于链表可实现
    • 栈
    • 队列
    • 哈希表
    • 树
    • 堆
    • 图
    • 等

5.基本数据类型

• 参考Java中的数据类型

# 注意不同编程语言的数据类型的定义在占用空间，取值范围和默认值会有所不同

• 基本数据类型提供了数据的内容类型
• 数据结构提供了数据的组织方式

6.数字编码

1.原码，反码，补码

1.原码

• 十进制数据的二进制表现形式，最左边是符号位，0为正，1为负
• 八个bit为一个字节
• 最大值：01111111=127
• 最小值：11111111=-127

1.原码的计算

• 二进制的计算方式，加1，则直接在末位加1，满二进一

2.原码的弊端

• 用原码对正数进行计算是不会有问题的
• 但如果是负数计算，结果就出错，实际运算的结果与预期的结果是相反的

2.反码

• 为了解决原码不能计算负数 的问题而出现的

1.反码的计算

• 正数的反码不变，负数的反码在原码的基础上，符号位不变，数字取反，0变1，1变0

• 如果加1，则在末位加1，满二进一，得到的就是加1后的反码

2.反码的弊端

• 反码的11111111表示-0，如果再加1，则变为00000000=0
• 同样类似于-4的反码+7，跨0，会比正确结果小1

# 因为反码中的0有11111111和00000000两种表示方式

3.补码

• 在负数的反码的基础上加1，这样-0就是00000000，-1就是11111111，反码再依次向后，形成补码

• -127就是10000001，-128就是10000000，-128只有补码，没有原码

• 计算机中数字的存储计算都是以补码的形式来操作的

• 所以一个字节 的范围就是**-128~127**

2.浮点数编码

• 在IEEE 754标准中，32bit长度的float类型由三个部分组成

  • 符号位：S，占1位
  • 指数位：E，占8位
  • 分数为：N，占23位

• 尽管浮点数float扩展了取值范围 ，但其副作用是牺牲了精度 。

7.字符编码

1.ASCII字符集

• 用7位二进制数表示一个字符，最多能表示128个不同的字符

• 包含英文字母的大小写，数字，标点，控制字符（换行，制表）

• 字符用一个字节表示

2.GBK字符集

• 收录汉字，包含国家标准GB13000-1中的全部中日韩汉字，和BIG5编码中的所有汉字

• 计算机默认编码

• 字符用两个字节表示

3.Unicode字符集（统一码）

• 国际标准字符集，将世界各种语言的每个字符定义一个唯一的编码（码点），以满足跨语言，跨平台的文本信息转化

• 但它并没有规定在计算机中如何存储这些字符码点

• 当多种长度的码点同时出现在一个文本时，系统如何解析字符

• 可以将所有字符存储为等长的编码，通过补0，将所有字符的编码都变为2字节长度

• 但是这样非常浪费空间

4.UTF-8编码

• 是国际上使用最广泛的Unicode编码方法

• 它是一种可变长度 的编码

• 使用1~4个字节来表示一个字符，根据复杂度而变

• ASCII字符需要1字节

• 拉丁字母和希腊字母需要2字节

• 常用中文字符需要3字节

• 一些生僻字需要4字节

• 对于长度为1字节的字符，将最高位设置为0，其余7位设置位Unicode编码，ASCII字符在Unicode字符集中占前128个码点，所以UTF-8编码可以向下兼容ASCII码

• 除了UTF-8以外还有两种常见的编码方式

• UTF‑16 编码 ：使用 2 或 4 字节来表示一个字符。所有的 ASCII 字符和常用的非英文字符，都用 2 字节表示；少数字符需要用到 4 字节表示。对于 2 字节的字符，UTF‑16 编码与 Unicode 码点相等。

• UTF‑32 编码 ：每个字符都使用 4 字节。这意味着 UTF‑32 比 UTF‑8 和 UTF‑16 更占用空间，特别是对于 ASCII 字符占比较高的文本

• 从存储空间占用的角度来看，UTF-8的效率非常高，对比UTF-16和UTF-32更加高效

• 从兼容性角度来看，UTF-8的通用性也是最佳

5.编程语言的字符编码

• 于以往的大多数编程语言，程序运行中的字符串都采用 UTF‑16 或 UTF‑32 这类等长编码。在等长编码下，可以将字符串看作数组来处理，这种做法具有以下优点
  • 随机访问：UTF‑16 编码的字符串可以很容易地进行随机访问。UTF‑8 是一种变长编码，要想找到第 𝑖个字符，我们需要从字符串的开始处遍历到第 𝑖 个字符，这需要 𝑂(𝑛) 的时间。
  • 字符计数：与随机访问类似，计算 UTF‑16 编码的字符串的长度也是 𝑂(1) 的操作。但是，计算 UTF‑8编码的字符串的长度需要遍历整个字符串。
  • 字符串操作：在 UTF‑16 编码的字符串上，很多字符串操作（如分割、连接、插入、删除等）更容易进行。

# 在 UTF‑8 编码的字符串上，进行这些操作通常需要额外的计算，以确保不会产生无效的 UTF‑8 编码

# 但是在文件存储和网络传输中通常还是将字符串编码位UTF-8格式，以达到最优的兼容性和空间效率。

4.数组与链表

1.数组

• 数组 （array）是一种线性数据结构 ，其将相同类型 的元素存储在连续的内存空间 中。我们将元素在数组中的位置称为该元素的索引 （index）。

1.数组常用操作

1.初始化数组

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

2.访问元素

• 因为被存储在连续的内存空间中，所以只要给定数组的内存地址（首元素的内存地址）和某个元素的索引，就可以计算除该元素的内存地址，从而直接访问该元素
• 计算公式：元素内存地址 = 数组内存地址 + 元素长度 * 元素索引

# 元素长度是又元素的类型决定的

• 索引是从0开始的，因为索引本质上是内存地址的偏移量，第一个元素的地址偏移量是0，因此索引为0

3.插入元素

• 由于数组是连续存储 的，所以要插入元素，就要将该元素后的所有元素都向后移动一位 ，再将元素赋值给索引
• 但是数组的长度是确定的，这样会导致最后一个元素的丢失

4.删除元素

• 与插入相同，将删除元素后面的元素都向前移动一位

• 因此插入和删除会有以下缺点

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

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

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

5.遍历数组

• 既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素

6.查找元素

• 在数组中查找指定元素需要遍历数组，判断是否匹配
• 因为数组是线性数据结构，所以这种查找操作称为线性查找

7.扩容数组

• 当原本的数组长度不够时，需要扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个𝑂(𝑛) 的操作，在数组很大的情况下非常耗时

2.数组的优点与局限性

1.优点

• 空间效率高 ：数组为数据分配了连续的内存块，无须额外的结构开销。
• 支持随机访问 ：数组允许在 𝑂(1) 时间内访问任何元素。
• 缓存局部性 ：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

2.局限性

• 插入与删除效率低 ：当数组中元素较多时，插入与删除操作需要移动大量的元素。
• 长度不可变 ：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
• 空间浪费 ：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

2.链表

• 链表 （linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过引用 相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点

• 因为计算机的内存空间的占用是分散的并不连续，但是数组的存储必须连续，数组过大时，内存不一定能够提供连续空间

• 链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

• 链表的组成单位是节点 （node），其中包含数据

  • 值
  • 指向下一个节点的引用（在支持指针的语言中，引用就替换为指针 ）

  # 因此链表在相同数据量下所占用的空间也比数组要大

• 链表的首个节点就叫头节点 ，最后一个节点就叫尾节点

1.链表常用操作

1.初始化链表

1.初始化各个节点对象

ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);

2.构建节点之间的引用关系

n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

# 通常将链表头作为链表的代称，上述代码的链表可以称为n0

2.插入节点

• 插入一个新的节点，只需要更改相邻两个节点的引用（指针） ，时间复杂度为𝑂(1)

void insert(ListNode *n0, ListNode *P) {
	ListNode *n1 = n0->next;
	P->next = n1;
	n0->next = P;
}

3.删除节点

• 删除一个节点，只需要改变前一个节点的引用（指针）
• 被删除节点的引用虽然还存在，但因为已经无法被访问到了，所以认为已经被删除

void removeItem(ListNode *n0) {
	if (!n0->next)
		return;
	// n0 -> P -> n1
	ListNode *P = n0->next;
    ListNode *n1 = P->next;
	n0->next = n1;
	// 释放内存
	free(P);
}

4.访问节点

• 链表中访问节点的效率较低，需要从头开始，逐个向后遍历 ，时间复杂度为 𝑂(𝑛)

ListNode *access(ListNode *head, int index) {
	for (int i = 0; i < index; i++) {
		if (head == NULL)
			return NULL;
		head = head->next;
	}
	return head;
}

5.查找节点

• 查找某一个值的节点，遍历链表，也是线性查找

int find(ListNode *head, int target) {
	int index = 0;
	while (head) {
		if (head->val == target)
			return index;
		head = head->next;
		index++;
	}
	return -1;
}

2.数组与节点的对比

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	𝑂(1)	𝑂(𝑛)
添加元素	𝑂(𝑛)	𝑂(1)
删除元素	𝑂(𝑛)	𝑂(1)

3.常见链表类型

• 单向链表 ：即普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。

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

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

4.链表典型应用

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

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

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

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

    表与该顶点相连的其他顶点

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

  • 高级数据结构 ：比如在红黑树、B 树中，我们需要访问节点的父节点 ，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
  • 浏览器历史 ：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
  • LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

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

  • 时间片轮转调度算法 ：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
  • 数据缓冲区 ：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器 中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放 。

3.列表

• 列表（list）是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。

• 当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低

• 可以使用动态数组 （dynamic array）来实现列表

• 许多语言中提供的列表都是基于动态数组实现的

• 但是c语言中没有动态数组

1列表常用操作

1.初始化列表

1.无初始值

nums1: list[int] = []

2.有初始值

nums: list[int] = [1, 3, 2, 5, 4]

2.访问元素

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

num: int = nums[1]

3.插入和删除元素

• 在列表尾部添加元素 的时间复杂度为 𝑂(1) ，但插入和删除元素的效率仍与数组相同，时间复杂度为 𝑂(𝑛) 。

nums.insert(3, 6)

# 在索引为3的位置插入数字6

nums.pop(3)

# 删除索引为3的元素

4.遍历列表

• 和数组一样，可以根据索引遍历，也可以直接遍历

count = 0

for i in range(len(nums)):

	count += nums[i]

# 通过索引遍历列表

for num in nums:

	count += num

# 直接遍历列表元素

5.拼接列表

• 将一个列表拼接到另一个列表的尾部

nums1: list[int] = [6, 8, 7, 10, 9]
nums += nums1

6.排序列表

• 将列表元素排序，便于后面的二分查找和双指针

nums.sort()

2.列表实现

• 一个简易的列表主要有三个部分
  • 初始容量 ：选取一个合理的数组初始容量。
  • 数量记录 ：声明一个变量 size ，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。
  • 扩容机制 ：若插入元素时列表容量已满，则需要进行扩容。先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组

4.内存与缓存

• 物理结构在很大程度上决定了程序对内存和缓存的使用效率 ，影响算法的整体性能

1.计算机存储设备

• 主要包含硬盘（hard disk）、内存（random‑access memory, RAM）、缓存（cache memory）

	硬盘	内存	缓存
用途	长期存储数据，包括操作系统、程序、文件等	临时存储当前运行的程序和正在处理的数据	存储经常访问的数据和指令，减少 CPU访问内存的次数
易失性	断电后数据不会丢失	断电后数据会丢失	断电后数据会丢失
容量	较大，TB 级别	较小，GB 级别	非常小，MB 级别
速度	较慢，几百到几千 MB/s	较快，几十 GB/s	非常快，几十到几百 GB/s
价格	较便宜，几毛到几元 / GB	较贵，几十到几百元 / GB	非常贵，随 CPU 打包计价

• 硬盘难以被内存取代 。首先，内存中的数据在断电后会丢失，因此它不适合长期存储数据 ；其次，内存的成本是硬盘的几十倍，这使得它难以在消费者市场普及。

• 缓存的大容量和高速度难以兼得 。随着L1、L2、L3缓存的容量逐步增大，其物理尺寸会变大 ，与 CPU核心之间的物理距离会变远，从而导致数据传输时间增加 ，元素访问延迟变高 。在当前技术下，多层级 的缓存结构是容量、速度和成本之间的最佳平衡点

• 总的来说，硬盘用于长期存储大量数据，内存用于临时存储程序运行中正在处理的数据，而缓存则用于存储经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行

• 在程序运行时，数据会从硬盘中被读取到内存中 ，供CPU计算使用。缓存可以看作CPU的一部分，它通过智能地从内存加载数据，给CPU提供高速的数据读取，从而显著提升程序的执行效率，减少对较慢的内存的依赖

2.数据结构的内存效率

• 内存是有限的，而且同一块内存只能有一个程序使用
  • 数组：需要连续的内存空间，可能导致浪费，而且扩容时也需要时间和空间
  • 链表：以节点为单位，更加灵活
• 程序运行时，反复申请和释放内存，空闲的内存碎片化程度变高
  • 数组：连续存储，不容易导致内存碎片化
  • 链表：分散存储，频繁的插入与删除，易导致内存碎片化

3.数据结构的缓存效率

• 由于缓存的容量有限 ，只能存储一小部分频繁访问的数据 ，因此当CPU尝试访问的数据不在缓存中时，就会发生缓存未命中 （cache miss），此时CPU不得不从速度较慢的内存中加载所需数据

• 缓存未命中 越少，CPU读写数据的效率就越高，将CPU 从缓存中成功获取数据的比例称为缓存命中率 （cache hit rate），这个指标通常用来衡量缓存效率。

• 为了尽可能达到更高的效率，缓存会采取以下数据加载机制

  • 缓存行 ：缓存不是单个字节地存储与加载数据，而是以缓存行为单位 。相比于单个字节的传输，缓存行的传输形式更加高效 。
  • 预取机制 ：处理器会尝试预测数据访问模式 （例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。
  • 空间局部性 ：如果一个数据被访问，那么它附近的数据 可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据 ，以提高命中率。
  • 时间局部性 ：如果一个数据被访问，那么它在不久的将来很可能再次被访问 。缓存利用这一原理，通过保留最近访问过的数据 来提高命中率

• 数组和链表对缓存的利用效率是不同的：

  • 占用空间 ：链表元素 比数组元素占用空间更多 ，导致缓存中容纳的有效数据量更少 。
  • 缓存行 ：链表数据分散 在内存各处，而缓存是按行加载 的，因此加载到无效数据 的比例更高。
  • 预取机制 ：数组 比链表的数据访问模式更具可预测性 ，即系统更容易猜出即将被加载的数据。
  • 空间局部性 ：数组被存储在集中 的内存空间中，因此被加载数据附近的数据 更有可能即将被访问

• 总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表 。

5.栈与队列

1.栈

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

• 可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。

• 将把元素添加到栈顶 的操作叫作入栈 ，删除栈顶元素 的操作叫作出栈 。

1.栈的常用操作

方法	描述	时间复杂度
push()	元素入栈（添加至栈顶）	𝑂(1)
pop()	栈顶元素出栈	𝑂(1)
peek()	访问栈顶元素	𝑂(1)

# 不同语言的方法名不一定相同

# 通常情况下，可以直接使用编程语言内置的栈类，但是，c语言没有提供

# 可以将c语言的数组或者链表当作栈来使用，并在程序逻辑上忽略与栈无关的操作

/* 初始化栈 */
Stack<Integer> stack = new Stack<>();

/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);

/* 访问栈顶元素 */
int peek = stack.peek();

/* 元素出栈 */
int pop = stack.pop();

/* 获取栈的长度 */
int size = stack.size();

/* 判断是否为空 */
boolean isEmpty = stack.isEmpty();

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

# 元素入栈
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

2.栈的实现

• 遵循栈先入后出的原则，只能在栈顶添加删除元素，但数组和链表可以在任意位置添加删除元素
• 可以将栈视为一种受限制的数组或链表

1.基于链表的实现

• 将链表的头节点视为栈顶，尾节点视为栈底
• 对于入栈操作，只需在链表头部插入元素即可，这种节点插入方法被称为头插法
• 对于出栈操作，只需将头节点从链表中删除即可

/* 基于链表实现的栈 */
typedef struct {
	ListNode *top; // 将头节点作为栈顶
	int size; // 栈的长度
} LinkedListStack;

/* 构造函数 */
LinkedListStack *newLinkedListStack() {
	LinkedListStack *s = malloc(sizeof(LinkedListStack));
	s->top = NULL;
	s->size = 0;
	return s;
}

/* 析构函数 */
void delLinkedListStack(LinkedListStack *s) {
	while (s->top) {
		ListNode *n = s->top->next;
		free(s->top);
		s->top = n;
	}
	free(s);
}

/* 获取栈的长度 */
int size(LinkedListStack *s) {
	return s->size;
}

/* 判断栈是否为空 */
bool isEmpty(LinkedListStack *s) {
	return size(s) == 0;
}

/* 入栈 */
void push(LinkedListStack *s, int num) {
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	node->next = s->top; // 更新新加节点指针域
	node->val = num; // 更新新加节点数据域
	s->top = node; // 更新栈顶
	s->size++; // 更新栈大小
}

/* 访问栈顶元素 */
int peek(LinkedListStack *s) {
	if (s->size == 0) {
		printf(" 栈为空\n");
		return INT_MAX;
	}
	return s->top->val;
}

/* 出栈 */
int pop(LinkedListStack *s) {
	int val = peek(s);
	ListNode *tmp = s->top;
	s->top = s->top->next;
	// 释放内存
	free(tmp);
	s->size--;
	return val;
}

2.基于数组的实现

• 将数组尾部视为栈顶，入栈和出栈分别对应在数组尾部添加和删除元素
• 由于入栈的元素可能会一致增加，所以使用动态数组，不需要再去处理数组扩容的问题

/* 基于数组实现的栈 */
typedef struct {
	int *data;
	int size;
} ArrayStack;

/* 构造函数 */
ArrayStack *newArrayStack() {
	ArrayStack *stack = malloc(sizeof(ArrayStack));
	// 初始化一个大容量，避免扩容
	stack->data = malloc(sizeof(int) * MAX_SIZE);
	stack->size = 0;
	return stack;
}

/* 析构函数 */
void delArrayStack(ArrayStack *stack) {
	free(stack->data);
	free(stack);
}

/* 获取栈的长度 */
int size(ArrayStack *stack) {
	return stack->size;
}

/* 判断栈是否为空 */
bool isEmpty(ArrayStack *stack) {
	return stack->size == 0;
}

/* 入栈 */
void push(ArrayStack *stack, int num) {
	if (stack->size == MAX_SIZE) {
		printf(" 栈已满\n");
		return;
	}
	stack->data[stack->size] = num;
	stack->size++;
}

/* 访问栈顶元素 */
int peek(ArrayStack *stack) {
	if (stack->size == 0) {
		printf(" 栈为空\n");
    	return INT_MAX;
	}
	return stack->data[stack->size - 1];
}

/* 出栈 */
int pop(ArrayStack *stack) {
	int val = peek(stack);
	stack->size--;
	return val;
}

# c语言中没有内置动态数组，所以仅使用一个大容量的数组来避免扩容问题

3.两种实现的对比

• 支持操作

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

• 时间效率

  • 在基于数组 的实现中，入栈和出栈操作都在预先分配好的连续内存中进行，具有很好的缓存本地性 ，因此效率较高 。然而，如果入栈时超出数组容量 ，会触发扩容机制 ，导致该次入栈操作的时间复杂度变为𝑂(𝑛) 。
  • 在基于链表 的实现中，链表的扩容非常灵活 ，不存在上述数组扩容时效率降低的问题。但是，入栈 操作需要初始化节点对象并修改指针 ，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤 ，从而提高效率。
  • 综上所述，当入栈与出栈操作的元素是基本数据类型时，例如 int 或 double ，我们可以得出以下结论
    • 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高 。
    • 基于链表实现的栈可以提供更加稳定 的效率表现。

• 空间效率

  • 在初始化列表时，系统会为列表分配初始容量 ，该容量可能超出实际需求 ；并且，扩容机制通常是按照特定倍率（例如 2 倍）进行扩容的，扩容后的容量 也可能超出实际需求 。因此，基于数组实现的栈可能造成一定的空间浪费。
  • 然而，由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。
  • 综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。

4.栈的典型应用

• 浏览器中的后退与前进、软件中的撤销与反撤销 。每当打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退 操作实际上是在执行出栈 。如果要同时支持后退和前进，那么需要两个栈来配合实现。
• 程序内存管理 。每次调用函数 时，系统都会在栈顶添加一个栈帧 ，用于记录函数的上下文信息 。在递归函数中，向下递推 阶段会不断执行入栈 操作，而向上回溯 阶段则会不断执行出栈 操作

2.队列

• 队列 （queue）是一种遵循先入先出 规则的线性数据结构
• 将队列头部称为队首 ，尾部则称为队尾 ，将元素加入队尾 的操作称为入队 ，删除队首 元素则称为出队

1.队列常用操作

方法	描述	时间复杂度
push()	元素入队（将元素添加到队尾）	𝑂(1)
pop()	队首元素出队	𝑂(1)
peek()	访问队首元素	𝑂(1)

# 不同语言的方法名不一定相同

# c语言未提供内置队列

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)

# 访问队首元素
front: int = que[0]

# 元素出队
pop: int = que.popleft()

# 获取队列的长度
size: int = len(que)

# 判断队列是否为空
is_empty: bool = len(que) == 0

2.队列的实现

1.基于链表的实现

• 将头节点 对应队首 ，尾节点 对应队尾 ，并且队尾只能添加节点，队首只能删除节点

/* 基于链表实现的队列 */
typedef struct {
	ListNode *front, *rear;
	int queSize;
} LinkedListQueue;

/* 构造函数 */
LinkedListQueue *newLinkedListQueue() {
	LinkedListQueue *queue = (LinkedListQueue *)malloc(sizeof(LinkedListQueue));
	queue->front = NULL;
	queue->rear = NULL;
	queue->queSize = 0;
	return queue;
}

/* 析构函数 */
	void delLinkedListQueue(LinkedListQueue *queue) {
		// 释放所有节点
		while (queue->front != NULL) {
			ListNode *tmp = queue->front;
			queue->front = queue->front->next;
			free(tmp);
	}
	// 释放 queue 结构体
	free(queue);
}

/* 获取队列的长度 */
int size(LinkedListQueue *queue) {
	return queue->queSize;
}

/* 判断队列是否为空 */
bool empty(LinkedListQueue *queue) {
	return (size(queue) == 0);
}

/* 入队 */
void push(LinkedListQueue *queue, int num) {
	// 尾节点处添加 node
	ListNode *node = newListNode(num);
	// 如果队列为空，则令头、尾节点都指向该节点
	if (queue->front == NULL) {
		queue->front = node;
		queue->rear = node;
	}
	// 如果队列不为空，则将该节点添加到尾节点后
	else {
		queue->rear->next = node;
		queue->rear = node;
	}
    queue->queSize++;
}

/* 访问队首元素 */
int peek(LinkedListQueue *queue) {
	assert(size(queue) && queue->front);
	return queue->front->val;
}

/* 出队 */
int pop(LinkedListQueue *queue) {
	int num = peek(queue);
	ListNode *tmp = queue->front;
	queue->front = queue->front->next;
	free(tmp);
	queue->queSize--;
	return num;
}

/* 打印队列 */
void printLinkedListQueue(LinkedListQueue *queue) {
	int *arr = malloc(sizeof(int) * queue->queSize);
	// 拷贝链表中的数据到数组
	int i;
	ListNode *node;
	for (i = 0, node = queue->front; i < queue->queSize; i++) {
		arr[i] = node->val;
		node = node->next;
	}
	printArray(arr, queue->queSize);
	free(arr);
}

2.基于数组的实现

• 在数组中删除首元素的时间复杂度为 𝑂(𝑛) ，这会导致出队操作效率较低。

• 所以可以用以下方法来解决

• 用一个变量front来指向队首 元素，再用一个变量size来记录队列的长度 ，再定义一个rear=front+size，指向的结果就是队尾元素后的下一个位置

• 那么数组中包含元素的区间就是[front,rear-1]

  • 入队：将输入的元素赋值给rear计算出的索引，并且将size+1
  • 出队：将front+1，size-1

• 这样就可以将时间复杂度降为 𝑂(1)

• 但是上面入队和出队操作中front和rear都在不断增加，即向右移动 ，如果到达了队尾就无法再移动了

• 所以可以将数组视为首尾相接的环形数组

• 即当front和rear将要越过数组的尾部时，通过取余操作，使其回到数组的头部继续遍历

/* 基于环形数组实现的队列 */
typedef struct {
	int *nums; // 用于存储队列元素的数组
	int front; // 队首指针，指向队首元素
	int queSize; // 尾指针，指向队尾 + 1
	int queCapacity; // 队列容量
} ArrayQueue;

/* 构造函数 */
ArrayQueue *newArrayQueue(int capacity) {
	ArrayQueue *queue = (ArrayQueue *)malloc(sizeof(ArrayQueue));
	// 初始化数组
	queue->queCapacity = capacity;
	queue->nums = (int *)malloc(sizeof(int) * queue->queCapacity);
	queue->front = queue->queSize = 0;
	return queue;
}

/* 析构函数 */
void delArrayQueue(ArrayQueue *queue) {
	free(queue->nums);
	free(queue);
}

/* 获取队列的容量 */
int capacity(ArrayQueue *queue) {
	return queue->queCapacity;
}

/* 获取队列的长度 */
int size(ArrayQueue *queue) {
	return queue->queSize;
}

/* 判断队列是否为空 */
bool empty(ArrayQueue *queue) {
	return queue->queSize == 0;
}

/* 访问队首元素 */
int peek(ArrayQueue *queue) {
	assert(size(queue) != 0);
	return queue->nums[queue->front];
}

/* 入队 */
void push(ArrayQueue *queue, int num) {
	if (size(queue) == capacity(queue)) {
		printf(" 队列已满\r\n");
		return;
	}
	// 计算队尾指针，指向队尾索引 + 1
	// 通过取余操作实现 rear 越过数组尾部后回到头部
	int rear = (queue->front + queue->queSize) % queue->queCapacity;
	// 将 num 添加至队尾
	queue->nums[rear] = num;
	queue->queSize++;
}

/* 出队 */
int pop(ArrayQueue *queue) {
	int num = peek(queue);
	// 队首指针向后移动一位，若越过尾部，则返回到数组头部
	queue->front = (queue->front + 1) % queue->queCapacity;
    queue->queSize--;
	return num;
}

/* 返回数组用于打印 */
int *toArray(ArrayQueue *queue, int *queSize) {
	*queSize = queue->queSize;
	int *res = (int *)calloc(queue->queSize, sizeof(int));
	int j = queue->front;
	for (int i = 0; i < queue->queSize; i++) {
		res[i] = queue->nums[j % queue->queCapacity];
		j++;
	}
	return res;
}

# 这样的队列仍然会受限于数组长度不可变的问题，所以可以再将数组替换为动态数组，加入扩容机制

3.队列的典型应用

• 淘宝订单 。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
• 各类待办事项 。任何需要实现先来后到 功能的场景，例如打印机的任务队列 、餐厅的出餐队列 等，队列在这些场景中可以有效地维护处理顺序 。

3.双向队列

• 双向队列 （double‑ended queue）提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。

1.双向队列的常用操作

方法名	描述	时间复杂度
push_first()	将元素添加至队首	𝑂(1)
push_last()	将元素添加至队尾	𝑂(1)
pop_first()	删除队首元素	𝑂(1)
pop_last()	删除队尾元素	𝑂(1)
peek_first()	访问队首元素	𝑂(1)
peek_last()	访问队尾元素	𝑂(1)

# 不同编程语言的方法名不一定相同

from collections import deque

# 初始化双向队列
deq: deque[int] = deque()

# 元素入队
deq.append(2) # 添加至队尾
deq.append(5)
deq.append(4)
deq.appendleft(3) # 添加至队首
deq.appendleft(1)

# 访问元素
front: int = deq[0] # 队首元素
rear: int = deq[-1] # 队尾元素

# 元素出队
pop_front: int = deq.popleft() # 队首元素出队
pop_rear: int = deq.pop() # 队尾元素出队

# 获取双向队列的长度
size: int = len(deq)

# 判断双向队列是否为空
is_empty: bool = len(deq) == 0

2.双向队列实现

1.基于双向链表的实现

• 双向链表的头节点和尾节点都可以视为队首和队尾，可以在两端添加和删除节点

/* 双向链表节点 */
typedef struct DoublyListNode {
	int val; // 节点值
	struct DoublyListNode *next; // 后继节点
	struct DoublyListNode *prev; // 前驱节点
} DoublyListNode;

/* 构造函数 */
DoublyListNode *newDoublyListNode(int num) {
	DoublyListNode *new = (DoublyListNode *)malloc(sizeof(DoublyListNode));
	new->val = num;
	new->next = NULL;
	new->prev = NULL;
	return new;
}

/* 析构函数 */
void delDoublyListNode(DoublyListNode *node) {
	free(node);
}

/* 基于双向链表实现的双向队列 */
typedef struct {
	DoublyListNode *front, *rear; // 头节点 front ，尾节点 rear
	int queSize; // 双向队列的长度
} LinkedListDeque;

/* 构造函数 */
LinkedListDeque *newLinkedListDeque() {
	LinkedListDeque *deque = (LinkedListDeque *)malloc(sizeof(LinkedListDeque));
	deque->front = NULL;
	deque->rear = NULL;
	deque->queSize = 0;
	return deque;
}

/* 析构函数 */
void delLinkedListdeque(LinkedListDeque *deque) {
	// 释放所有节点
	for (int i = 0; i < deque->queSize && deque->front != NULL; i++) {
		DoublyListNode *tmp = deque->front;
		deque->front = deque->front->next;
		free(tmp);
	}
	// 释放 deque 结构体
	free(deque);
}

/* 获取队列的长度 */
int size(LinkedListDeque *deque) {
	return deque->queSize;
}

/* 判断队列是否为空 */
bool empty(LinkedListDeque *deque) {
	return (size(deque) == 0);
}

/* 入队 */
void push(LinkedListDeque *deque, int num, bool isFront) {
	DoublyListNode *node = newDoublyListNode(num);
	// 若链表为空，则令 front 和 rear 都指向 node
	if (empty(deque)) {
		deque->front = deque->rear = node;
	}
	// 队首入队操作
	else if (isFront) {
		// 将 node 添加至链表头部
		deque->front->prev = node;
		node->next = deque->front;
		deque->front = node; // 更新头节点
	}
	// 队尾入队操作
	else {
	// 将 node 添加至链表尾部
		deque->rear->next = node;
		node->prev = deque->rear;
		deque->rear = node;
	}
	deque->queSize++; // 更新队列长度
}

/* 队首入队 */
void pushFirst(LinkedListDeque *deque, int num) {
	push(deque, num, true);
}

/* 队尾入队 */
void pushLast(LinkedListDeque *deque, int num) {
	push(deque, num, false);
}

/* 访问队首元素 */
int peekFirst(LinkedListDeque *deque) {
	assert(size(deque) && deque->front);
    return deque->front->val;
}

/* 访问队尾元素 */
int peekLast(LinkedListDeque *deque) {
	assert(size(deque) && deque->rear);
	return deque->rear->val;
}

/* 出队 */
int pop(LinkedListDeque *deque, bool isFront) {
	if (empty(deque))
		return -1;
	int val;
	// 队首出队操作
	if (isFront) {
		val = peekFirst(deque); // 暂存头节点值
		DoublyListNode *fNext = deque->front->next;
		if (fNext) {
			fNext->prev = NULL;
			deque->front->next = NULL;
		}
		delDoublyListNode(deque->front);
		deque->front = fNext; // 更新头节点
	}
	// 队尾出队操作
	else {
		val = peekLast(deque); // 暂存尾节点值
		DoublyListNode *rPrev = deque->rear->prev;
		if (rPrev) {
			rPrev->next = NULL;
			deque->rear->prev = NULL;
		}
		delDoublyListNode(deque->rear);
		deque->rear = rPrev; // 更新尾节点
	}
	deque->queSize--; // 更新队列长度
	return val;
}

/* 队首出队 */
int popFirst(LinkedListDeque *deque) {
	return pop(deque, true);
}

/* 队尾出队 */
int popLast(LinkedListDeque *deque) {
    return pop(deque, false);
}

/* 打印队列 */
void printLinkedListDeque(LinkedListDeque *deque) {
	int *arr = malloc(sizeof(int) * deque->queSize);
	// 拷贝链表中的数据到数组
	int i;
	DoublyListNode *node;
	for (i = 0, node = deque->front; i < deque->queSize; i++) {
		arr[i] = node->val;
		node = node->next;
	}
	printArray(arr, deque->queSize);
	free(arr);
}

2.基于数组的实现

• 用环形数组来实现

/* 基于环形数组实现的双向队列 */
typedef struct {
	int *nums; // 用于存储队列元素的数组
	int front; // 队首指针，指向队首元素
	int queSize; // 尾指针，指向队尾 + 1
	int queCapacity; // 队列容量
} ArrayDeque;

/* 构造函数 */
ArrayDeque *newArrayDeque(int capacity) {
	ArrayDeque *deque = (ArrayDeque *)malloc(sizeof(ArrayDeque));
	// 初始化数组
	deque->queCapacity = capacity;
	deque->nums = (int *)malloc(sizeof(int) * deque->queCapacity);
	deque->front = deque->queSize = 0;
	return deque;
}

/* 析构函数 */
void delArrayDeque(ArrayDeque *deque) {
	free(deque->nums);
	free(deque);
}

/* 获取双向队列的容量 */
int capacity(ArrayDeque *deque) {
	return deque->queCapacity;
}

/* 获取双向队列的长度 */
int size(ArrayDeque *deque) {
	return deque->queSize;
}

/* 判断双向队列是否为空 */
bool empty(ArrayDeque *deque) {
	return deque->queSize == 0;
}

/* 计算环形数组索引 */
int dequeIndex(ArrayDeque *deque, int i) {
	// 通过取余操作实现数组首尾相连
	// 当 i 越过数组尾部时，回到头部
	// 当 i 越过数组头部后，回到尾部
	return ((i + capacity(deque)) % capacity(deque));
}

/* 队首入队 */
void pushFirst(ArrayDeque *deque, int num) {
	if (deque->queSize == capacity(deque)) {
		printf(" 双向队列已满\r\n");
		return;
	}
	// 队首指针向左移动一位
	// 通过取余操作实现 front 越过数组头部回到尾部
	deque->front = dequeIndex(deque, deque->front - 1);
	// 将 num 添加到队首
	deque->nums[deque->front] = num;
	deque->queSize++;
}

/* 队尾入队 */
void pushLast(ArrayDeque *deque, int num) {
	if (deque->queSize == capacity(deque)) {
		printf(" 双向队列已满\r\n");
		return;
	}
	// 计算队尾指针，指向队尾索引 + 1
	int rear = dequeIndex(deque, deque->front + deque->queSize);
	// 将 num 添加至队尾
	deque->nums[rear] = num;
	deque->queSize++;
}

/* 访问队首元素 */
int peekFirst(ArrayDeque *deque) {
	// 访问异常：双向队列为空
	assert(empty(deque) == 0);
	return deque->nums[deque->front];
}

/* 访问队尾元素 */
int peekLast(ArrayDeque *deque) {
	// 访问异常：双向队列为空
	assert(empty(deque) == 0);
	int last = dequeIndex(deque, deque->front + deque->queSize - 1);
	return deque->nums[last];
}

/* 队首出队 */
int popFirst(ArrayDeque *deque) {
	int num = peekFirst(deque);
	// 队首指针向后移动一位
	deque->front = dequeIndex(deque, deque->front + 1);
	deque->queSize--;
	return num;
}

/* 队尾出队 */
int popLast(ArrayDeque *deque) {
	int num = peekLast(deque);
	deque->queSize--;
	return num;
}

/* 返回数组用于打印 */
int *toArray(ArrayDeque *deque, int *queSize) {
	*queSize = deque->queSize;
	int *res = (int *)calloc(deque->queSize, sizeof(int));
	int j = deque->front;
	for (int i = 0; i < deque->queSize; i++) {
		res[i] = deque->nums[j % deque->queCapacity];
		j++;
	}
	return res;
}

3.双向队列的应用

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

• 例如：因为软件限制只能撤销最多50步，（撤销功能就需要栈来实现）当栈中存储超过50步的内容时，所以在长度超过50的时候要将队首删除 ，（这就需要队列的功能）也就是将50步以前的删除掉，减少占用过多的内存

• 双向队列相当于是给这个栈设置了最大容量

6.哈希表

1.哈希表

• 哈希表 （hash table），又称散列表 ，它通过建立键key 与值value 之间的映射 ，实现高效的元素查询。

• 效率对比

	数组	链表	哈希表
查找元素	𝑂(𝑛)	𝑂(𝑛)	𝑂(1)
添加元素	𝑂(1)	𝑂(1)	𝑂(1)
删除元素	𝑂(𝑛)	𝑂(𝑛)	𝑂(1)

1.哈希表常用操作

# c语言没有提供内置哈希表

• 哈希表的常见操作：初始化，查询操作，添加键值对，删除键值对

# 初始化哈希表
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)

• 常用的遍历方式：遍历键值对，遍历键，遍历值

# 遍历哈希表
# 遍历键值对 key->value
for key, value in hmap.items():
	print(key, "->", value)

    # 单独遍历键 key
for key in hmap.keys():
	print(key)

    # 单独遍历值 value
for value in hmap.values():
	print(value)

2.哈希表简单实现

• 考虑最简单的情况，仅用一个数组来实现哈希表

• 将数组的每个空位称为桶 ，每个桶中存储一个键值对

• 查询操作就是找到key对应的桶 ，再在桶中获取value

• 哈希函数 （hash function）可以通过key来定位到对应的桶

• 此函数可以将一个较大的输入空间映射到一个较小的输出空间

• 即将所有key映射到所有桶（数组索引）

• 哈希函数的计算分为两步：

  • 通过哈希算法hash（）计算得到哈希值
  • 将哈希值对桶数量（数组长度）capacity取模，从而获取该key对应的数组索引index
  • index = hash(key) % capacity

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) -> str:
		""" 查询操作"""
		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[Pair]:
		""" 获取所有键值对"""
		result: list[Pair] = []
		for pair in self.buckets:
			if pair is not None:
				result.append(pair)
		return result

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

    def value_set(self) -> list[str]:
		""" 获取所有值"""
		result = []
		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)

# 这里设置数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100

3.哈希冲突与扩容

• 哈希函数可以将一个较大的 输入空间映射到一个较小的 输出空间

• 所以理论上必定会存在重复的现象

• 即多个输入对应一个输出

• 将这种多个输入对应同一输出的情况称为哈希冲突 （hash collision）

• 扩容哈希表（数组）可以降低哈希冲突的概率

• 但是扩容就需要用到数组的迁移，所以在一开始就要给哈希表留足够大的容量，防止频繁扩容

• 负载因子 （load factor）是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量 ，用于衡量哈希冲突的严重程度 ，也常作为哈希表扩容的触发条件 。

• 例如在 Java 中，当负载因子超过0.75时，系统会将哈希表扩容至原先的2倍。

2.哈希冲突

• 理论上哈希冲突是不可避免的
• 可以通过一直扩容直到哈希冲突消失，但是效率过低
• 可以采取两种策略
  • 改良哈希表的数据结构，使得哈希表可以在出现哈希冲突的时候正常工作
  • 仅在哈希冲突严重的时候才执行扩容操作

1.链式地址

• 在原始哈希表中，每个桶仅能存储一个键值对。链式地址 （separate chaining）将单个元素转换为链表 ，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表 中

• 是一个索引对应数组元素 ，数组元素再对应一个链表 的结构

• 其操作方式也就发生了改变

  • 查询元素：输入key，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比key以查找目标键值对。
  • 添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表中。
  • 删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除。

• 因此也就存在了局限性

  • 占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
  • 查询效率降低：因为需要线性遍历链表来查找对应元素。

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

	def __init__(self):
		""" 构造方法"""
		self.size = 0 # 键值对数量
		self.capacity = 4 # 哈希表容量
		self.load_thres = 2.0 / 3.0 # 触发扩容的负载因子阈值
		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 | None:
		""" 查询操作"""
		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)                

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

# 这里实现包含哈希表扩容方法。当负载因子超过 2/3 时，将哈希表扩容至原先的 2 倍。

# 当链表很长时，查询效率 𝑂(𝑛) 很差。此时可以将链表转换为AVL 树 或红黑树 ，从而将查询操作的时间复杂度优化至 𝑂(log 𝑛) 。

2.开放寻址

• 开放寻址 （open addressing）不引入额外的数据结构，而是通过多次探测 来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等。
• 开放 ：即是所有键值对都存储在数组内，而不是数组元素对应的链表
• 寻址 ：哈希冲突时，按照预定规则，寻址下一个可用的空位置

1.线性探测

• 采用固定步长的线性搜索来探测

• 其操作方法与普通哈希表有所不同

  • 插入元素 ：通过哈希函数计算桶索引，若发现桶内已有元素（即发生哈希冲突），则从冲突位置向后线性遍历，步长通常为1 ，直至找到空桶，将元素插入其中。
    • 所以其插入的一定是第一个空桶，所以下面查找时，遇到第一个空桶，即元素不在表中
    • 因此也导致下面的聚集问题
  • 查找元素 ：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。
    • 元素查找时，如果不在其初始的位置，那么就是发生了哈希冲突导致其插入时向后找可用的第一个空桶，查找时是从初始位置开始一直到第一个空桶，因为元素只有可能在这个区间内（直接删除元素的情况除外）

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

• 不能在开放寻址哈希表中直接删除元素。这是因为删除元素会在数组内产生一个空桶None ，而当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在

• 为了解决该问题，可以采用懒删除 （lazy deletion）机制：它不直接从哈希表中移除元素，而是利用一个常量 Tombstone/Deleted来标记这个桶。在该机制下，None和Tombstone/Deleted都代表空桶，都可以放置键值对。但不同的是，线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。

• 但是，懒删除可能会加速哈希表的性能退化 。这是因为每次删除操作都会产生一个删除标记，随着 Tombstone/Deleted的增加，搜索时间也会增加，因为线性探测可能需要跳过多个Tombstone/Deleted才能找到目标元素。

• 在线性探测中记录遇到的首个Tombstone/Deleted的索引，并将搜索到的目标元素与该Tombstone/Deleted交换位置 。这样做的好处是当每次查询或添加元素时，元素会被移动至距离理想位置（探测起始点）更近的桶 ，从而优化查询效率。

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

    def __init__(self):
        """ 构造方法"""
        self.size = 0 # 键值对数量
        self.capacity = 4 # 哈希表容量
        self.load_thres = 2.0 / 3.0 # 触发扩容的负载因子阈值
        self.extend_ratio = 2 # 扩容倍数
        self.buckets: list[Pair | None] = [None] * self.capacity # 桶数组
        self.TOMBSTONE = 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 find_bucket(self, key: int) -> int:        
        """ 搜索 key 对应的桶索引"""
        index = self.hash_func(key)
        first_tombstone = -1
        # 线性探测，当遇到空桶时跳出
        while self.buckets[index] is not None:
            # 若遇到 key ，返回对应的桶索引
            if self.buckets[index].key == key:
                # 若之前遇到了删除标记，则将键值对移动至该索引处
                if first_tombstone != -1:
                    self.buckets[first_tombstone] = self.buckets[index]
                    self.buckets[index] = self.TOMBSTONE
                    return first_tombstone # 返回移动后的桶索引
                return index # 返回桶索引
            # 记录遇到的首个删除标记
            if first_tombstone == -1 and self.buckets[index] is self.TOMBSTONE:
                first_tombstone = index
                # 计算桶索引，越过尾部则返回头部
                index = (index + 1) % self.capacity
			# 若 key 不存在，则返回添加点的索引
            return index if first_tombstone == -1 else first_tombstone

        def get(self, key: int) -> str:
            """ 查询操作"""
   		    # 搜索 key 对应的桶索引
            index = self.find_bucket(key)
            # 若找到键值对，则返回对应 val
            if self.buckets[index] not in [None, self.TOMBSTONE]:
                return self.buckets[index].val
            # 若键值对不存在，则返回 None
            return None
        
        def put(self, key: int, val: str):
            """ 添加操作"""
            # 当负载因子超过阈值时，执行扩容
            if self.load_factor() > self.load_thres:
                self.extend()
            # 搜索 key 对应的桶索引
   	        index = self.find_bucket(key)
            # 若找到键值对，则覆盖 val 并返回
            if self.buckets[index] not in [None, self.TOMBSTONE]:
                self.buckets[index].val = val
                return
            # 若键值对不存在，则添加该键值对
            self.buckets[index] = Pair(key, val)
            self.size += 1
 
	def remove(self, key: int):
        """ 删除操作"""
        # 搜索 key 对应的桶索引
        index = self.find_bucket(key)
        # 若找到键值对，则用删除标记覆盖它
        if self.buckets[index] not in [None, self.TOMBSTONE]:
            self.buckets[index] = self.TOMBSTONE
            self.size -= 1
          
	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.TOMBSTONE]:
                self.put(pair.key, pair.val)
                
	def print(self):
        """ 打印哈希表"""
        for pair in self.buckets:
            if pair is None:
                print("None")
            elif pair is self.TOMBSTONE:
                print("TOMBSTONE")
            else:
                print(pair.key, "->", pair.val)

# 为了更加充分地使用哈希表的空间，将哈希表看作一个环形数组 ，当越过数组尾部时，回到头部继续遍历。

2.平方探测

• 与线性探测类似，发生冲突时，会跳过探测次数的平方 的步数，即 1, 4, 9, … 步

• 平方探测主要具有以下优势：

  • 平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应 。
  • 平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀 。

• 同样也有局限性：

  • 仍然存在聚集现象，即某些位置比其他位置更容易被占用。

  • 由于平方的增长，平方探测可能不会探测整个哈希表 ，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它。

  • 同样不能直接删除元素

3.多次哈希

• 多次哈希方法使用多个哈希函数 𝑓1(𝑥)、𝑓2(𝑥)、𝑓3(𝑥)、… 进行探测

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

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

• 同样不能直接删除元素

3.编程语言的选择

• 各种编程语言采取了不同的哈希表实现策略
  • Python 采用开放寻址 。字典 dict 使用伪随机数 进行探测。
  • Java 采用链式地址 。自 JDK 1.8 以来，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会转换为红黑树 以提升查找性能。
  • Go 采用链式地址 。Go规定每个桶最多存储 8 个键值对，超出容量则连接一个溢出桶；当溢出桶过多时，会执行一次特殊的等量扩容操作 ，以确保性能。

3.哈希算法

• 无论是开放寻址还是链式地址，它们只能保证哈希表可以在发生冲突时正常工作，而无法减少哈希冲突的发生

• 如果哈希冲突过于频繁，哈希表的性能则会急剧劣化

• 键值对的分布情况由哈希函数决定

• index = hash(key) % capacity

• 当哈希表容量 capacity 固定时，哈希算法 hash() 决定了输出值

• 所以要降低哈希冲突的概率，就要集中于哈希算法的设计

1.哈希算法的目标

• 为了实现既快 又稳 的哈希表数据结构，哈希算法应具备以下特点。

  • 确定性 ：对于相同的输入 ，哈希算法应始终产生相同的输出 。这样才能确保哈希表是可靠的。
  • 效率高 ：计算哈希值的过程应该足够快 。计算开销越小，哈希表的实用性越高 。
  • 均匀分布 ：哈希算法应使得键值对均匀分布 在哈希表中。分布越均匀，哈希冲突的概率就越低 。

• 在其他领域中也有广泛应用

  • 密码存储 ：为了保护用户密码的安全，系统通常不会直接存储用户的明文密码，而是存储密码的哈希值。当用户输入密码时，系统会对输入的密码计算哈希值 ，然后与存储的哈希值进行比较 。如果两者匹配，那么密码就被视为正确。
  • 数据完整性检查 ：数据发送方可以计算数据的哈希值 并将其一同发送；接收方可以重新计算接收到的数据的哈希值 ，并与接收到的哈希值进行比较 。如果两者匹配 ，那么数据就被视为完整。

• 在密码学 中，为了防止从哈希值推导出原始密码等逆向工程，哈希算法需要具备更高等级的安全特性

  • 单向性 ：无法通过哈希值反推出关于输入数据的任何信息。
  • 抗碰撞性 ：应当极难 找到两个不同的输入，使得它们的哈希值相同。即哈希冲突（哈希碰撞）

  # 这里不完全等同于均匀分布，均匀分布是均匀导致哈希冲突概率低，但是哈希算法可以较为简单，可以被简单的反推出来，而抗碰撞性是通过计算复杂度使其极难发生哈希冲突

  # 哈希冲突就像是“世界上存在两片一模一样的雪花”。我们知道理论上可能存在，但几乎没人见过。

  # 抗碰撞性就是“制造一台机器，让它能故意造出两片一模一样的雪花”。密码学哈希函数的设计目标就是，让造出这台机器的难度高到令人绝望。

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

2.哈希算法的设计

• 对于某些要求不高的场景，可以设计一些简单的哈希算法。
• 加法哈希 ：对输入的每个字符的ASCII码 进行相加，将得到的总和作为哈希值

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

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

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

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

def rot_hash(key: str) -> int:
    """ 旋转哈希"""
    hash = 0
    modulus = 1000000007
    for c in key:
        hash = (hash << 4) ^ (hash >> 28) ^ ord(c)
    return hash % modulus

• 这些算法的最后都是对大质数1000000007取模，可以确保哈希值在合适的范围内
• 因为质数不存在公约数，减少出现取模产生的周期性模式，最大程度的保证哈希值均匀分布，避免聚集现象的出现，避免哈希冲突

3.常见哈希算法

• 以上算法都比较简单
• 实际中会采用一些标准哈希算法

	MD5	SHA-1	SHA-2	SHA-3
推出时间	1992	1995	2002	2008
输出长度	128 bit	160 bit	256/512 bit	224/256/384/512 bit
哈希冲突	较多	较多	很少	很少
安全等级	低，已被成功攻击	低，已被成功攻击	高	高
应用	已被弃用，仍用于数据完整性检查	已被弃用	加密货币交易验证、数字签名等	可用于替代 SHA‑2

• SHA‑2 系列中的 SHA‑256 是最安全的哈希算法之一，仍未出现成功的攻击案例，因此常用在各类安全应用与协议中。
• SHA‑3 相较 SHA‑2 的实现开销更低、计算效率更高，但目前使用覆盖度不如 SHA‑2 系列。

4.数据结构的哈希值

• 编程语言中通常会为数据类型提供内置的哈希算法

• 在python中，调用hash()来计算各种数据类型的哈希值

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

  num = 3
  hash_num = hash(num)
  # 整数 3 的哈希值为 3
  
  bol = True
  hash_bol = hash(bol)
  # 布尔量 True 的哈希值为 1

  • 浮点数 和字符串 的哈希值计算较为复杂

  dec = 3.14159
  hash_dec = hash(dec)
  # 小数 3.14159 的哈希值为 326484311674566659
  
  str = "Hello 算法"
  hash_str = hash(str)
  # 字符串“Hello 算法”的哈希值为 4617003410720528961

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

  tup = (12836, " 小哈")
  hash_tup = hash(tup)
  # 元组 (12836, '小哈') 的哈希值为 1029005403108185979

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

  obj = ListNode(0)
  hash_obj = hash(obj)
  # 节点对象 <ListNode object at 0x1058fd810> 的哈希值为 274267521

# 不同编程语言的内置哈希值计算函数的定义和方法不同

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

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

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

7.树

1.二叉树

• 二叉树 （binary tree）是一种非线性 数据结构，代表祖先 与后代 之间的派生关系 ，体现了一分为二

  的分治逻辑。与链表类似，二叉树的基本单元是节点 ，每个节点包含值 、左子节点引用 和右子节点引用 。

/* 二叉树节点结构体 */
typedef struct TreeNode {
    int val; // 节点值
    int height; // 节点高度
    struct TreeNode *left; // 左子节点指针
    struct TreeNode *right; // 右子节点指针
} TreeNode;

/* 构造函数 */
TreeNode *newTreeNode(int val) {
    TreeNode *node;
    
    node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

flowchart TD
	1["1
	(2和3的父节点)"] --> 2["2
	(左子节点)"]
	1 --> 3["3
	(右子节点)"]
	subgraph 右子树
	3 --> 6
	3 --> 7
	end
	subgraph 左子树
	2 --> 4
	2 --> 5
	end

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

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

1.二叉树常见术语

• 根节点 （root node）：位于二叉树顶层的节点，没有父节点 。
• 叶节点 （leaf node）：没有子节点 的节点，其两个指针均指向None 。
• 边 （edge）：连接两个节点的线段 ，即节点引用 （指针）。
• 节点所在的层 （level）：从顶至底 递增，根节点 所在层为1 。
• 节点的度 （degree）：节点的子节点的数量 。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度 （height）：从根节点 到最远叶节点 所经过的边的数量 。
• 节点的深度 （depth）：从根节点 到该节点 所经过的边的数量 。
• 节点的高度 （height）：从距离该节点最远的叶节点 到该节点 所经过的边的数量 。

flowchart TB
	subgraph 高度为3的二叉树
	direction TB
	1["1
	(根节点)
	(层为1)
	(度为2)
	(深度为0)
	(高度为3)"] --边--> 2["2
	(层为2)
	(度为2)
	(深度为1)
	(高度为2)"]
	1 --边--> 3["3
	(层为2)
	(度为2)
	(深度为1)
	(高度为2)"]
	3 --边--> 6["6
	(层为3)
	(度为1)
	(深度为2)
	(高度为1)"]
	3 --边--> 7["7
	(层为3)
	(度为2)
	(深度为2)
	(高度为1)"]
	2 --边--> 4["4
	(层为3)
	(度为2)
	(深度为2)
	(高度为1)"]
    2 --边--> 5["5
    (叶节点)
    (层为3)
    (度为0)
    (深度为2)
    (高度为1)"]
    4 --边--> 8["8
    (叶节点)
    (层为4)
    (度为0)
    (深度为3)
    (高度为0)"]
    4 --边--> 9["9
    (叶节点)
    (层为4)
    (度为0)
    (深度为3)
    (高度为0)"]
    6 --边--> 12["12
    (叶节点)
    (层为4)
    (度为0)
    (深度为3)
    (高度为0)"]
    7 --边--> 14["14
    (叶节点)
    (层为4)
    (度为0)
    (深度为3)
    (高度为0)"]
    7 --边--> 15["15
    (叶节点)
    (层为4)
    (度为0)
    (深度为3)
    (高度为0)"]   
    end

2.二叉树基本操作

1.初始化二叉树

• 与链表相似，先初始化节点，然后构建引用

/* 初始化二叉树 */
// 初始化节点
TreeNode *n1 = newTreeNode(1);
TreeNode *n2 = newTreeNode(2);
TreeNode *n3 = newTreeNode(3);
TreeNode *n4 = newTreeNode(4);
TreeNode *n5 = newTreeNode(5);
// 构建节点之间的引用（指针）
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

2.插入与删除节点

• 与链表相似，都是修改指针

flowchart LR
    
    subgraph 插入后二叉树
    direction TB
    1'["1
    (n1)"] --> 0
	1' --> 3'[3]
	0["0
	(p)"] --> 2'["2
	(n2)"]
    2' --> 4'[4]
    2' --> 5'[5]
    end
    
    subgraph 原二叉树
	direction TB
	1["1
	(n1)"] --> 2["2
	(n2)"]
	1 --> 3
	2 --> 4
    2 --> 5
    0'["0
	(p)"]
    end
    
    subgraph 删除后二叉树
	direction TB
	1''["1
	(n1)"] --> 2''["2
	(n2)"]
	1'' --> 3''[3]
	2'' --> 4''[4]
    2'' --> 5''[5]
    end
    
    
    
    原二叉树 --n1.left = p
    p.left = n2--> 插入后二叉树
    
    插入后二叉树 --n1.left = n2--> 删除后二叉树

/* 插入与删除节点 */
TreeNode *P = newTreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1->left = P;
P->left = n2;
// 删除节点 P
n1->left = n2;

# 原有的引用不删除，只将插入的节点删除，所以删除后就是原二叉树，如果将原有引用删除后又删除插入的节点则就是删除了整个左子树

3.常见二叉树类型

1.完美二叉树(满二叉树)

• 完美二叉树 （perfect binary tree）所有层的节点都被完全填满。在完美二叉树中，叶节点的度 为 0 ，其余所有节点的度都为 2 ；若树的高度为 ℎ ，则节点总数为 $2^{ℎ+1} − 1$ ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象

flowchart TD
	1 --> 2
	1 --> 3
	3 --> 6
	3 --> 7
	2 --> 4
	2 --> 5
	4 --> 8
	4 --> 9
	5 --> 10
	5 --> 11
	6 --> 12
	6 --> 13
	7 --> 14
	7 --> 15

2.完全二叉树

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

# 完美二叉树也是一棵完全二叉树。

flowchart TD
	1 --> 2
	1 --> 3
	3 --> 6
	3 --> 7
	2 --> 4
	2 --> 5
	4 --> 8
	4 --> 9
	5 --> 10
	5 --> 11
	6 --> 12

3.完满二叉树

• 完满二叉树 （full binary tree）除了叶节点之外，其余所有节点都有两个子节点
• 即所有节点的度都为0或2

flowchart TD
	1 --> 2
	1 --> 3
	2 --> 4
	2 --> 5
	5 --> 10
	5 --> 11

4.平衡二叉树

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

flowchart TD
	1 --> 2
	1 --> 3
	3 --> 6
	2 --> 4
	2 --> 5
	5 --> 10
	5 --> 11

4.二叉树的退化

• 二叉树的理想结构就是满二叉树
• 当所有节点都偏向一侧时，二叉树就退化为链表

flowchart LR
	subgraph 满二叉树
	1 --> 2
	1 --> 3
	3 --> 6
	3 --> 7
	2 --> 4
	2 --> 5
	end
	
	subgraph 链表
	1'[1] --> 2'[2]
	2' --> 3'[3]
	3' --> 4'[4]
	4' --> 5'[5]
	5' --> 6'[6]
	6' --> 7'[7]
	end
	
	满二叉树 --退化--> 链表

• 在最佳结构 和最差结构 下，二叉树的叶节点数量、节点总数、高度等达到极大值 或极小值

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

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

	完美二叉树	链表
第i层的节点数量	$2^{i-1}$	1
高度为h的树的叶节点数量	$2^h$	1
高度为h的树的节点总数	$2^{h+1}$	h+1
节点总数为n的树的高度	$\log_2(n+1)-1$	n-1

2.二叉树遍历

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

1.层序遍历

• 层序遍历 （level‑order traversal）从顶部到底部逐层 遍历二叉树，并在每一层按照从左到右 的顺序访问节点

• 层序遍历本质上属于广度优先 遍历（breadth‑first traversal），也称广度优先搜索 （breadth‑first search,BFS）

1.代码实现

• 借助队列来实现，队列的先进先出 和广度优先的逐层推进 是一致的

/* 层序遍历 */
int *levelOrder(TreeNode *root, int *size) {
    /* 辅助队列 */
    int front, rear;
    int index, *arr;
    TreeNode *node;
    TreeNode **queue;
    
    /* 辅助队列 */
    queue = (TreeNode **)malloc(sizeof(TreeNode *) * MAX_SIZE);
    // 队列指针
    front = 0, rear = 0;
    // 加入根节点
    queue[rear++] = root;
    // 初始化一个列表，用于保存遍历序列
    /* 辅助数组 */
    arr = (int *)malloc(sizeof(int) * MAX_SIZE);
    // 数组指针
    index = 0;
    while (front < rear) {
        // 队列出队
        node = queue[front++];
        // 保存节点值
        arr[index++] = node->val;
        if (node->left != NULL) {
            // 左子节点入队
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            // 右子节点入队
            queue[rear++] = node->right;
        }
    }
    // 更新数组长度的值
    *size = index;
    arr = realloc(arr, sizeof(int) * (*size));
    
    // 释放辅助数组空间
    free(queue);
    return arr;
}

2.复杂度分析

• 时间复杂度为 𝑂(𝑛) ：所有节点被访问一次，使用 𝑂(𝑛) 时间，其中 𝑛 为节点数量。
• 空间复杂度为 𝑂(𝑛) ：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在(𝑛 + 1)/2 个节点，占用 𝑂(𝑛) 空间。

2.前序，中序，后序遍历

• 前序、中序和后序遍历 都属于深度优先 遍历（depth‑first traversal），也称深度优先 搜索（depth‑first search, DFS）

• 规定D，L，R分别代表根节点，左子树，右子树

  • DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
    • 1（D）-[2（4，5的D）-4（2的L）-5（2的R）]（L）-[3（6，7的D）-6（3的L）-7（3的R）]（R）
  • LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
    • [4（2的L）-2（4，5的D）-5（2的R）]（L）-1（D）-[6（3的L）-3（6，7的D）-7（3的R）]（R）
  • LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）
    • [4（2的L）-5（2的R）-2（4，5的D）]（L）-[6（3的L）-7（3的R）-3（6，7的D）]（R）-1（D）

# 每个根都是相对的

flowchart TB
	subgraph D
	1
	end
	1 --> L
	1 --> R
	subgraph R
	direction TB
	3 --> L''
	3 --> R''
	subgraph D'[D]
	3
	end
	subgraph L''[L]
	6
	end
	subgraph R''[R]
	7
	end
	end
	subgraph L
	direction TB
	2 --> L'
	2 --> R'
	subgraph D''[D]
	2
	end
	subgraph L'[L]
	4
	end
	subgraph R'[R]
	5
	end
	end

1.代码实现

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

/* 前序遍历 */
void preOrder(TreeNode *root, int *size) {
    if (root == NULL)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    arr[(*size)++] = root->val;
    preOrder(root->left, size);
    preOrder(root->right, size);
}

/* 中序遍历 */
void inOrder(TreeNode *root, int *size) {
    if (root == NULL)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root->left, size);
    arr[(*size)++] = root->val;
    inOrder(root->right, size);
}

/* 后序遍历 */
void postOrder(TreeNode *root, int *size) {
    if (root == NULL)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root->left, size);
    postOrder(root->right, size);
    arr[(*size)++] = root->val;
}

# 也可以基于迭代来实现

• 可以分为两个部分
  • 递 表示开启新方法，程序在此过程中访问下一个节点。
  • 归 表示函数返回，代表当前节点已经访问完毕

# 以前序遍历为例

1（递）-2（递）-4（递）-[2（归）]-5（递）-[2（归）]-[1（归）]-3（递）-6（递）-[3（归）]-7（递）-[3（归）]-[1（归）]

2.复杂度分析

• 时间复杂度为 𝑂(𝑛) ：所有节点被访问一次，使用 𝑂(𝑛) 时间。
• 空间复杂度为 𝑂(𝑛) ：在最差情况下，即树退化为链表时，递归深度达到 𝑛 ，系统占用 𝑂(𝑛) 栈帧空间。

3.二叉树数组表示

1.表示完美二叉树

• 按照层序遍历的顺序作为索引，即从每一层从左到右
• 根据层序遍历的特性，可以推导出父节点索引 与子节点索引 之间的映射公式 ：若某节点的索引为𝑖 ，则该节点的左子节点索引为2𝑖 + 1，右子节点索引为2𝑖 + 2 。
  • 这个公式就相当于是链表里的指针，给定节点索引就可以访问其左右子节点

2.表示任意二叉树

• 一般的二叉树中会有许多none，所以在写数组的时候就把none的地方直接标记出来

// 使用 int 最大值标记空位，因此要求节点值不能为 INT_MAX
int tree[] = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};

# 完全二叉树 非常适合使用数组来表示。None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾 ，可以省略存储所有 None

/* 数组表示下的二叉树结构体 */
typedef struct {
    int *tree;
    int size;
} ArrayBinaryTree;

/* 构造函数 */
ArrayBinaryTree *newArrayBinaryTree(int *arr, int arrSize) {
    ArrayBinaryTree *abt = (ArrayBinaryTree *)malloc(sizeof(ArrayBinaryTree));
    abt->tree = malloc(sizeof(int) * arrSize);
    memcpy(abt->tree, arr, sizeof(int) * arrSize);
    abt->size = arrSize;
    return abt;
}

/* 析构函数 */
void delArrayBinaryTree(ArrayBinaryTree *abt) {
    free(abt->tree);
    free(abt);
}

/* 列表容量 */
int size(ArrayBinaryTree *abt) {
    return abt->size;
}

/* 获取索引为 i 节点的值 */
int val(ArrayBinaryTree *abt, int i) {
    // 若索引越界，则返回 INT_MAX ，代表空位
    if (i < 0 || i >= size(abt))
        return INT_MAX;
    return abt->tree[i];
}

/* 层序遍历 */
int *levelOrder(ArrayBinaryTree *abt, int *returnSize) {
    int *res = (int *)malloc(sizeof(int) * size(abt));
    int index = 0;
    // 直接遍历数组
    for (int i = 0; i < size(abt); i++) {
        if (val(abt, i) != INT_MAX)
            res[index++] = val(abt, i);
    }
    *returnSize = index;
    return res;
}

/* 深度优先遍历 */
void dfs(ArrayBinaryTree *abt, int i, char *order, int *res, int *index) {
    // 若为空位，则返回
    if (val(abt, i) == INT_MAX)
        return;
    // 前序遍历
    if (strcmp(order, "pre") == 0)
        res[(*index)++] = val(abt, i);
    dfs(abt, left(i), order, res, index);
    // 中序遍历
    if (strcmp(order, "in") == 0)
        res[(*index)++] = val(abt, i);
    dfs(abt, right(i), order, res, index);
    // 后序遍历
    if (strcmp(order, "post") == 0)
        res[(*index)++] = val(abt, i);
}

/* 前序遍历 */
int *preOrder(ArrayBinaryTree *abt, int *returnSize) {
    int *res = (int *)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "pre", res, &index);
    *returnSize = index;
    return res;
}

/* 中序遍历 */
int *inOrder(ArrayBinaryTree *abt, int *returnSize) {
    int *res = (int *)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "in", res, &index);
    *returnSize = index;
    return res;
}

/* 后序遍历 */
int *postOrder(ArrayBinaryTree *abt, int *returnSize) {
    int *res = (int *)malloc(sizeof(int) * size(abt));
    int index = 0;
    dfs(abt, 0, "post", res, &index);
    *returnSize = index;
    return res;
}

• 可以实现

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

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

3.优点与局限性

• 优点
  • 数组存储在连续的内存空间 中，对缓存友好 ，访问与遍历速度较快 。
  • 不需要存储指针 ，比较节省空间 。
  • 允许随机访问节点 。
• 局限性
  • 数组存储需要连续内存空间 ，因此不适合存储数据量过大 的树。
  • 增删节点 需要通过数组插入与删除操作实现，效率较低 。
  • 当二叉树中存在大量 None 时 ，数组中包含的节点数据比重较低 ，空间利用率较低 。

4.二叉搜索树

• 二叉搜索树 （binary search tree）满足以下条件
  • 对于根节点，左子树 中所有节点的值 < 根节点的值 < 右子树 中所有节点的值 。
  • 任意节点 的左、右子树也是二叉搜索树 ，即同样满足上一个条件 。

1.二叉搜索树的操作

• 将二叉搜索树封装为一个类 BinarySearchTree ，并声明一个成员变量 root ，指向树的根节点

1.查找操作

• 给定目标节点值 num ，可以根据二叉搜索树的性质来查找。声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。
  • 若 cur.val < num ，说明目标节点在 cur 的右子树 中，因此执行 cur = cur.right 。
  • 若 cur.val > num ，说明目标节点在 cur 的左子树 中，因此执行 cur = cur.left 。
  • 若 cur.val = num ，说明找到目标节点 ，跳出循环并返回该节点。
• 二叉搜索树的查找操作与二分查找算法 的工作原理一致，都是每轮排除一半 情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用 𝑂(log 𝑛) 时间。

/* 查找节点 */
TreeNode *search(BinarySearchTree *bst, int num) {
    TreeNode *cur = bst->root;
    // 循环查找，越过叶节点后跳出
    while (cur != NULL) {
        if (cur->val < num) {
            // 目标节点在 cur 的右子树中
            cur = cur->right;
        } else if (cur->val > num) {
            // 目标节点在 cur 的左子树中
            cur = cur->left;
        } else {
            // 找到目标节点，跳出循环
            break;
        }
    }
    // 返回目标节点
    return cur;
}

2.插入节点

• 插入元素时需要保证二叉搜索树左子树 < 根节点 < 右子树 的性质，流程如下

  • 查找插入位置 ：与查找操作相似 ，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出循环。

  • 在该位置插入节点 ：初始化节点 num ，将该节点置于 None 的位置。

  # 因此与查找节点相同，插入节点使用 𝑂(log 𝑛) 时间

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

• 为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点 。这样在遍历至 None 时，我们可以获取到其父节点 ，从而完成节点插入操作。

/* 插入节点 */
void insert(BinarySearchTree *bst, int num) {
    // 若树为空，则初始化根节点
    if (bst->root == NULL) {
        bst->root = newTreeNode(num);
        return;
    }
    TreeNode *cur = bst->root, *pre = NULL;
    // 循环查找，越过叶节点后跳出
    while (cur != NULL) {
        // 找到重复节点，直接返回
        if (cur->val == num) {
            return;
        }
        pre = cur;
        if (cur->val < num) {
            // 插入位置在 cur 的右子树中
            cur = cur->right;
        } else {
            // 插入位置在 cur 的左子树中
            cur = cur->left;
        }
    }
    // 插入节点
    TreeNode *node = newTreeNode(num);
    if (pre->val < num) {
        pre->right = node;
    } else {
        pre->left = node;
    }
}

flowchart LR
	subgraph 插入后二叉树
	subgraph A[在None的位置插入节点执行pre.right = 8]
	direction TB
	4'[4] --> 2'[2]
	4' --> 6'[6]
	6' --> 5'[5]
	6' --> 7'[7]
	2' --> 1'[1]
	2' --> 3'[3]
	3' --> 8'[8]
	end
	end

	subgraph 原二叉树
	subgraph 查找节点插入位置
	direction TB
	4 --> 2
	4 --> 6
	6 --> 5
	6 --> 7
	2 --> 1
	2 --> 3
	7 --> None
	end
	end
	
	原二叉树 --插入节点8--> 插入后二叉树

3.删除节点

• 首先查找相应节点，为了保证删除后仍满足左子树 < 根节点 < 右子树 的性质，将要删除的节点的位置分为三种

  • 度为0，即叶节点，直接删除

  flowchart LR
  	subgraph 删除后二叉树
  	subgraph A[直接删除cur即可，执行pre.left = None]
  	direction TB
  	4'[4] --> 2'[2]
  	4' --> 6'[6]
  	2' --> 3'[3]
  	6' --> 5'[5]
  	6' --> 7'[7]
  	end
  	end
  
  	subgraph 原二叉树
  	subgraph 查找要删除元素的位置
  	direction TB
  	4 --> 2
  	4 --> 6
  	6 --> 5
  	6 --> 7
  	2 --> 1["1
  	(节点cur，子节点的个数为0)"]
  	2 --> 3
  	end
  	end
  	
  	原二叉树 --删除节点1--> 删除后二叉树

  • 度为1，将要删除的节点换位其子节点即可

  flowchart LR
  	subgraph 删除后二叉树
  	subgraph A[将删除节点替换为其子节点，执行pre.left = pre.right]
  	direction TB
  	4'[4] --> 3'[3]
  	4' --> 6'[6]
  	6' --> 5'[5]
  	6' --> 7'[7]
  	end
  	end
  
  	subgraph 原二叉树
  	subgraph 查找要删除元素的位置
  	direction TB
  	4 --> 2
  	4 --> 6
  	6 --> 5
  	6 --> 7
  	2 --> 3["3
  	(节点cur，子节点的个数为1)"]
  	end
  	end
  	
  	原二叉树 --删除节点3--> 删除后二叉树

  • 度为2，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树左子树 < 根节点 < 右子树 的性质，因此这个节点可以是右子树的最小节点（中序遍历该删除节点的下一个节点）或左子树的最大节点（中序遍历该删除节点的上一个节点） 。

    • 先用中序遍历找到要删除节点的下一个（右子树的最小节点）或上一个（左子树的最大节点），记为tmp

    flowchart LR
    
    	subgraph 查找中序遍历的后继节点nex
    	8'[8] --> 4'["4
    	(节点cur，子节点的个数为2)"]
    	8' --> 12'[12]
    	4' --> 3'[3]
    	4' --> 6'[6]
    	6' --> 5'["5
    	(cur在中序遍历中的后继节点nex)"]
    	6' --> 7'[7]
    	12' --> 10'[10]
    	12' --> 14'[14]
    	10' --> 9'[9]
    	10' --> 11'[11]
    	14' --> 13'[13]
    	14' --> 15'[15]
    	end
    	
    	subgraph 原二叉树
    	8 --> 4["4
    	(节点cur，子节点的个数为2)"]
    	8 --> 12
    	4 --> 3
    	4 --> 6
    	6 --> 7
    	6 --> 5
    	12 --> 10
    	12 --> 14
    	10 --> 9
    	10 --> 11
    	14 --> 13
    	14 --> 15
    	end
    	
    
    	原二叉树 --> 查找中序遍历的后继节点nex

    • 删除tmp，然后将要删除的节点替换为tmp

    flowchart LR
    	subgraph 将节点nex的值赋给cur
    	8'''[8] --> 5'''[5]
    	8''' --> 12'''[12]
    	5''' --> 3'''[3]
    	5''' --> 6'''
    	6'''[6] --> 7'''[7]
    	12''' --> 10'''[10]
    	12''' --> 14'''[14]
    	10''' --> 9'''[9]
    	10''' --> 11'''[11]
    	14''' --> 13'''[13]
    	14''' --> 15'''[15]
    	end
    
    	subgraph 删除nex
    	8''[8] --> 4''["4
    	(节点cur，子节点的个数为2)"]
    	8'' --> 12''[12]
    	4'' --> 3''[3]
    	4'' --> 6''[6]
    	6'' --> 7''[7]
    	12'' --> 10''[10]
    	12'' --> 14''[14]
    	10'' --> 9''[9]
    	10'' --> 11''[11]
    	14'' --> 13''[13]
    	14'' --> 15''[15]
    	end
    	
    	删除nex --> 将节点nex的值赋给cur

  # 因为与查找类似，所以删除节点操作同样使用 𝑂(log 𝑛) 时间，其中查找待删除节点需要 𝑂(log 𝑛) 时间，获取中序遍历后继节点需要 𝑂(log 𝑛) 时间

/* 删除节点 */
// 由于引入了 stdio.h ，此处无法使用 remove 关键词
void removeItem(BinarySearchTree *bst, int num) {
    // 若树为空，直接提前返回
    if (bst->root == NULL)
        return;
    TreeNode *cur = bst->root, *pre = NULL;
    // 循环查找，越过叶节点后跳出
    while (cur != NULL) {
        // 找到待删除节点，跳出循环
        if (cur->val == num)
            break;
        pre = cur;
        if (cur->val < num) {
            // 待删除节点在 root 的右子树中
            cur = cur->right;
        } else {
            // 待删除节点在 root 的左子树中
            cur = cur->left;
        }
    }
    // 若无待删除节点，则直接返回
    if (cur == NULL)
        return;
    // 判断待删除节点是否存在子节点
    if (cur->left == NULL || cur->right == NULL) {
        /* 子节点数量 = 0 or 1 */
        // 当子节点数量 = 0 / 1 时， child = nullptr / 该子节点
        TreeNode *child = cur->left != NULL ? cur->left : cur->right;
        // 删除节点 cur
        if (pre->left == cur) {
            pre->left = child;
        } else {
            pre->right = child;
        }
        // 释放内存
        free(cur);
    } else {
        /* 子节点数量 = 2 */
        // 获取中序遍历中 cur 的下一个节点
        TreeNode *tmp = cur->right;
        while (tmp->left != NULL) {
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        // 递归删除节点 tmp
        removeItem(bst, tmp->val);
        // 用 tmp 覆盖 cur
        cur->val = tmpVal;
    }
}

4.中序遍历有序

• 中序遍历遵循LDR ，且二叉搜索树满足左子节点<根节点<右子节点
• 所以二叉搜索树中进行中序遍历时，总是会优先遍历下一个最小节点，从而得出一个重要性质：
• 二叉搜索树的中序遍历序列是升序的 。
• 利用中序遍历升序的性质，在二叉搜索树中获取有序数据仅需 𝑂(𝑛) 时间，无须进行额外的排序操作

2.二叉搜索树的效率

	无序数组	二叉搜索树
查找元素	𝑂(𝑛)	𝑂(log 𝑛)
插入元素	𝑂(1)	𝑂(log 𝑛)
删除元素	𝑂(𝑛)	𝑂(log 𝑛)

• 二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定 且高效 的性能。
• 只有在高频添加 、低频查找删除数据 的场景下，数组比二叉搜索树的效率更高。

# 理想状态下的二叉树是平衡的，此时可以在 log 𝑛 轮循环内查找任意节点

# 但在使用后可能会退化为链表，此时各操作的时间复杂度也会退化为 𝑂(𝑛) 。

3.二叉搜索树常见应用

• 用作系统中的多级索引，实现高效的查找、插入、删除操作。
• 作为某些搜索算法的底层数据结构。
• 用于存储数据流，以保持其有序状态。

5.AVL树

• 二叉搜索树在多次删除和插入后都会严重退化

flowchart LR

	subgraph 链表
	4''[4] --> 2''[2]
	2'' --> 1''[1]
	end
	
	subgraph 普通二叉树
	4'[4] --> 2'[2]
	2' --> 1'[1]
	2' --> 3'[3]
	end
	
	subgraph 平衡二叉树
	4[4] --> 2[2]
	4 --> 5[5]
	2 --> 1[1]
	2 --> 3[3]
	end
	
	平衡二叉树 --删除节点5--> 普通二叉树
	普通二叉树 --删除节点3--> 链表

flowchart LR
	subgraph 普通二叉树
	4''[4] --> 3''[3]
	4'' --> 5''[5]
	3'' --> 2''[2]
	2'' --> 1''[1]
	end


	subgraph 平衡二叉树
	4'[4] --> 3'[3]
	4' --> 5'[5]
	3' --> 2'[2]
	end
	

	subgraph 完美二叉树
	4[4] --> 3[3]
	4 --> 5[5]
	end
	
	完美二叉树 --插入节点2--> 平衡二叉树
	平衡二叉树 --插入节点1--> 普通二叉树

• 1962 年 G. M. Adelson‑Velsky 和 E. M. Landis 在 论 文 “An algorithm for the organization of information”中提出了 AVL 树 。论文中详细描述了一系列操作，确保在持续添加和删除节点后 ，AVL 树不会退化，从而使得各种操作的时间复杂度保持在 𝑂(log 𝑛) 级别 。

1.AVL树常见术语

• AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树 （balanced binary search tree）

1.节点高度

• 由于 AVL 树的相关操作需要获取节点高度，因此需要为节点类添加 height 变量

/* AVL 树节点结构体 */
typedef struct TreeNode {
    int val;
    int height;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

/* 构造函数 */
TreeNode *newTreeNode(int val) {
    TreeNode *node;
    
    node = (TreeNode *)malloc(sizeof(TreeNode));
    node->val = val;
    node->height = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

• 节点高度：该节点到它的最远叶节点的距离，即所经过的边 的数量

# 叶节点的高度为0

# 空节点的高度为-1

/* 获取节点高度 */
int height(TreeNode *node) {
    // 空节点高度为 -1 ，叶节点高度为 0
    if (node != NULL) {
        return node->height;
    }
    return -1;
}

/* 更新节点高度 */
void updateHeight(TreeNode *node) {
    int lh = height(node->left);
    int rh = height(node->right);
    // 节点高度等于最高子树高度 + 1
    if (lh > rh) {
        node->height = lh + 1;
    } else {
        node->height = rh + 1;
    }
}

2.节点平衡因子

• 节点的平衡因子 （balance factor）：节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为 0 。

/* 获取平衡因子 */
int balanceFactor(TreeNode *node) {
    // 空节点平衡因子为 0
    if (node == NULL) {
        return 0;
    }
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node->left) - height(node->right);
}

# 设平衡因子为 𝑓 ，则一棵 AVL 树的任意节点的平衡因子皆满足 −1 ≤ 𝑓 ≤ 1 。

2.AVL树旋转

• AVL 树的特点在于旋转 操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持二叉搜索树的性质，也能使树重新变为平衡二叉树

• 将平衡因子绝对值 > 1 的节点称为失衡节点 。根据节点失衡情况的不同，旋转操作分为四种：

  • 右旋
  • 左旋
  • 先右旋后左旋
  • 先左旋后右旋。

1.右旋

flowchart LR
	subgraph B[将该节点记为node，其左节点记为child]
	4'[4] --> 3'["3
	(node)"]
	4' --> 5'[5]
	3' --> 1'["1
	(child)"]
	1' --> 0'[0]
	end

	subgraph A[失衡的树]
	4[4] --> 3[3]
	4 --> 5[5]
	3 --> 1[1]
	1 --> 0[0]
	end
	
	A --关注失衡节点为根节点的子树--> B

flowchart LR
	subgraph B[恢复平衡]
	4' --> 1'
	1'[1] --> 3'[3]
	1' --> 0'[0]
	4'[4] --> 5'[5]
	end


	subgraph A[将失衡节点以child为原点右旋]
	4[4] --> 5[5]
	1[1] --> 3
	1 --> 0[0]
	end
	
	A --用child代替原来node的位置--> B

• 向右旋转 是一种形象化的说法，实际上需要通过修改节点指针 来实现

/* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {
    TreeNode *child, *grandChild;
    child = node->left;
    grandChild = child->right;
    // 以 child 为原点，将 node 向右旋转
    child->right = node;
    node->left = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}

2.左旋

• 与右旋类似
• 在逻辑上和右旋是镜像对称的，它们分别解决的两种失衡情况也是对称的
• 所以只要把上述右旋代码中的left替换为right，right替换为left即可

3.先左旋后右旋

flowchart LR
	subgraph 原失衡树
	4[4] --> 3["3
	(失衡节点)"]
	4 --> 5[5]
	3 --> 1[1]
	1 --> 2[2]
	end
	subgraph 先左旋
	4'[4] --> 3'[3]
	4' --> 5'[5]
	3' --> 1'[1]
	1' --> 2'[2]
	end	
	subgraph 再右旋
	4''[4] --> 3''[3]
	4'' --> 5''[5]
	3'' --> 1''[1]
	1'' --> 2''[2]
	end	
	原失衡树 --> 先左旋 --> 再右旋

4.先右旋后左旋

• 和上述同理

5.旋转的选择

• 根据失衡节点的平衡因子已经较高一侧的平衡因子的正负号来确定

失衡节点的平衡因子	子节点的平衡因子	应采用的旋转方法
>1（左偏树）	$\geq$0	右旋
>1（左偏树）	<0	先左旋后右旋
<-1（右偏树）	$\leq$0	左旋
<-1（右偏树）	>0	先右旋后左旋

/* 执行旋转操作，使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {
    // 获取节点 node 的平衡因子
    int bf = balanceFactor(node);
    // 左偏树
    if (bf > 1) {
        if (balanceFactor(node->left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (bf < -1) {
        if (balanceFactor(node->right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    // 平衡树，无须旋转，直接返回
    return node;
}

# 这个函数就可以应对各种失衡情况

3.AVL树常见操作

1.插入节点

• 与二叉搜索树类似，但是在插入后可能会导致失衡，所以需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡

/* 插入节点 */
void insert(AVLTree *tree, int val) {
    tree->root = insertHelper(tree->root, val);
}
/* 递归插入节点（辅助函数） */
TreeNode *insertHelper(TreeNode *node, int val) {
    if (node == NULL) {
        return newTreeNode(val);
    }
    
    /* 1. 查找插入位置并插入节点 */
    if (val < node->val) {
        node->left = insertHelper(node->left, val);
    } else if (val > node->val) {
        node->right = insertHelper(node->right, val);
    } else {
        // 重复节点不插入，直接返回
        return node;
    }
    // 更新节点高度
    updateHeight(node);
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

2.删除节点

• 在二叉搜索树的基础上，需要从底部至顶部执行旋转操作，使所有失衡节点恢复平衡

/* 删除节点 */
// 由于引入了 stdio.h ，此处无法使用 remove 关键词
void removeItem(AVLTree *tree, int val) {
    TreeNode *root = removeHelper(tree->root, val);
}

/* 递归删除节点（辅助函数） */
TreeNode *removeHelper(TreeNode *node, int val) {
    TreeNode *child, *grandChild;
    if (node == NULL) {
        return NULL;
    }
    /* 1. 查找节点并删除 */
    if (val < node->val) {
        node->left = removeHelper(node->left, val);
    } else if (val > node->val) {
        node->right = removeHelper(node->right, val);
    } else {
        if (node->left == NULL || node->right == NULL) {
            child = node->left;
            if (node->right != NULL) {
                child = node->right;
            }
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == NULL) {
                return NULL;
            } else {
                // 子节点数量 = 1 ，直接删除 node
                node = child;
            }
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode *temp = node->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    // 更新节点高度
    updateHeight(node);
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

3.查找节点

• 与二叉搜索树相同

4.AVL树典型应用

• 组织和存储大型数据，适用于高频查找、低频增删 的场景。
• 用于构建数据库中的索引系统 。
• 红黑树 也是一种常见的平衡二叉搜索树。相较于 AVL 树，红黑树的平衡条件更宽松，插入与删除节点所需的旋转操作更少，节点增删操作的平均效率更高。