数据结构与算法：第九章 查找技术详解
该思维导图总结了第九章查找算法的知识点，涵盖静态查找表（顺序查找、折半查找、静态树表查找、索引顺序表查找）和动态查找表（二叉排序树、平衡二叉树、B树、B+树、键树）以及哈希表。 重点介绍了各种查找方法的算法流程、时间复杂度、适用场景及优缺点，并对哈希函数的构造方法和冲突处理策略进行了详细阐述，最终旨在全面理解和掌握各种查找算法的原理和应用。
源码
# 数据结构与算法
## 9.1 静态查找表
### 9.1.1 顺序表的查找
- 流程
- 逐个比较元素
- 结束条件
- 时间复杂度
- 最坏 O(n)
- 最好 O(1)
- 适用场景
- 数据量小
- 数据无序
- 局限性
- 低效
- 不适合大规模数据
### 9.1.2 有序表的查找
- 折半查找
- 步骤
- 选择中间元素
- 比较和调整范围
- 性能优势
- 时间复杂度 O(log n)
- 前提条件
- 表必须有序
- 局限性
- 插入和删除效率降低
### 9.1.3 静态树表的查找
- 构建思路
- 分类整理数据
- 使用树结构
- 改进方式
- 基于二叉排序树
- 优化原理
- 快速定位数据
### 9.1.4 索引顺序表的查找
- 建立索引
- 索引的结构与功能
- 数据块划分
- 分块查找流程
- 先索引后块内查找
- 提高效率策略
- 优化索引结构
- 选择合适的分块大小
## 9.2 动态查找表
### 9.2.1 二叉排序树和平衡二叉树
- 二叉排序树
- 定义
- 特性：节点左小右大
- 操作
- 插入：自上而下
- 删除：保持二叉排序特性
- 平衡二叉树
- 特性
- 调整机制
- 旋转调整
### 9.2.2 B_树和 B + 树
- B_树
- 特征
- 多叉树结构
- 自平衡性
- 节点存储
- 数据与指针存储
- 查找过程
- B + 树
- 特点
- 所有值在叶子节点
- 适用场景：数据库索引
- 多级索引优势
### 9.2.3 键树
- 概念与应用
- 字符串查找
- 适用场景：字典树
- 存储结构设计
- 节点表示字符
- 子节点的表示
- 操作要点
- 查找：逐字符比较
- 插入与删除：调整结构
## 9.3 哈希表
### 9.3.1 什么是哈希表
- 原理
- 哈希函数
- 直接定位数据
- 对比传统查找表
- 效率更高
- 时间复杂度 O(1)
- 理想特点
- 完全无冲突
- 高效查找
### 9.3.2 哈希函数的构造方法
- 直接定址法
- 线性关系
- 除留余数法
- 取模运算
- 模数选择方法
- 数字分析法
- 平方取中法
- 特点与应用
### 9.3.3 处理冲突的方法
- 开放定址法
- 线性探测
- 二次探测
- 链地址法
- 链表构建
- 适应性强
- 再哈希法
- 多重哈希函数
- 解决冲突的思路
### 9.3.4 哈希表的查找及其分析
- 查找过程
- 哈希函数计算
- 冲突处理方式
- 平均查找长度分析
- 影响因素：哈希函数、冲突处理
- 性能优化方向
- 高效的哈希函数设计
- 冲突处理策略优化
图片
