1. 最小生成树概述最小生成树（Minimum Spanning Tree，简称为 MST）作为图论领域的关键概念，在加权连通图里有着广泛且重要的应用。在深入探究最小生成树的具体内涵之前，让我们先一同回顾图论中的一些基础知识点：
加权图
加权图（Weighted Graph）是一种每条边都被赋予一个权值（Weight）的图。这些权值可以代表距离、成本、时间等实际意义的度量。比如在一个表示城市间道路的图中，边的权值可以表示两个城市之间的距离。
连通图
连通图（Connected Graph）指的是在无向图中，任意两个顶点之间都存在路径相连。也就是说，从图中的任意一个顶点出发，都能够到达其他任何顶点。
联通网
带权连通图就是连通网。
生成树
生成树是一种特殊的连通子图，涵盖了连通图里的所有N个顶点，并且恰好包含N−1条边。
最小生成树这一概念，最初主要是为加权连通无向图量身打造的。不过，在有向图领域，也衍生出了与之类似的拓展性概念。而本课程所涉及的内容，主要围绕加权连通无向图来逐步展开，以此来探讨最小生成树相关知识。
对于一个加权连通无向图 G=(V,E)，其中V是图的顶点集合 ...
1. 并查集概述并查集（Union-Find），又称不相交集合（Disjoint Set Union, DSU），是一种用于处理不相交集合的合并与查询问题的数据结构。它支持两种主要操作：
查找（Find）：确定一个元素属于哪个集合。
合并（Union）：将两个不同的集合合并成一个集合。
并查集常见的存储方式是使用数组来模拟树结构，利用数组存储每个元素的父节点信息。数组的下标对应元素编号，数组中存储的值代表该元素的父节点编号。通过不断查找元素的父节点，最终找到根节点，以此确定元素所属的集合。
在上图里呈现的是两棵树的结构，而在并查集这种数据结构体系中，这两棵树分别对应着两个集合。从存储实现的角度来看，这两个集合通常会以两个数组的形式来进行表示。
（图1）数组下标
0
1
2
3
4
5
节点值
D
E
F
G
H
J
存储的父节点编号
0
0
0
0
1
3
（图2）数组下标
0
1
2
3
4
5
6
节点值
A
B
C
D
E
F
G
存储的父节点编号
0
0
0
1
3
4
5
在并查集所构建的树状结构里，根节点处于一种特殊地位，它不 ...
1. 最短路径概述在计算机科学和图论领域中，图的最短路径问题是一个非常重要且经典的问题。图是由顶点（节点）和连接这些顶点的边组成的数据结构，在许多实际场景中都有广泛应用，如地图导航、网络路由、社交网络分析等。最短路径问题的目标是在一个图中找到从一个特定的起始顶点到另一个目标顶点的路径，使得这条路径上所有边的权值之和最小。
依据图中边是否具有方向对最短路径进行分类，可将其明确划分为有向图最短路径和无向图最短路径这两类。
1.1 有向图的最短路径在有向图中，边是有方向的，从顶点u到顶点v的路径必须沿着边的方向进行。因此，有向图中顶点之间的可达性和最短路径是有方向性的，即从u到v的最短路径和从v到u的最短路径可能不同，甚至一个方向可达而另一个方向不可达。
有向图的的最短路径的应用场景举例：
交通网络：例如城市中的单行道网络，车辆只能按照规定的方向行驶，就可以用有向图来表示，计算从一个地点到另一个地点的最短路径。
任务调度：在项目管理中，任务之间存在先后依赖关系，用有向边表示任务的先后顺序，可通过计算有向图的最短路径来确定项目的最短完成时间。
然后，我们再来了解一下有向图最短路径的求解方式 ...
1. 图的基本概念图（Graph）是一种极为重要且基础的结构。由顶点（Vertex，也称为节点 Node）集合V和边（Edge）集合 E组成的一种数据结构，通常表示为 G=(V,E)其中 V代表顶点的有穷非空集合，而 E 则代表边的集合。
接下来，我们再了解一些图相关的术语：
顶点（Vertex）集合：具有有穷性且非空，意味着其中包含有限数量的顶点元素，并且至少存在一个顶点
边（Edge）集合：边用于表示顶点与顶点之间的关联关系，它们可以是无向的，用以体现顶点间的双向联系，也可以是有向的，来明确顶点间的单向关联
度（Degree）：在无向图中，一个顶点的度是指与该顶点相连的边的数量；
入度（In - Degree）：在有向图中，入度是指向该顶点的边的数量
出度（Out - Degree）：在有向图中，出度是从该顶点出发的边的数量。
相邻顶点（Adjacent Vertices）：如果两个顶点之间有边相连，则称这两个顶点相邻。
生成树（Spanning Tree）：连通无向图的一个子图，它是包含图中所有顶点的树（无环的连通图）。
森林（Forest）：由若干棵树组成的图，即每个连通 ...
1. Trie 树的基本概念Trie树，又称字典树、前缀树，是一种树形数据结构，常用于高效地存储和检索字符串集合。它的主要特点是利用字符串的公共前缀来减少存储空间和提高查询效率，特别适用于字符串的前缀匹配、自动补全、拼写检查等场景。
对于一棵字典树而言具有以下基本性质：
它是一棵多叉树，每个节点代表一个字符。根节点不包含字符，除根节点外的每个节点都包含一个字符。
从根节点到某一节点的路径上经过的字符连接起来，即为该节点对应的字符串。
每个节点可能有多个子节点，每个子节点对应一个不同的字符。
通常在表示字符串集合的Trie树中，会有一些特殊标记来表示某个节点是否是一个字符串的结尾。
下图是一颗字典树，在树中存储了这些单词：
app、apple、acc、acce、access、
back、backup、backed、be、bea、bear
ca、can、cancel、cancer、car、carbon、cause
基于字典树的特性，我们可以得知它是天然支持前缀匹配的，因为字典树可以适用于以下的场景：
字符串检索
可以高效地查找某个字符串是否存在于一个字符串集合中，时间复杂度为 ...
1. 跳跃表基本概念跳跃表（Skip List）是一种概率性数据结构，它就像是升级版的有序链表，专门用来实现有序集合的功能。它通过引入多层索引来提高查找、插入和删除操作的效率，使得这些操作的时间复杂度可以达到 O(logn)，其效率可以与平衡二叉搜索树相媲美。跳跃表的核心思想是通过随机化来维护多层索引，从而避免像平衡树那样复杂的平衡操作。
随机性决定节点层数：在跳跃表中，每个节点的层数是随机确定的。
当插入一个新节点时，算法会根据一个随机过程来决定该节点应该拥有多少层。通常，这个随机过程基于抛硬币的思想，比如抛一次硬币，正面则该节点的层数加 1，继续抛硬币，直到出现反面为止。这种随机性使得跳跃表在构建时不需要预先知道数据集的大小和分布，它会在动态插入和删除元素的过程中自动调整结构。
平均性能而非最坏性能保证：跳跃表通过随机化的方式来平衡其结构，从而在平均情况下达到较好的性能。
虽然在最坏情况下，跳跃表的性能可能会退化为普通链表的性能（例如所有节点的层数都为 1），但这种情况发生的概率非常低。它的平均时间复杂度为 O(logn)，这里的平均是基于随机算法的期望性能，而不是对所有 ...
1. 红黑树概述1.1 红黑树的定义红黑树是一种自平衡的二叉搜索树，，由Rudolf Bayer于1972年发明。它能确保在最坏情况下基本动态集合操作（如插入、删除、查找）的时间复杂度为 O(logn)，这里的 n 是树中节点的数量。红黑树在它的每个节点上增加了一个存储位来表示节点的颜色（红色或黑色），通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。这使得树的高度始终保持在对数级别，从而保证了操作的高效性。
红黑树的高效性使其在很多领域都有广泛的应用，以下是一些常见场景：
标准库的实现
C++ STL 的map/multimap/set/multiset容器
Java TreeMap 和 TreeSet
由于红黑树的自平衡特性，这些容器在插入、删除和查找操作上都能保证 O(logn)的时间复杂度，为开发者提供了高效的数据存储和检索方式。
Linux 内核进程调度，是在完全公平调度器（Completely Fair Scheduler，CFS）里，红黑树被用于管理进程。
...
数据结构
未读1. 霍夫曼树霍夫曼树（Huffman Tree），又称最优二叉树，它是一种在给定一组带有特定权值的叶子节点后，构建出的带权路径长度（Weighted Path Length, WPL）达到最小的二叉树。
基于下表我们可以构建出这样一棵霍夫曼树：
数据
权值（频率）
A
10
B
15
C
12
D
3
E
4
F
13
G
1
在学习霍夫曼树的过程中，有几个关键概念需要大家深入理解。接下来，我将为大家逐一详细介绍。
1.1 重要概念解析字符频率
定义：字符频率是指在一个数据集中，某个字符出现的次数或概率。
作用：霍夫曼树的构建依赖于字符的频率，频率越高的字符在树中的路径越短，从而获得更短的编码。
示例：在字符串 "aabbbcc" 中，字符 'a' 的频率为 2，'b' 的频率为 3，'c' 的频率为 2。
叶子节点
定义：霍夫曼树中的叶子节点表示字符及其频率。
作用：使用叶子节点存储字符及其频率信息。
示例：在霍夫曼树中，字符 'a' 和 'b& ...
1. 平衡二叉树1.1 概述平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它的每个节点的左右子树的高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。这意味着所有的平衡二叉树都必然是二叉搜索树，但并非所有的二叉搜索树都是平衡二叉树。平衡二叉树的主要目的是避免二叉搜索树（BST）在极端情况下退化为链表，从而保证查找、插入和删除操作的时间复杂度为 O(logn)。
常见的平衡二叉树包括：
AVL 树（严格平衡）：通过旋转操作保持平衡。
红黑树（相对平衡）：通过颜色标记和旋转操作保持平衡。
AVL 树的全称是“Adelson-Velsky and Landis Tree”，它以苏联数学家 Georgy Adelson - Velsky 和 Evgenii Landis 的名字命名。这两位数学家在 1962 年的论文中首次提出了这种自平衡的二叉搜索树结构，通过在插入和删除操作时进行旋转操作来保持树的平衡，确保树的高度始终维持在对数级别，从而保证了各种操作（如查找、插入、删除）具有 O(logn) 的时间复杂度。
1.2 平衡因子AVL 树的每个节 ...
1. 二叉树搜索树概述二叉搜索树（Binary Search Tree, BST）也叫二叉排序树（Binary Sort Tree），是一种特殊的二叉树，它满足以下性质：
左子树：左子树上所有节点的值都小于根节点的值。
右子树：右子树上所有节点的值都大于根节点的值。
递归性质：左子树和右子树本身也是二叉排序树。
二叉搜索树的一个重要特性是，它的中序遍历（左 → 根 → 右）结果是一个有序的序列。因此，二叉搜索树常用于实现动态集合的查找、插入和删除操作。
2. 二叉搜索树的基本操作2.1 查找操作二叉搜索树（BST）的查找操作是一种高效的算法，其平均时间复杂度为 O(log n)。查找步骤是基于二叉搜索树的特性：对于每个节点，左子树的所有节点值小于当前节点，右子树的所有节点值大于当前节点。以下是详细的查找步骤：
从根节点开始：查找操作必须从二叉搜索树的根节点开始。
比较目标值与当前节点值
如果 目标值 == 当前节点值，查找成功，返回该节点。
如果 目标值 < 当前节点值，则递归查找左子树。
如果 目标值 > 当前节点值，则递归查找右子树。
...
