本文是ads的个人学习提要。
第一节课：#
心理准备：多做题；
提前约课堂展示。
要记得给别人打分。认真打分。评价打分打得好有加分。
记得做诚信守则。
AVL:#
二叉搜索树的进一步优化（提高搜索效率），核心思想是减小树高，使其 平衡。
树高的定义取决于 空树的树高是多少 ，这里统一为：
- Height(NULL)=-1;
- Height(0)=0;
AVL树的平衡策略是减小左子树和右子树的树高距离，保持左右子树树高的距离小于1；
其基本定义为：
- 空树是平衡的；
- 若某节点的左右子树高距离小于1，则这个节点是平衡的；
- 若这个树是AVL树，则所有的节点都是平衡的。
AVL树最常见的建立方式是 边插入，边平衡。平衡涉及的操作是 旋转。旋转是计算开销的基本单位。
不仅要理解其本质旋转原型是什么样的，还要学会辨别需要什么类型的旋转。
考试不考删除。
书上的单旋转将旋转后的新根返回，我个人的实现中没有实现这一点，所以有所差异。
splay tree:#
涉及到 均摊分析，也就是说，我们对序列操作的时间消耗总和进行更细致的分析。
我们对序列操作的相互影响进行分析，主要思想是：在一次查询后为下一次查询做铺垫。
因为得到资源地址是困难的，因而我们最好能在获得了资源地址后，多做一些尽量有用的操作。这些操作在独立实现的时候是非常费事的。
从而，splay tree的核心思想就是，对那些可能需要多次查询的资源，提高他们的位置，这样方便后面的寻找。
摊还分析：#
核心思想是：对连续操作来说，我们希望总体上减少这些操作的耗时，一个显而易见的思路是 省时间的操作时多做一点工作，减少耗时间的操作的时间。
比如上面的splay tree。
计算摊还总代价有两个方面：
- 我们正面计算$n$次每个操作所消耗的代价总和,直接计算平均值；
- 我们计算耗时少的操作能省下的时间，并用这些时间来做剩下的耗时高的操作。只要剩下的耗时高的操作都可以完成，那么说明我们计算的就是正确的。
第一种方法就是最简单的 aggregate method，也即 聚合分析；后者则有两种形式，一种是 accounting method，一种是 potential methods。
势能法分析实际上是将核算法（我喜欢叫数钱法）从离散形式拓展到可离散可连续的形式。
作业：#
- 计算某一高度的avl树的最小节点数：注意高度的定义；递归计算。
- 这个计算结果告诉我们，只有节点数充足才能构建相应的avl树。
- 伸展树的操作；
- 均摊分析，势能法。
- program：avl树的实现
第二节课：#
本节课讲红黑树/B+树。
avl树的删除不好/插入的时候往下遍历（还要往上遍历）
看完了网上的教程和历史后，我可以负责的写下：红黑树的来源是B树。因此对插入和删除的理解都可以从B树出发。
红黑的定义：
- 每个节点要么黑要么红；
- 根/叶子是红的，空指针也算叶子，称为nil；
- 红节点的孩子必须是黑的；
- 从节点到所有子叶子上黑色的节点数量完全相同。可以定义为黑高。
- 黑高不数根，但数nil。
红色节点数显然是少于黑色节点数的。这个树想要越高（但是节点数不随之增加太多），就要有更多的红色节点，这样会不增加黑高。所以全是黑色节点的树高度是最小的。
黑高和树高有很近的关系，树高最多是黑高的两倍，否则必然有两个红节点相遇。所以我们根据这一个关系得到一个不等式：
若红黑树的节点数总数为$n$，则其树高最多为$2log_2(n+1)$;
老师说的有一点乱，我觉得上面这个就是比较好理解得一点。
进一步的说，红黑树的约束就体现在这个地方： 约束了搜索的最大上限：到达每个节点都有着不错的平均耗时（黑高）；
删除操作：
- 首先保持二叉搜索树特性，这是正常删除操作；
- 删除的时候，如果删除要改变某子树的黑高，肯定是减少，那么有这样的解决思路：减少隔壁子树的黑高，然后在共同路径上增加一个黑色的，这样整体黑高就不会变。
- 这种做法有一些handy的操作，比如旋转，可以将一个黑的从子树间调整；比如直接把所有的路径上的黑高全部都减1；比如把要删除节点的邻子树变个颜色，然后再旋转。不过想要真正运用出来，需要
B+树：#
出现失衡的一种直观表现是，有的子树存的多，有的子树存的少。必加树就是为了解决这个问题。
必加树规定：
- 根要么是叶子，要么含有2-M个子节点。
- 不是叶子的节点必须要有一半M以上的的子节点数；
- 所有的叶子节点深度一致。
内部节点是索引，叶子是真正存储数据的东西。看下面这段描述：
- 有 n 棵子树的节点中含有 n-1 个关键字（即将区间分为 n 个子区间，每个子区间对应一棵子树）。
- 所有叶子节点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
- 所有的非叶子节点可以看成是索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字。
- 除根节点外，其他所有节点中所含关键字的个数最少有$\lceil \dfrac{m}{2} \rceil$（注意：B 树中除根以外的所有非叶子节点至少有$\lceil \dfrac{m}{2} \rceil$棵子树）。
必加树的操作有：
- 初始化：
- 插入：插入一个新的节点，包括分割
- 删除；
必加树的每一个节点提供了一个一半M以上的分法，因此搜索时间和二分法是一样的$O(logN)$；每个内部节点称为
必加树和红黑树之间有神奇的联系。因为必加树所有叶子的深度都一样，红黑树的黑高是一样的，所以红黑树的黑节点其实就是必加树的每一层。
必加树的插入思如果插入后叶子的父节点也满了，那么就需要对叶子的父节点进行分割；然后路是这样的：
- 如果根是空的，那么直接创建一个新叶子作为根，然后往里面添加key，直到满；
- 如果叶子满了，那么将叶子分裂成为两半，然后插入到其父节点（内部节点上）；
第三节课：#
本节课讲述一个搜索引擎如何实现。
将超链接视为节点，我们就可以实现一个图。
根据搜索关键词，我们先找出现了该词的文章，然后再找每个词对应文章的交集。称之为 term-document incidence matrix。其中找交集的方法称为布尔查询/布尔检索。
然而直接使用矩阵来存还是太占空间了，于是我们使用邻接表来存。
我们不仅要看到文章标题，还要相互匹配，给出上下文，以便进一步分析。
左式堆：#
左式堆对应avl。
堆是具有最值性质的完全二叉树。但是堆进行合并的时候没有完全利用堆的性质。于是我们希望修改这个内容。
首先定义零路径，也就是到 没有两个子节点的节点的路径长度。定义NPL(NULL)=-1;
左式堆：根的左子节点零路径大于右子节点零路径。这保证了树会沿着左走。
（第四节课）
这个性质保证了，右零路径如果长度是r，那么整棵树的节点数不会少于$2^r-1$个;
其关键函数是合并，插入和删除都可以看成合并。
斜堆：#
二项队列：#
二项队列是由二项树组成的，二项树是一种
斐波那契堆：#
第五节课：#
数据结构从这里就基本讲完了，后面都是算法的事情。
算法