学习完二叉树和二分搜索树之后我们可以再来看看三叉树是怎么实现的，随后可以推广到多叉树。 三叉树 三叉树的一个节点需要两个值和三个指针，以及一个 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...

二分搜索树（Binary Search Tree） 相比于二叉树有更加严格的性质： 无重复元素 从左到右、从上到下依次增大 寻找（Find） 核心想法是一直比较左右节点，然后向下递归查找。 找最小 BinaryNode<Comparable>* findMin(BinaryNode<Comparable>* t) const { i...

这份笔记是大一下复习C++时顺手整理的，可以服务于考试，也可以用于C++的实践了解，其主要注重于C++的三大特性（封装，继承，多态）。