授课教师：邓俊辉
教师介绍：清华2014年度十大优秀老师！MOOC上数据结构公开课报名已超5万人！你还不来看
笔记简介：哈希表，红黑树，斐波那契二分查找，从基本到高端的数据结构全都有！有重点，有插图，还有鄙人学习感悟，看完这笔记中的战斗机你还想啥！
20140603
————————————————————
ADT是抽象数据类型，为一组数据模型，加上一组操作，不涉及具体的储存方式，就像是用户使用的产品（黑箱），只考虑抽象层面
DS是数据接收，是根据特定语言实现ADT的算法，设计复杂度和各种具体机制。
（计算幂次方的方法： pow(a,b)
we can devide b into binary type and pow(a,2^n) = pow(a,2^(n-1)) so we can do it in O(log2 n), each time rotate 1 time. ）
vector 向量数据结构，可以对不同数据类型操作，并且封装了许多操作，比如remove(r),sort(),search(e)无序去重,deduplicate(),uniquify()有序去重,traverse()遍历
search(n) 返回不大于n的元素的最后的rank put(a,b) 将rank为a的数改为b
平均复杂度：根据数据结构个操作出现概率分布进行加权平均，每个操作作为独立事件，割裂了相关性与连贯性
分摊复杂度：将数据结构连续地实施足够多的操作，所需总体成本分摊至单次操作。对一系列操作整体考量，更加精确。
vector 插入算法：
从固定插入位置开始，先扩容，然后从rank = n downto 固定位置k vector[n] = vector[n-1]逐个后移 最后执行插入。
vector 删除： 区间删除：
删除从lo 到 hi 的区间
则执行如下：
_elem[lo++] = elem[hi++] 即从前向后逐次移位
不能更改次序，因为如果要删除的区间与想向前移动的区间有重复区间，从后向前的话会覆盖掉重复区间的部分。
有序相向量的唯一化 低效版：
有序向量，重复的元素构成一个区间，因此每个区间保留一个即可。 于是可以从前向后依次检查来逐个删除相同元素 O(N^2) 高效版：
成批删除雷同元素，将他们视为一个整体。 i = j = 0
如果二者不相等，则_elem[++i] = _elem[++j]，相当于忽略了所有重复元素（没有直接显示调用删除）。
_____________________________________ Fabonacci查找法：
由于二分查找在大于、小于和等于的情况下比较次数不同，所以造成内部比较次数的不平均，因此为了平衡比较和查找次数，可以构建一个看起来不平衡的数列来平衡比较次数。这就是Fabonacci查找法
while(lo < hi) {
while (hi - ol < fib.get()) fib.previous(); rank mi = lo + fib.get() - 1; if (e < A[mi]) hi = mi;
else if (A[mi] < e) lo = mi + 1; else return mi; }
return -1;
证明：运用递推*
———————————————————————— 二分查找的改进版：
为了隐藏比较次数，只比较一次： while(1 < hi - lo)
{
rank mi = (lo + hi) >>１；
( e < A[mi] ) ? hi = mi : lo = mi; (不再是 mi + 1) }出口时 hi = lo + 1 return (e == A[lo]) ? lo : -1;
只是平均情况减少，但最好情况增加。
最优化版：如果不在其中，还可返回最近的小于此元素的坐标
冒泡排序改进：可以记录前面是否有逆序对，如果没有就证明不用再排序了
再改进：可以增加一个last，也就是最后一个逆序对的位置，然后以后就只用排开始到last位置的元素了。
————————————————————————
第三章：列表