导图社区 ⑦查找
24自用408数据结构，分享了顺序查找、折半查找（二分查找）、分块查找（索引顺序查找）、树型查找、B树和B+树、散列表的知识。
x4毛中特政治背诵，毛泽东思想和中国特色社会主义理论体系，这是两个既相互独立又紧密联系的理论体系，是中国共产党在不同历史时期的思想结晶和伟大创造。
③存储系统，介绍了存储器、主存储器与CPU的连接、外部存储器、cache、虚拟存储器、Cache行内容的知识，快来看看吧！
24自用408计算机组成原理，分享了数制与编码、运算方法和运算电路、浮点数的表示与运算的知识，欢迎大家学习。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
马克思主义原理
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
查找
概念
查找
静态查找表
适合顺序查找、折半查找、散列查找
动态查找表
适合二叉排序树、散列查找
平均查找长度ASL
所有查找过程中进行关键字比较次数的平均值
衡量查找算法最重要的指标
顺序查找
一般线性查找
查找成功
i为定位到第i个元素
当P＝1/n时
ASL＝(n+1)/2
查找失败
ASL＝n+1
特点
缺点
n比较大的时候，平均查找长度较大，效率低
优点
对数据元素的存储无要求，顺序存储或链式存储皆可
有序表的顺序查找
对线性的链表只能进行顺序查找
折半查找(二分查找)
仅适用于有序的顺序表
每一次查找取中间位置
判定树
平衡二叉树，也是二叉排序树唯一
mid向下取整
右子树结点数-左子树结点树＝0或1
mid向上取整
左子树结点数-右子树结点树＝0或1
h是树高，元素个数为n时树高为
最多查询次数为max(h)
时间复杂度
O(log2n)
要求线性表必须具有随机存取的特性
仅适合顺序存储结构，且有序
分块查找(索引顺序查找)
吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
将查找表分为若干个子块
块内元素无序
块间有序，即第一个块中最大关键字小于第二个块中所有记录的关键字
建立索引表
有每块的最大关键字或最小关键字
第一个元素的地址
按关键字顺序有序排列
步骤
在索引表中确定待查记录的所在块
顺序查找或折半查找
在块中顺序查找
ASL
将长度为n的查找表均匀分为b块，每块有s个记录
在索引表和块内均采用顺序查找
在索引表采用折半查找
low＞high跳出
且在low所指块中查找
low超出索引表范围，查找失败
树型查找
二叉排序树BST
左子树结点值＜根结点值＜右子树结点值
则中序遍历可得递增序列
插入的结点一定是叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子
删除结点z
1| 叶结点
直接删除
2| 有一棵子树
让子树代替z
3| 有左右两棵子树
让z的中序遍历的直接前驱或直接后继代替z，再从原来的二叉排序树中删除代替者
和B树的非叶结点删除作对比
查找效率
左右子树高度之差不超过1，即为平衡二叉树
单支树
O(n)
和二分查找对比区别
二分查找判定树唯一，二叉排序树的查找不唯一
插入和删除
二叉排序树
只需修改指针即可
O(log2'n)
二分查找
静态查找表(只查，不修改数据)
采用顺序表作为其存储结构
采用二分法查找
选择二叉排序树作为逻辑结构
平衡二叉树AVL
任意结点的左、右子树高度差的绝对值不超过1
即平衡因子为-1、0和1
插入
导致不平衡后，调整最小不平衡二叉树
LL平衡旋转(右单旋转)
RR平衡旋转(左单旋转)
LR平衡旋转(先左后右双旋转)
RL平衡旋转(先右后左双旋转)
删除w
从结点开始，向上回溯，找到第一个不平衡结点z；y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点
情况
y是左孩子，x是y的左孩子(LL，右单旋转)
y是左孩子，x是y的右孩子(LR，先左后右双旋转)
y是右孩子，x是y的右孩子(RR，左单旋转)
y是右孩子，x是y的左孩子(LL，先右后左双旋转)
含有n个结点的平衡二叉树的最大深度为O(log2'n)
假设以Nh表示深度为h的平衡树中含有的最少结点数
红黑树
相关概念
黑高
一个结点的黑高：从某结点出发(不含该结点)到达任一空叶结点的路径上黑结点总数
叶结点
在RBT中，叶结点通常指失败结点(又名：空叶结点/NULL结点/外部结点)
定义
左根右
根叶黑
不红红
黑路同
性质
从根结点到叶结点的最长路径不大于最短路径的2倍
有n个内部结点的红黑树高度h≤2log(n+1)
推论：若黑高为h，则内部结点至少为2′h-1
黑满二叉树
黑结点数量至少为h/2
插入
新结点为根，则染黑
新结点非根则染红
插入后违反“不红红” 看叔脸色
黑叔：旋转+换色
LL，右单旋，父代爷，父爷换色
RR，左单旋，父代爷，父爷换色
LR，先左后右双旋，儿代爷，儿爷换色
RL，先右后左单旋，儿代爷，儿爷换色
红叔：换色+变新
叔父爷换色，爷为新结点
B树和B+树
B树 多路平衡查找树
m阶B树定义
树中每个结点至多有m棵子树，即至多含有m-1个关键字
若根结点不是终端结点，至少有两棵子树
除根结点外的所有非叶结点至少有m/2(向上取整)，即至少含有m/2(向上取整)-1个关键字
“有一半多”
根结点
子树数量[2，m]
关键字数[1，m-1]
其他结点
对任一结点，其所有子树的高度相同
关键字的值
左中右
查找
在B树中找结点
在磁盘上
在结点内找关键字
在内存中
最低高度
每个结点最多有m棵子树，m-1个关键字
最高高度
每个结点中的关键字个数最少
此高度不包括叶子结点层
定位
找到最底层中的某个叶结点
插入后，关键字数个数小于m，直接插入
大于m-1时，对结点进行分裂
分裂
1| 插入后，找到中间位置m/2(向上取整)将其分裂成两部分，
2| 中间位置的关键字插入原结点的父结点
3| 若导致父结点也超出了上限，则继续分裂
4| 若分裂至根结点，则导致树的高度+1
删除
若被删关键字不在终端结点(最底层非叶结点)
用直接前驱代替
当前关键字最左侧指针最右下关键字
用直接后继代替
当前关键字最右侧指针最左下关键字
被删关键字在终端结点
直接删除
兄弟够借
兄弟不够借
B+树
应数据库需求出现的一种B树的变形
条件
每个分支结点最多有m棵子树
非叶根结点至少有两棵子树，其他每个分支至少有m/2(向上取整)棵子树
结点的子树个数与关键字个数相等
所有叶结点包含全部关键字及指向相应记录的指针
叶结点中将关键字按大小顺序排列
相邻叶结点按大小顺序相互链接起来
所有分支结点仅包含子结点的最大值及指向其子结点的指针
与B树区别
关键字数与子树数，都至少要子树数量：
B树n个关键字n+1棵子树
B+树n个关键字n棵子树
结点中关键字数范围
B树
B+树
B+树中，叶结点包含信息，所有非叶结点仅起索引作用
B+树中，叶结点包含了全部关键字
B树
B树中，叶结点终端结点和其他结点的关键字不重复
B树不能顺序查找，B+树可以顺序查找，两者都能随机查找
考题注意： 1.注意是求关键字数还是结点数
散列表 (空间换时间)
概念
散列表建立了关键字和存储地址之间的一种直接映射关系
同义词
发生碰撞的不同关键字
根据关键字直接访问的数据结构
散列函数的构造方法
直接定址法
直接取关键字的某个线性函数值为散列地址
散列函数
H(key)＝key或H(key)＝a×key+b
特点
简单，无冲突
适合关键字分布的基本连续的情况
若分布不连续，空位较多
例子
除留余数法
设列表长m，取一个等于m或最接近m的质数(素数)p，利用散列函数转换成散列地址
散列函数
H(key)＝key%p
最简单，最常用
p的取值，需使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而减少冲突的可能性
数字分析法
选取数码分布较为均匀的若干位作为散列地址
适合已知的关键字集
选取手机号码后四位作为散列地址
平方取中法
取关键字的平方值的中间几位作为散列地址
散列地址与关键字的每位都有关系
例子
身份证号
处理冲突的方法
开放定址法
线性探测法
冲突发生时，顺序查找下一个单元，直至找到一个空闲单元
di＝0，1，2，3.....，m-1
特点
大量元素在相邻的散列地址上“堆积”起来，大大降低了查找效率
关键字可能与同义词发生冲突，也可能与非同义词
在不删关键字的情况下，查找遇到表空为查找失败
平方探测法
不能探测到散列表上所有单元，但至少能探测到一半单元
列表长度必须是可以表示成4k+3的素数
可以探测到所有元素
di＝0方，1方，-1方......k方，-k方
k≤m/2
再散列法
Hi＝RHi(key)
当一个散列函数发生冲突时，使用另一个散列函数计算散列地址
伪随机序列法
di＝伪随机数序列
删除某元素，需标记该单元
Hi＝(H(key)+di)%m
m为表长
拉链法 链地址法
同义词串成一个链表
散列查找及性能分析
装填因子
表现表满的程度，越满冲突越大
