生成树 Spanning Tree 给定连通图中的 $|V|=n$ 个节点，使用 n-1 条边将这些点连接起来。在这些点中选取一个根节点，即成为一颗生成树。生成树不是唯一的，可以选取不同的顶点作为根节点。 生成树可以很奇特： 最小生成树 Minimal Spanning Tree 如果我们将这个图的边添加权重，那么所包含的边权重最小的生成树就是最小生成树。对于没有显式给出权重...

图的基本定义 图是一种用于存储邻接关系（Adjacency） 的抽象数据类型 (ADT)，由顶点和边组成： 顶点集合 $V={v_{1},v_{2},…,v_{n}}$ 连接顶点的边集合 $E$ 图又被分为无向图和有向图； 度（Degree） 一个顶点的度为与该顶点相邻的顶点数量（区分有向和无向） 。 无向图（Undirected） 无向图的边为无序对 ${v_{i},...

主要对学习过的排序算法进行时间、空间复杂度上的一些整理。 算法名称 类别 最好 平均 最坏 空间复杂度 核心思想 1. 冒泡排序(Bubble Sort) 交换排序 $O(n)$ $O(n^2)$ ...

在离散数学（Discrete Mathematics）中我们曾经学习过，“一个等价关系可以将一个集合中的元素划分为多个等价类”，这多个等价类就是多个不相交的集合，我们称其为并查集（Disjoint Set）。 从翻译的角度上来看，并查集和 Disjoint 好像并没有什么关系。中文上的“并查”指的是在这个数据结构上可以进行的操作：并（Union） 和查（Find）。但在英语上，只是说明了他...

学习完二叉树和二分搜索树之后我们可以再来看看三叉树是怎么实现的，随后可以推广到多叉树。 三叉树 三叉树的一个节点需要两个值和三个指针，以及一个 int num_values (1 or 2) 来存储当前节点有几个值（还有几个空位）。 这是因为为了实现三叉树，必须要有两个可进行比较的元素来将当前进入的节点划分到两个值切成的三个范围中（也就是三个指针指向左、中、右子树）。 和二叉树...

前面我们学习过在AVL树中，我们实现查找到叶子节点或者其他操作的时间受到树高 $O(\log N)$ 的限制，现在我们再来看看有没有更快的一种搜索并查找我们想要的数据。 Map ADT 首先来看看一种新的ADT，Map，映射。 一个映射是一个或多个键值对 (Key, Value) 的集合，对于每一个键值对，Key是唯一的。 支持两个操作： get(key)：获取键对应的值 pu...

在学习完Mergesort和Quicksort之后，我们会发现他们的时间复杂度似乎已经突破不了 $\Theta(nln(n))$ ，这其实是这类排序算法的局限。 这类排序算法的本质其实是通过元素间的移动、交换来最终实现排序。理论已经证明了基于元素交换的排序算法存在速度上限 $\Theta(nln(n))$ ，因此我们无法尝试再去在元素交换的基础上去提高速度。 能不能换种方法继续提高速度？...

和堆排序类似，合并排序和快排也都是 $\Theta(n ln(n))$ 的排序算法，但是这两个排序算法会稍微更快点，因为分别需要 $\Theta(n)$ 和 $\Theta(ln(n))$ 的空间。 归并排序 Mergesort Mergesort 是一种递归的“分治”(divide-and-conquer) 算法。 假设我们现在有两个已经排好序的 sublist，那么现在需要做的就是...

首先我们需要认识一个概念 Inversions ： 指的是在一个 $n$ 个数的集合中 $a_0…a_{n-1}$ 满足：$j<k$ 但 $a_j>a_k$ 的有序元组 $(a_j,a_k)$ 对于一个未排序的数组，就可以看成是由多个 Inversions 组成的 选择排序 Selection Sort 先考虑以下情况： 有一个已排序的列表，其所有元素都小于未排序的列表，...

堆的ADT是“优先队列（Priority Queue）”。 优先队列的定义与操作 定义：与标准队列的“先进先出” 不同，优先队列允许弹出具有最高优先级的对象 ，一般定义 0 为最高优先级 。 优先队列的两种简单实现 多队列 (Multiple Queues) 方法：创建一个包含 M 个队列的数组，每个队列对应一个优先级。 分析：Pus...