行业知识
408数据结构知识点——第七章 查找
文章目录
- 查找的基本概念
- 基本概念
- 对查找表的常见操作
- 查找算法的评价指标
- 顺序查找和折半查找
- 顺序查找
- 顺序查找的算法思想
- 顺序查找的实现
- 顺序查找的实现（哨兵）
- 查找效率分析
- 顺序查找的优化（对有序表）
- 顺序查找的优化（被查概率不相等）
- 折半查找
- 折半查找的算法思想
- 折半查找的实现
- 查找效率分析
- 分块查找
- 分块查找的算法思想
- 分块查找的实现
- 查找效率分析
- 树形查找
- 二叉排序树
- 二叉排序树的定义
- 二叉排序树的查找
- 二叉排序树的插入
- 二叉排序树的构造
- 二叉排序树的删除
- 查找效率分析
- 平衡二叉树
- 平衡二叉树的定义
- 平衡二叉树的插入
- 调整最小不平衡子树
- 查找效率分析
- 平衡二叉树的删除
- 红黑树
- 为什么要发明红黑树
- 红黑树的定义
- 结点的“黑高”
- 红黑树的性质
- 红黑树的查找
- 红黑树的插入
- 红黑树的删除
- B树和B+树
- 5叉查找树
- 如何保证查找效率
- B树
- B树的高度
- B树的插入
- B树的删除
- B+树
- B树和B+树对比
- 散列表
- 散列表、散列函数
- 冲突、同义词
- 如何减少冲突
- 如何减少冲突
- 散列函数的构造
- 除留余数法
- 直接定址法
- 数字分析法
- 平方取中法
- 处理冲突的方法
- 拉链法
- 开���定址法
注：内容参考王道2024考研复习指导以及《数据结构》
查找的基本概念
基本概念
查找 —— 在数据集合中寻找满⾜某种条件的数据元素的过程称为查找。
查找表（查找结构）—— ⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成。
关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。
对查找表的常见操作
- 查找符合条件的数据元素
- 插入、删除某个数据元素
只需进行操作1，为静态查找表，关注查找速度；
操作1、2都需要进行，为动态查找表，除了查找速度，也要关注插/删操作是否方便实现。
查找算法的评价指标
查找长度——在查找运算中，需要对比关键字的次数为查找长度
平均查找长度（ASL,Average Search Length）——所有查找过程中进行关键字的比较次数的平均值， A S L = ∑ i = 1 n P i C i ASL=\sum_{i=1}^{n}P_iC_i ASL=∑i=1nPiCi（通常认为查找任何一个元素的概率都相同）
顺序查找和折半查找
顺序查找
顺序查找的算法思想
顺序查找，也叫“线性查找”，通常用于线性表。
算法思想，从头到尾挨个查找。
顺序查找的实现
typedef struct{ ElemType *elem; int TalbeLen;}SSTable;int Search_Seq(SSTable ST,ELemType key){ int i; for(i=0;i ElemType *elem; int TalbeLen;}SSTable;int Search_Seq(SSTable ST,ELemType key){ ST.elem[0]=key; int i; for(i=ST.TableLen;ST.elem[i]!=key;i--); return i;} ElemType *elem; int TableLen;}SSTable;int Binary_Search(SSTable L,ElemType key){ int low=0,high=L.TableLen-1,mid; while(low mid=(low+high)/2; if(L.elem[mid]==key){ return mid; }else if(L.elem[i]key){ high=mid-1; }else { low=mid-1; } return -1; }}h5查找效率分析/h5 pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-250423013034555.png" //p p构造查找判定树/p p注：图中数字只是⼀个编号，并不是关键字的值/p pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-250423013034J3.png" //p ulli如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素。/lili如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等p折半查找的判定树中，若 m i d = ⌊ ( l o w + h i g h ) / 2 ⌋ mid=\lfloor (low+high)/2 \rfloor mid=⌊(low+high)/2⌋，则对于任何⼀个结点，必有:右⼦树结点数-左⼦树结点数=0或1/p p折半查找的判定树一定是平衡二叉树。/p p折半查找的判定树中，只有最下面一层是不满的，因此，元素个数为n时树高 h = ⌈ log 2 ( n + 1 ) ⌉ h=\lceil \log_2(n+1) \rceil h=⌈log2(n+1)⌉/p pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-250423013035934.png" //p p A S L 成功 = ( 1 ∗ 1 + 2 ∗ 2 + 3 ∗ 4 + 4 ∗ 4 ) / 11 ASL_{成功}=(1*1+2*2+3*4+4*4)/11 ASL成功=(1∗1+2∗2+3∗4+4∗4)/11=3/p p A S L 失败 = ( 3 ∗ 4 + 4 ∗ 8 ) 12 = 11 / 3 ASL_{失败}=(3*4+4*8)12=11/3 ASL失败=(3∗4+4∗8)12=11/3/p h4分块查找/h4 h5分块查找的算法思想/h5 p分块查找，又称索引顺序查找，算法过程如下：/p olli在索引表中确定待查记录所属的分块（可顺序、可折半）/lili在块内顺序查找/li/ol p注：若索引表中不包含⽬标关键字，则折半查找索引表最终停在 low>high，要在low所指分块中查找。“索引表”中保存每个分块的最大关键字和分块存储区间。
特点：块内无序，块间有序。
分块查找的实现
//索引表typedef struct{ ElemType maxValue; int low,high;}Index;//顺序表存储实际元素ElemTyee list[100];查找效率分析
假设，长度为n的查找表被均匀地分成b块，每块s个元素
设索引查找和块内查找的平均查找长度分别为 L I 、 L S L_I、L_S LI、LS，则分块查找地平均查找长度为 A S L = L I + L S ASL=L_I+L_S ASL=LI+LS
用顺序查找索引表，则 L I = 1 + 2 + . . . + b b = b + 1 2 , L S = 1 + 2 + . . . + s s = s + 1 2 L_I=\frac{1+2+...+b}{b}=\frac{b+1}{2},L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2} LI=b1+2+...+b=2b+1,LS=s1+2+...+s=2s+1
则 A S L = b + 1 2 + s + 1 2 = s 2 + 2 s + n 2 s ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s} ASL=2b+1+2s+1=2ss2+2s+n，当 s = n s=\sqrt{n} s=n 时， A S L 最小 = n + 1 ASL_{最小}=\sqrt n+1 ASL最小=n +1
用折半查找查索引表，则 L I = ⌈ log 2 ( b + 1 ) ⌉ , L S = 1 + 2 + . . . + s s = s + 1 2 L_I=\lceil \log_2(b+1) \rceil,L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2} LI=⌈log2(b+1)⌉,LS=s1+2+...+s=2s+1
则 A S L = ⌈ log 2 ( b + 1 ) ⌉ + s + 1 2 ASL=\lceil \log_2(b+1) \rceil +\frac{s+1}{2} ASL=⌈log2(b+1)⌉+2s+1
树形查找
二叉排序树
二叉排序树的定义
二叉排序树，又称二叉查找树（BST，Binary SearchTree）
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
- 左子树上所有结点的关键字均小于根结点的关键字
- 右子树上所有结点的关键字均大于根结点的关键字
- 左子树和右子树又各是一棵二叉排序树
即，左子树结点值 int key; strcut BSTNode *lchild,rchild;}BSTNode,*BSTree;//非递归BSTNode *BST_Search(BStree T,int key){ while(T!=NULL && key!=T-key){ if(keylchild; else T=T-rchild; } return T;}//递归BSTNode *BSTSearch(BStree T,int key){ if(T==NULL){ return NULL; } if(key==T->key){ return T; }else if(keykey){ return BSTSearch(T->lchild,key); }else if(key>T->key){ return BSTSearch(T->rchild,key); }}
二叉排序树的插入
若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树
int BST_Insert(BSTree &T，int k）{ if(T==NULL）{//原树为空，新插入的结点为根结点 T=(BSTree)malloc(sizeof(BSTNode)); T->key=k; T->lchild=T->rchild=NULL; return 1;//返回1，插入成功 }else if(k==T->key){//树中存在相同关键字的结点，插入失败 return 0; }else if(kkey){//插入到T的左子树 return BST_Insert(T->lchild,k); }else{//插入到T的右子树return BST_Insert(T->rchild,k);}}二叉排序树的构造
不同的关键字序列可能得到相同的二叉排序树，也可能得到不同的二叉排序树。
//按照str[]中的关键字序列建立二叉排序树void Creat_BST(BSTree &T，int str[],int n){ T=NULL;//初始时T为空树 int i=0; while(i//依次将每个关键字插入到二叉排序树中 BST_Insert(T,str[i]); i++; } } int key; int balance; struct AVLNode *lchild,*rchild;}AVLNode,*AVLTree;h5平衡二叉树的插入/h5 p在二叉树排序树中插入新结点后，需要查找路径上所有结点，从插入点往回找到第一个不平衡的结点，调整以该结点为根的子树（最小不平衡树）。/p h5调整最小不平衡子树/h5 tabletheadtrth/thth调整最小不平衡子树A/th/tr/theadtbodytrtdLL/tdtd在A的左孩子的左子树中插入导致不平衡/td/trtrtdRR/tdtd在A的右孩子的右子树中插入导致不平衡/td/trtrtdLR/tdtd在A的左孩子的右子树中插入导致不平衡/td/trtrtdRL/tdtd在A的右孩子的左子树中插入导致不平衡/td/tr/tbody/table p调整最小不平衡子树（LL）/p pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-250423013035915.png" //p pLL平衡旋转（右单旋转）/p ulli由于在结点A的左孩子（L）的左子树（L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。/lili将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。p调整最小不平衡子树（RR）/p pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-25042301303CL.png" //p pRR平衡旋转（左单旋转）/p ulli由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。/lili将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。p代码思路/p pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250423/-25042301303C96.png" //p ulli p实现f向右下旋转，p向右上旋转：其中f是爹，p为左孩子，gf为f的爹（左旋、右旋操作后可以保持二叉排序树的特性）/p ullif-lchild=p-rchild;/lilip->rchild=f; - gf->lchild/rchild=p;
-
实现 f 向左下旋转， p 向左上旋转：其中f是爹，p为右孩子，gf为f的爹
- f->rchild = p->lchild;
- p->lchild = f;
- gf->lchild/rchild = p;
调整最小不平衡子树（LR）
LR平衡旋转（先左后右双旋转）
- 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因
子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
- 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。
调整最小不平衡子树（RL）
RL平衡旋转（先右后左双旋转）
- 由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡
因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
- 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该c结点向左上旋转提升到A结点的位置。
查找效率分析
若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O(h)
平衡二叉树一一树上任一结点的左子树和右子树的高度之差不超过1。
假设以 n h n_h nh表示深度为h的平衡树中含有的最少结点数，则有 n 0 = 0 , n 1 = 1 , n 2 = 2 , 并且有 n h = n h − 1 , + n h − 2 + 1 n_0=0,n_1=1,n_2=2,并且有n_h=n_{h-1},+n_{h-2}+1 n0=0,n1=1,n2=2,并且有nh=nh−1,+nh−2+1
可以证明含有n个结点的平衡二叉树的最大深度为 O ( log 2 n ) O(\log_2n) O(log2n)，平衡二叉树的平均查找长度为 O ( log 2 n ) O(\log_2n) O(log2n)
平衡二叉树的删除
平衡二叉树的删除操作：
- 删除结点后，要保持二叉排序树的特性不变（左 int key; RBnode* parent; RBnode* lchild; RBnode* rchild; int color;}; ElemType keys[4];//最多4个关键字 struct Node* child[5];//最多5个孩子 int num;//结点中有几个关键字};
- 由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡
- 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因
下一篇：最后不管怎么样英文怎么说?
