ASL = 1/2 ASL_success + 1/2\*ASL_failed = 3/4\*(n+1)
- 折半查找（Binary Search， 二分查找）
- 高效率的查找方案，前提条件是查找表中的记录有序
- 二分查找的路径会得到一个二叉树，称为判定树。n个结点的判定深度是log2n+1。
- 分块查找（Blocking Search，索引顺序查找）
-
- 将查找表分为几块，块间有序，块内无序
-
- 在查找表的基础上附加一个索引表，索引表按关键字有序 查找方法的比较
-
| 查找方法 | 顺序查找 | 二分查找 | 索引查找 |
|---|---|---|---|
| ASL | 最大 | 最小 | 中等 |
| 表结构 | 有序表、无序表 | 有序表 | 分块有序表 |
| 存储结构 | 顺序存储结构线性链表 | 顺序存储结构 | 顺序存储结构线性链表 |
- 具有以下特性的二叉树或空树
- 每个结点都有一个作为搜索依据的关键字，所有结点的关键字互不相同
- 左子树上的所有结点的关键字都小于根节点关键字
- 右子树上的所有结点的关键字都大于根节点关键字
- 左右子树也是二叉搜索树
- 特性：
- 左子树<根结点<右子树
- 如果对一棵二叉搜索树中序遍历，可以得到一个从小到大的结果
- 搜索方法：
- 从根节点开始，沿某一个分支逐层向下进行比较判等的过程
- 如果根指针为null，搜索失败；否则用给定值x与根节点判断
- 若给定x等于根节点，搜索成功
- 若给定x小于根节点，搜索失败，转向左子树；反之转向右子树
- 插入算法：
- 检查该值是否已经存在
- 如果查找成功，拒绝插入
- 如果查找失败，将给定值x插入到搜索停止的地方
- 检查该值是否已经存在
- 删除算法：
- 删除叶结点
- 被删结点右子树为空，拿它左子女顶替；反之亦然
- 被删结点左右都不为空，判定后向上平移
- 具有以下特性的二叉搜索树
- 左子树和右子树的高度差绝对值不超过1
- 平衡因子bf（-1,0,1）
- 如果是一棵AVL树，高度和ASL都可以保持O(log2n)
- 平衡化旋转
- 单旋转（左旋和右旋）
- 双旋转（左平衡和右平衡）
- 每插入一个新结点的时候，AVL树的相关结点的平衡状态将会变化，因此插入结点后，需要从插入位置沿根的路径回溯，检查各结点的平衡因子。
- 如果在某一结点发现不平衡，停止回溯。从不平衡的结点开始，沿刚才回溯路径取下两层结点等待操作
- 如果在一条直线上：单旋转
- 右单旋转
- 左单旋转
- 如果在一条折线上：双旋转
- 先左后右双旋转
- 先右后左双旋转
- 如果在一条直线上：单旋转
- B树是平衡的多路查找树，满足以下特性：
- 每个结点至多有m可子树
- 若根节点不是叶子，至少有两棵子树
- B树查找分析
- 在B树中查找结点（磁盘进行，耗时）
- 在结点中找关键字（内存进行）
- B树上进行查找的效率由待查关键字所在结点的层次数l决定
- B树的插入
- m阶B树的结点分裂
- B+树是B树的特殊情形，不同点在：
- 所有关键字都存放叶结点，上层的非叶结点都是子树中最小（大）的关键字的副本
- 叶结点包含了全部关键字以及指向相应数据记录存放的地址指针，叶结点本身按照关键字从小到达排序
- B+树的分类
- 按照“最大关键字复写”原则组织
- 按照“最小关键字复写”原则组织
- B+树的插入
- 只能在叶结点插入，没插入一个需要判断是否超过范围m。
- 基本概念
- 理想的搜索方法是可以不经过比较，一次直接从字典中获取要搜索的元素
- 散列函数、散列表
- 使用散列方法不需要进行多次关键字的比较，可以直接到达有此关键字的表项的实际存放地址
- 通过散列函数的计算得到了同一个散列地址，称这些产生冲突的散列地址相同的不同关键字为同义词
- 散列函数
- 要求：
- 运算简单
- 定义域需要包含需要存储的全部关键字
- 计算出来的地址地址应能均匀分布在整个地址空间中
- 生成方法：
- 直接定址
- 数字分析
- 除留余数法
- 平方取中法
- 折叠法
- 要求：