远方的岛第五章 查找结构
type
status
date
slug
summary
tags
category
icon
password
5.1基本概念和术语
操作：查找、插入、删除，平均查找长度
分类：（查找方法取决于记录的键值/存储位置）基于关键字比较的查找/基于关键字存储位置的查找
（被查找的数据集合存储位置）外查找/内查找
（查找方法是否改变数据集合）静态查找/动态查找
5.2线性查找
5.3折半查找（二分查找）
只适用于静态查找
适用条件
非递归/递归
折半查找判定树：平衡二叉树
5.4分块查找——线性查找+折半查找
基本思想：均匀分块，块间有序，块内无序，建块索引
只适合静态查找
B
B
A
B
B
B A
AD
A
A
A
B
5.5二叉查找树BST、二叉搜索/分类/排序树
AVL树
AVL树的平衡化处理：找最小不平衡子树/若为整棵树则为沿路径与根节点相连的3个结点，调整
【一秒学会 平衡二叉树的调整，非标题党！不简单你打我！ （考研数据结构）】 https://www.bilibili.com/video/BV16m4y1F7do
C
AVL树的删除操作
C
A
C
A
A
C
C
B
B
D
5.7B-树和B+树
m-路查找树
B-树
插入：直接插入，关键字数超了把第m/2向上取整个元素拿上去
删除
【【数据结构】分享一个B树插入和删除的技巧】 https://www.bilibili.com/video/BV1yP411s7wh/
B-树的查找时间与高度和阶数直接有关
B+树：相对B-树更充分地利用了节点的空间，让查询速度更加稳定，接近于二分法查找
B
D
D
B 把题的意思理解明白
A 有公式
D
A
B
B
5.8散列技术
散列冲突、同义词
散列函数构造原则：计算简单、分布均匀
构造方法：直接定址法、质数除余法、平方取中法、折叠法、数字分析法、随机数法
冲突处理：开放定址法（线性探测（再散列）法c=1、线性探测补偿法、二次探测法、随机探测法）、带溢出表的内散列法、拉链法/链地址法
堆积现象
不成功比较次数：地址到第一个关键字为空的地址
B
A
A
D
D
D
D
C
C 散列表一定不要构建错
期末真题
2021
3
2020
2019
散列技术
2017
2016
B
B
5
2015
C 满二叉树
B
B
高度 阶数
线性查找和折半查找 根号n
Loading...