最近发现有时候看完一本书，时间久了容易忘记，看书不总结思考效果大打折扣，故打算写这一系列文章，一是为了整理书中的要点，帮助自己消化理解；二是勉励自己多看书思考。文章中不会把书中内容讲解的非常详细，只是总结概括，适合已经阅读过该书的读者。
（1）栈与队列
栈（stack）：后进先出（LIFO）队列（queue）：先进先出（FIFO）（2）链表
单向链表双向链表在直接寻址方式下，具有关键字k的元素被存放在槽k中。在散列方式下，该元素存放在槽h(k)中；即利用散列函数（hash function）h，由关键字k计算出槽的位置
装载因子：给定一个能存放n个元素的、具有m个槽位的散列表T，T的装载因子为n/m，即一个链的平均存储元素数
冲突：两个关键字可能映射到同一个槽中
（1）解决冲突的方法
链接法：把散列到同一槽中的所有元素都放在一个链表中线性探查法：冲突后，线性向前试探，找到最近的一个空位置。缺点是会出现堆积现象。存取时，可能不是同义词的词也位于探查序列，影响效率。双散列函数法：在位置d冲突后，再次使用另一个散列函数产生一个与散列表桶容量m互质的数c，依次试探(d+n*c)%m，使探查序列跳跃式分布。（2）散列函数
除法散列法：h(k) = k mod maxM ; maxM一般是不太接近 2^t 的一个质数。乘法散列发法:h(k) = m(Ak mod 1)平方取中法：h(x) =(x*x div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较多。（3）用途
文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。MD5 Hash算法的”数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。数字签名 Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称”数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。鉴权协议 如下的鉴权协议又被称作挑战–认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。（1）特点和遍历－O(n)
设x市二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key <= x.key。如果y是x右子树中的一个结点，那么y.key >=x.key。
中序遍历（inorder tree walk）：子树根的关键字位于其左子树和右子树的关键字之间。先序遍历（preorder tree walk）：根的关键字在其左右子树的关键字之前。后续遍历（postorder tree walk）：根的关键字在其左右子树的关键字之后。（2） 查询二叉搜索树-O(h)
递归版
TREE-SEARCH(x,k) if x==NIL or x.key==k return x if k < x.key return TREE-SEARCH(x.left,k) else return TREE-SEARCH(x.right,k)迭代版(效率高很多)
ITERATIVE-TREE-SEARCH(x,k) while x!=NIL and k!=x.key if k < x.key x=x.left; else x=x.right return x（3）插入和删除-O(h)
插入算法与查询算法类似
删除：（分三种情况，设一棵二叉搜索树T中删除结点z） * 如果z没有孩子结点，那么简单地将它删除，并修改它的父结点，用NIL作为孩子来替换z * 如果z只有一个孩子，那么将这个孩子提升到树中z的位置，并修改z的父结点，用z的孩子来替换z * 如果z有两个孩子，那么找z的后继y（一定在z的右子树中），并让y占据树中z的位置。z的原来右子树部分称为y的新的右子树，并且z的左子树称为y的新的左子树，这种情况稍微复杂，有两种情况，如下所示：因为还涉及y是否为z的右孩子
一棵高度为h的二叉搜索树，它可以支持任何一种基本动态集合操作，其时间复杂度均为O(h)。当h较小时，执行会比较快。红黑树是许多“平衡”搜索树中的一种。
（1）性质
树中的结点有5个属性：color，key，key，left，right和p，满足以下五大性质：
每个结点或是Red，或是Black根结点是Black的每个叶结点NIL是Black的如果一个结点是Red，则它的两个结点都是black对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的Black结点（2）旋转
一棵含有n个关键字的红黑树上，搜索树操作插入和删除话费时间在O(lgn)。这两个操作对树做了修改，可能违反红黑性质，为维护这些性质，需改变树中结点颜色以及指针结构，一般通过旋转操作。
B树以一种自然的方式推广了二叉搜索树。如果B树一个内部结点x包含x.n个关键字，那么结点x就有x.n+1个孩子
一个常见的B树变种，称为B+树，它把所有的卫星数据都存储在叶结点中，内部结点只存放关键字和孩子指针，因此最大化了内部结点的分支因子
ps：由于大多数系统中，一个B树算法的运行时间主要由它所执行的DISK－READ和DISK－WRITE操作的次数决定，所以我们希望这些操作能噢股读或写尽可能多的信息。因此，一个B树结点通常和一个完整磁盘页一样大，并且磁盘页的大小限制了一个B树结点可以含有的孩子个数
（1）特性
比较重要的特性有 每个叶结点具有相同的深度，即树的高度h每个结点所包含的关键字个数有上界，和下界。用一个被称为B树的最小度树的固定整数表示t >= 2 1.除了根结点以外，每个结点至少有t－1个关键字，即至少t个孩子2.每个结点至多可包含2t－1个关键字，即至多2t个孩子（2）搜索
O(th)=O(tlog_t(n))
t为B树的最小度数，h为B树的高度，n为B树的结点数
（3）插入
O(th)
（4）删除
O(th)
