数据结构简介（下）
树（续）
⼆叉树
⼆叉排序树
⼆叉排序树，⼜叫⼆叉查树，它或者是⼀棵空树；或者是具有以下性质的⼆叉树：
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。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。