树（续）

二叉树

二叉排序树

二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树

• 二叉排序树的建立
  集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我们的二叉排序树中去存储，如果对我们创建好的二叉排序树进行中序搜索的话，输出的结果就是上面集合的有序序列。下方就是我们二叉排序树从无到有的完整创建过程。

1. 在初始化状态下我们二叉排序树的根节点为空，我们依次将集合中的元素通过搜索插入到二叉排序树中合适的位置。
2. 首先在二叉排序中进行搜索62的位置，树为空，所以将62存入到二叉排序树的根节点中，及root=(62)。
3. 从集合中取出88，然后查找我们的二叉排序树，发现88大于我们的根节点62，所以将88插入到62节点的右子树中，即(62)->rightChild=(88)。
4. 从集合中取出58，然后从根节点开始查找我们现有的二叉排序树，发现55<62，将55作为62的左结点，即(62)->leftChild=(55)。
5. 从集合中取出47，然后对二叉排序树进行搜索，发现47<55, 所以(55)->leftChild=(47)。
6. 从集合中取出35，再次对二叉排序树进行搜索，发现35又小于47，所以(47)->leftChild=(35)。
7. 从集合中取出73，再次对二叉排序树进行搜索，发现62<73<88, 所以有(88)->leftChild=(73)。
   以此类推，要做的事情就是不断从集合中取值，然后对二叉排序树进行查找，找到合适的插入点，然后将相应的节点进行插入，具体步骤就不做过多赘述了。

• 二叉排序树节点的删除
  冒泡手法

二叉平衡树

• 二叉排序树的结点删除：
  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)是右子树的节点数量。

• eg:
  镜像二叉树
  有限单词拼写错误检查
  二叉树中和为某一值的路径
  二叉搜索树第k个结点
  按之字顺序打印二叉树

图(续)

图的存储形式

1. 邻接矩阵和加权邻接矩阵
   无权有向图：出度: i行之和；入度: j列之和。
   无权无向图：i结点的度: i行或i列之和。
   加权邻接矩阵：相连为w，不相连为∞
2. 邻接表
   用顶点数组表、边（弧）表表示该有向图或无向图
   顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n
   边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。
   n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n(n-1)/2条边，此时为完全无向图，而在邻接表中每条边存储两次，所以有n(n-1)个结点

图的遍历

深度优先搜索利用栈，广度优先搜索利用队列

环

环的检测：黑白灰算法，死锁检测（拓扑排序）

• 在有向图中选一个没有前驱的顶点且输出之
• 从图中删除该顶点和所有以它为尾的弧
• 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）

最短路径

贪心算法：Dijkstra算法

最小生成树

贪心算法：Prim算法、Kruskal算法

AOE网：

带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

1. 事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。
2. 事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。
3. 活动ai由弧<j,k>表示，持续时间记为 dut<j,k>,则有:
   活动的最早开始时间：e(i)=ve(j)
   活动的最迟开始时间：l(i)=vl(k) - dut(<j , k >)
   活动余量：l(i)-e(i)的差
4. 关键活动：活动余量为0的活动
5. 关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。关键活动一定位于关键路径上。
6. 关键活动组成了关键路径，关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间，关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加。关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期，因为其他关键路径没有变化。任何一条关键路径上的关键活动变长了，都会使这条关键路径变成更长的关键路径，并且导致其他关键路径变成非关键路径（如果关键路径不唯一）。关键活动不按期完成就会影响整个工程的完成时间。所有的关键活动提前完成,那么整个工程才会提前完成。关键路径也不能任意缩短，一旦缩短到一定程度，该关键活动可能变成非关键活动了。

查找

顺序查找、折半查找、索引查找、分块查找 vs 二叉排序树查找，最优二叉树查找，键树查找，哈希表查找

• tips:
  时间：顺序查找最差，二分最好，分块介于两者之间
  空间：分块最大，需要增加索引数据的空间
  顺序查找对表没有特殊要求
  分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。
  二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。
  在表不大时，一般直接使用顺序查找。
  既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。
  二叉排序树查找，最优二叉树查找，键树查找，哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存，若动态变化则可以添加在表的尾部（非顺序结构），时间复杂度是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.
  链式存储不能随机访问，必须是顺序存储

  
  
  一种二叉平衡树

哈希表

在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较，一次存取就能得到元素。
哈希函数——在记录的关键字与记录的存储位置之间建立的一种对应关系。是从关键字空间到存储位置空间的一种映象。
哈希表——应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。
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查找效率：装填因子=表中记录数/表容量

排序

内部排序：全部数据可同时放入内存进行的排序。
外部排序：文件中数据太多，无法全部调入内存进行的排序。

内部排序

• 插入类：

1. 直接插入排序。最坏情况是数据递减序，数据比较和移动量最大，达到O(n2)，最好是数据是递增序，比较和移动最少为O(n)。趟数是固定的n-1，即使有序，也要依次从第二个元素开始。排序趟数不等于时间复杂度。
2. 折半插入排序 。由于插入第i个元素到r[1]到r[i-1]之间时，前i个数据是有序的，所以可以用折半查找确定插入位置，然后插入。
3. 希尔排序。缩小增量排序。5-3-1。在实际应用中，步长的选取可简化为开始为表长n的一半（n/2），以后每次减半，最后为1。插入的改进，最后一趟已基本有序，比较次数和移动次数相比直接插入最后一趟更少

• 交换类：

1. 冒泡排序。O(n2)通常认为冒泡是比较差的，可以加些改进，比如在一趟中无数据的交换，则结束等措施。
   在数据已基本有序时，冒泡是一个较好的方法
   在数据量较少时（15个左右）可以用冒泡
2. 快速排序。
   时间复杂度。最好情况：每次支点总在中间，O(nlog2n)，平均O(nlog2n)。最坏，数据已是递增或递减，O(n2)。pivotkey的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。越无序越快。
   空间复杂度。需栈空间以实现递归，最坏情况：S(n)=O(n)；一般情况：S(n)=O(log2n)
   在序列已是有序的情况下，时间复杂度最高。原因：支点选择不当。改进：随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点，通常可以避免最坏情况。所以，快速排序在表已基本有序的情况下不合适。
   在序列长度已较短时，采用直接插入排序、起泡排序等排序方法。序列的个数通常取10左右。

• 选择类排序：

1. 简单选择排序。O(n2)。总比较次数n(n-1)/2。（类似冒泡排序）
2. 堆排序。建堆 O(n)，筛选排序O(nlogn)。找出若干个数中最大/最小的前K个数，用堆排序是最好。小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于[n/2]。时间复杂度不会因为待排序序列的有序程度而改变，但是待排序序列的有序程度会影响比较次数。
3. 归并排序。时间：与表长成正比，若一个表表长是m，另一个是n，则时间是O(m+n)。单独一个数组归并，时间：O(nlogn)，空间：O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。归并排序算法比较占用内存，但却是效率高且稳定的排序算法。在外排序中使用。归并的趟数是logn。
4. 基数排序。在一般情况下，每个结点有 d 位关键字，必须执行 t = d次分配和收集操作。分配的代价：O(n)；收集的代价：O(rd) （rd是基数）；总的代价为：O( d ×(n + rd))。适用于以数字和字符串为关键字的情况。
5. 枚举排序，通常也被叫做秩排序，比较计数排序。对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置，时间复杂度为O(n2)

• 排序算法的一些特点：

1. 堆排序、冒泡排序、快速排序在每趟排序过程中,都会有一个元素被放置在其最终的位置上。
2. 有字符序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ ,新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}，是快速排序算法一趟扫描的结果。(拿Q作为分割点,快速排序一轮。二路归并，第一趟排序，得到 n / 2 个长度为 2 的各自有序的子序列，第二趟排序，得到 n / 4 个长度为 4 的各自有序的子序列H Q C Y A P M S D R F X。如果是快速排序的话，第一个元素t将会被放到一个最准确的位置，t前的数均小于t，后面的数均大于t。希尔排序每个小分组内将会是有序的。堆排序，把它构成一颗二叉树的时候，该堆要么就是大根堆，要么就是小根堆，第一趟Y排在最后；冒泡，那么肯定会有数据下沉的动作，第一趟有A在第一位。)
3. 在文件"局部有序"或文件长度较小的情况下,最佳内部排序的方法是直接插入排序。（归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为O(nlog2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，即n-1趟比较的时间复杂度由O(n^2)降至O(n)。在待排序的元素序列基本有序或者每个元素距其最终位置不远也可用插入排序，效率最高的排序方法是插入排序）
4. 排序趟数与序列的原始状态有关的排序方法是优化冒泡和快速排序法。(插入排序和选择排序不管序列的原始状态是什么都要执行n-1趟，优化冒泡和快排不一定。仔细理解排序的次数和比较次数的区别)
5. 不稳定的排序方法：快排，堆排，希尔，选择
6. 要与关键字的初始排列次序无关,那么就是最好、最坏、一般的情况下排序时间复杂度不变, 总共有堆排序,归并排序,选择排序,基数排序.
   快速排序、Shell 排序、归并排序、直接插入排序的关键码比较次数与记录的初始排列有关。折半插入排序、选择排序无关。(直接插入排序在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；折半插入排序，比较次数是固定的，与初始排序无关；快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数，但快排平均比较次数最小；归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关)
7. 精俭排序，即一对数字不进行两次和两次以上的比较，插入和归并是“精俭排序”。插入排序，前面是有序的，后面的每一个元素与前面有序的元素比较，比较过的就是有序的了，不会再比较一次。归并每次合并后，内部都是有序的，内部的元素之间不用再比较。选择排序，每次在后面的元素中找到最小的，找最小元素的过程是在没有排好序的那部分进行，所有肯定会比较多次。堆排序也需比较多次。

外部排序

生成合并段（run）：读入文件的部分记录到内存－>在内存中进行内部排序－>将排好序的这些记录写入外存，形成合并段－>再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。

外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文件。

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序

不管初始序列是否有序, 冒泡、选择排序时间复杂度是O(n^2),归并、堆排序时间复杂度是O(nlogn）

外部排序的总时间 = 内部排序（产出初始归并段）所需时间 + 外存信息读取时间 + 内部归并所需的时间

外排中使用置换选择排序的目的,是为了增加初始归并段的长度。减少外存读写次数需要减小归并趟数

根据内存容量设若干个输入缓冲区和一个输出缓冲区。若采用二路归并，用两个输入缓冲。

归并的方法类似于归并排序的归并算法。增加的是对缓冲的监视，对于输入，一旦缓冲空，要到相应文件读后续数据，对于输出缓冲，一旦缓冲满，要将缓冲内容写到文件中去。

外排序和内排序不只是考虑内外排序算法的性能，还要考虑IO数据交换效率的问题，内存存取速度远远高于外存。影响外排序的时间因素主要是内存与外设交换信息的总次数

例子

1. 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0
2. 逆序数
3. 加法的实现

4. 最大K个数

   
   
   some thoughts