查找

一些定义：

事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。

事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。

活动ai由弧

查找

顺序查找、折半查找、索引查找、分块查找是静态查找，动态查找有二叉排序树查找，最优二叉树查找，键树查找，哈希表查找

静态查找表

顺序表的顺序查找：应用范围：顺序表或线性链表表示的表，表内元素之间无序。查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。

顺序有序表的二分查找。平均查找时间(n+1)/n log2(n+1)

分块查找：将表分成几块，块内无序，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序，块内无序。所以，块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间；先确定待查记录所在块，再在块内查找。因此跟表中元素个数和块中元素个数都有关。

用数组存放待查记录,

建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成。

当索引表较大时，可以采用二分查找

在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级

分块查找平均查找长度：ASLbs = Lb + Lw。其中，Lb是查找索引表确定所在块的平均查找长度， Lw是在块中查找元素的平均查找长度。在n一定时，可以通过选择s使ASL尽可能小。当s=sqrt(n)时，ASL最小。

时间：顺序查找最差，二分最好，分块介于两者之间

空间：分块最大，需要增加索引数据的空间

顺序查找对表没有特殊要求 

分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。

二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。

在表不大时，一般直接使用顺序查找。

动态查找

二叉排序树的结点删除：

x为叶子结点，则直接删除

x只有左子树xL或只有右子树xR ,则令xL或xR直接成为双亲结点f的子树；

x即有左子树xL也有右子树xR，在xL中选值最大的代替x，该数据按二叉排序树的性质应在最右边。

平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差1的二叉排序树。

平衡二叉树的平衡：

左调整(新结点插入在左子树上的调整)：

LL(插入在结点左子树的左子树上)：旋转前后高度都为h+1

LR(新插入结点在左子树的右子树上)：旋转前后高度仍为h+1

右调整(新结点插入在右子树上进行的调整):

RR(插入在的右子树的右子树上)：处理方法和 LL对称

RL(插入在的右子树的左子树上)：处理方法和 LR对称

平衡树建立方法：

按二叉排序树插入结点

如引起结点平衡因子变为|2|，则确定旋转点，该点是离根最远（或最接近于叶子的点）

确定平衡类型后进行平衡处理，平衡后以平衡点为根的子树高不变

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

常见的平衡二叉树：

红黑树是平衡二叉树，也就是左右子树是平衡的，高度大概相等。这种情况等价于一块完全二叉树的高度，查找的时间复杂度是树的高度，为logn，插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)

节点是红色或黑色。

根是黑色。

所有叶子都是黑色（叶子是NIL节点）。

每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。

avl树也是自平衡二叉树；红黑树和AVL树查找、插入、删除的时间复杂度相同；包含n个内部结点的红黑树的高度是o(logn); TreeMap 是一个红黑树的实现，能保证插入的值保证排序

STL和linux多使用红黑树作为平衡树的实现：

如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。

其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。

查找总结

既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。二叉排序树查找，最优二叉树查找，键树查找，哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存，若动态变化则可以添加在表的尾部（非顺序结构），时间复杂度是O(1)，查找复杂度为O(n)；若每个表内部为顺序结构，则可用二分法将查找时间复杂度降至O(logn)，但同时动态变化复杂度则变成O(n)；顺序法是挨个查找，这种方法最容易实现，不过查找时间复杂度都是O(n)，动态变化时可将保存值放入线性表尾部，则时间复杂度为O(1)；二分法是基于顺序表的一种查找方式，时间复杂度为O(logn)；通过哈希函数将值转化成存放该值的目标地址，O（1）

二叉树的平均查找长度为O(log2n)——O(n).二叉排序树的查找效率与二叉树的高度有关，高度越低，查找效率越高。二叉树的查找成功的平均查找长度ASL不超过二叉树的高度。二叉树的高度与二叉树的形态有关，n个节点的完全二叉树高度最小，高度为[log2n]+1,n个节点的单只二叉树的高度最大，高度为n，此时查找成功的ASL为最大(n+1)/2，因此二叉树的高度范围为[log2n]+1——n.

链式存储不能随机访问，必须是顺序存储

B_树的B+树

B_树

B-树就是B树。m阶B_树满足或空，或为满足下列性质的m叉树：

树中每个结点最多有m棵子树

根结点在不是叶子时，至少有两棵子树

除根外，所有非终端结点至少有⎡m/2⎤棵子树

有s个子树的非叶结点具有 n = s-1个关键字，结点的信息组织为:(n,A0,K1,A1,K2,A2 … Kn，An)。这里：n为关键字的个数，ki（i=1,2,…,n)为关键字，且满足Ki小于Ki+1,，Ai(i=0,1,..n)为指向子树的指针。

所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。

关键字集合分布在整颗树中

任何一个关键字出现且只出现在一个结点中

搜索有可能在非叶子结点结束

其搜索性能等价于在关键字全集内做一次二分查找

只适用于随机检索，不适用于顺序检索。

有结点的平衡因子都为零

M阶B-树中含有N个关键字，最大深度为log⎡m/2⎤(n+1)/2+2

B_树中结点的插入

m代表B_树的阶，插入总发生在最低层

插入后关键字个数小于等于 m-1,完成。

插入后关键字个数等于m,结点分裂，以中点数据为界一分为二，中点数据放到双亲结点中。这样就有可能使得双亲结点的数据个数为m,引起双亲结点的分裂，最坏情况下一直波及到根，引起根的分裂——B_树长高。

3阶B_树的插入。每个结点最多3棵子树，2个数据；最少2棵子树，1个数据。所以3阶B_树也称为2-3树。

B_树中结点的删除

删除发生在最底层

被删关键字所在结点中的关键字数目大于等于 m/2 ，直接删除。

删除后结点中数据为⎡m/2⎤-2，而相邻的左（右）兄弟中数据大于⎡m/2⎤-1，此时左（右兄弟）中最大（小）的数据上移到双亲中，双亲中接（靠）在它后（前）面的数据移到被删数据的结点中

其左右兄弟结点中数据都是⎡m/2⎤-1，此时和左（右）兄弟合并，合并时连同双亲中相关的关键字。此时，双亲中少了一项，因此又可能引起双亲的合并，最坏一直到根，使B-树降低一层。

删除不在最底层

在大于被删数据中选最小的代替被删数据，问题转换成在最底层的删除

B+树

在实际的文件系统中，用的是B+树或其变形。有关性质与操作类似与B_树。

差异：

有n棵子树的结点中有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

所有叶子结点中包含全部关键字信息，及对应记录位置信息及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)

所有非叶子为索引，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B树的非终节点也包含需要查找的有效信息)

非叶最底层顺序联结，这样可以进行顺序查找

B+特性

所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

不可能在非叶子结点命中

非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层

更适合文件索引系统

B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)

查找过程

在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找；

在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；

若在结点内查找时，给定值≤Ki， 则应继续在 Ai 所指子树中进行查找

插入和删除的操作：类似于B_树进行，即必要时，也需要进行结点的“分裂”或“合并”。

为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引？

B+tree的磁盘读写代价更低

B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

B+tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B树和B+树都是平衡的多叉树。B树和B+树都可用于文件的索引结构。B树和B+树都能有效的支持随机检索。B+树既能索引查找也能顺序查找.

哈希表

在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较，一次存取就能得到元素。

哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系。是从关键字空间到存储位置空间的一种映象。

哈希表——应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。

Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。

更适合查找，不适合频繁更新

Hash表等查找复杂依赖于Hash值算法的有效性，在最好的情况下，hash表查找复杂度为O(1)。只有无冲突的hash_table复杂度才是O(1)。一般是O(c)，c为哈希关键字冲突时查找的平均长度。插入，删除，查找都是O(1)。平均查找长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大

由于冲突的产生，使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。

根据抽屉原理，冲突是不可能完全避免的，所以，选择好的散列函数和冲突处理方法：

构造一个性能好，冲突少的Hash函数

如何解决冲突

常用的哈希函数

直接定址法。仅适合于：地址集合的大小 == 关键字集合的大小

数字分析法。对关键字进行分析，取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

平方取中法。以关键字的平方值的中间几位作为存储地址。

折叠法。将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。移位叠加/间界叠加。适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况。

除留余数法。取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，p<=m。

随机数法。取关键字的伪随机函数值作哈希地址，即H(key)=random(key)，适于关键字长度不等的情况。

冲突解决

开放定址法。当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列。缺点：删除：只能作标记，不能真正删除；溢出；载因子过大、解决冲突的算法选择不好会发生聚集问题。要求装填因子α较小，故当结点规模较大时会浪费很多空间。

线性探测再散列：di=1，2，3，…，m-1

二次探测再散列：di=12,-12,22,-22,…，±k2（k<=m/2）

伪随机探测再散列: di为伪随机数序列

链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。一旦发生冲突，在当前位置给单链表增加结点就行。

其他方法：再哈希法、建立公共溢出区

在用拉链法构造的散列表中，删除结点的操作易于实现。拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间。由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况。拉链法解决冲突时，需要使用指针，指示下一个元素的存储位置

开哈希表–链式地址法;闭哈希表–开放地址法.开哈希和闭哈希主要的区别在于，随着哈希表的密集度提高，使用闭哈希时，不仅会与相同哈希值的元素发生冲突，还容易与不同哈希值的元素发生冲突；而开哈希则不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长度不会增长。

设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n*(n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n*(n+1)/2次探测

Hash查找效率：装填因子=表中记录数/表容量

有B+Tree/Hash_Map/STL Map三种数据结构。对于内存中数据，查找性能较好的数据结构是Hash_Map，对于磁盘中数据，查找性能较好的数据结构是B+Tree。Hash操作能根据散列值直接定位数据的存储地址，设计良好的hash表能在常数级时间下找到需要的数据，但是更适合于内存中的查找。B+树是一种是一种树状的数据结构，适合做索引，对磁盘数据来说，索引查找是比较高效的。STL_Map的内部实现是一颗红黑树，但是只是一颗在内存中建立二叉树树，不能用于磁盘操作，而其内存查找性能也比不上Hash查找。