408

数据结构 7 查找

查找的基本概念

1. 查找表 用于查找的数据集合，静态为不删减，动态增加删除

2. 平均查找长度ASL 需要比较的平均次数

顺序查找

顺序表，链表都适用，正常查找 o(n)

优化 有序，减少失败ASL；将概率大的数据放前面

折半查找

二分查找 o(log2 n)

1. 失败条件 L指针大于H

2. 判定树 平衡树，向上向下取整决定左右子树的大小关系

   折半查找次数不超过树高，适合有序顺序存储

分块查找

块内无序，块间有序

1. ASL=索引ASL+块内ASL

2. 最小ASL，块数平方为字数

二叉排序树BST

左<中<右，中序遍历为顺序数列，可以是空，最差o(n)，最好o(log2 n)，适合动态查找

1. 插入 插入访问失败最后节点的孩子，不可相同

2. 删除 叶节点直接删除；只有一颗子树直接添加；两颗子树找前驱或后继

！平衡二叉树AVL

左右高度差不超过1，查找o(log2 n)

AVL插入

根据插入点后最小不平衡树

1. LL 右旋转

2. RR 左旋转

3. LR 左右

4. RL 右左

根据情况将子树迁移

构造时按照插入处理

AVL删除

删除操作先按照BST处理，再按照插入处理，再继续检查是否传递不平衡

红黑树RBT

左中右，根叶黒，无二红，黑数同，查找o(log2 n)

引入了NULL作为叶子，黒

L最大不超过L最小的二倍

RBT插入

只需要关注插入节点的叔节点

1. 叔节点黒 根据AVL插入处理，一次的父爷变换，两次的爷孙变换

2. 叔节点红 爷父叔变换，爷作为新节点检查

RBT删除

查找o(log2 n)，先按照BST处理，再进行变换

408

数据结构 6.4 图的应用

最小生成树

1. Prim算法 从一个点出发寻找权值小的下一点

   时间复杂度V^2

2. Kruskal算法 并查集寻找最短边的集合

   时间复杂度e log e

最短路径

1. BFS 无权图

2. Djikstra算法 单源有权图 动态规划 加入后比较最短边

   时间复杂度V^2 边上有负值不适用

3. Floyd算法 任意两点 顺序作为中间点比较

   时间复杂度V^3 负值环路不适用

有向无环图DAG

用来储存算术表达式，压缩空间

拓扑排序

1. AOV网 节点代表活动

2. 拓扑排序 先进行的活动必在前，无关系的点任意

   无环必有拓扑排序 起始有入度，时间复杂度 V+E或V^2 三角矩阵必存在拓扑排序

关键路径

1. AOE网 边代表活动

2. 关键路径 时间最长的路径

   先画出关键路径再计算最迟时间

This is my first blog in 2024Fall