【王道数据结构】第七章| 查找 | 树

目录

一、查找

1、查找概念

2、顺序查找

3、折半查找 

4、分块查找

二、树

1、B树 

2、B树的基本操作

3、B+树

4、散列查找及其性能分析 

5、散列查找及性能分析

---

一、查找

1、查找概念

 

• 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
• 查找表(查找结构)：用于查找的。数据集合称为查找表，它由同一类型的数据元素 (或记录)组成。
• 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

如下举例： 

 

• 查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
• 平均查找长度(ASL，Average Search Length)： 所有查找过程中进行关键字的比较次数的平均值。

2、顺序查找

 

• 顺序查找，又叫“线性查找”，通常用于线性表算法
• 思想:从头到 jio 个找 (或者反过来也OK) 

代码实现： 

typedef struct{				//查找表的数据结构（顺序表）ElemType *elem;			//动态数组基址int TableLen;			//表的长度
}SSTable;//顺序查找
int Search_Seq(SSTable ST,ElemType key){int i;for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);// 查找成功返回数组下标，否则返回-1return i=ST.TableLen? -1 : i;
}

哨兵方式代码实现：

typedef struct{				//查找表的数据结构（顺序表）ElemType *elem;			//动态数组基址int TableLen;			//表的长度
}SSTable;//顺序查找
int Search_Seq(SSTable ST,ElemType key){ST.elem[0]=key;int i;for(i=ST.TableLen;ST.elem[i]!=key;--i)// 查找成功返回数组下标，否则返回0return i;
}

 用查找判定树分析ASL

• 一个成功结点的查找长度=自身所在层数
• 一个失败结点的查找长度 =其父节点所在
• 层数默认情况下，各种失败情况或成功情况都等概率发生

3、折半查找 

【折半查找概念】

• 折半查找，又称“二分查找”，仅适用于有序的顺序表

折半查找代码实现： 

typedef struct{ElemType *elem;int TableLen;
}SSTable;// 折半查找
int Binary_Search(SSTable L,ElemType key){int low=0,high=L.TableLen,mid;while(low<=high){mid=(low+high)/2;if(L.elem[mid]==key)return mid;else if(L.elem[mid]>key)high=mid-1;					//从前半部分继续查找elselow=mid+1;					//从后半部分继续查找}return -1;
}

• 折半查找判定树的构造：m i d = ⌊ ( l o w + h i g h ) / 2 ⌋ ，如果当前 low 和 high 之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等；如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素。
• 折半查找的判定树中，若m i d = ⌊ ( l o w + h i g h ) / 2 ⌋ ，则对于任何⼀个结点，必有：右⼦树结点数 - 左⼦树结点数 = 0 或 1。
• 折半查找的判定树⼀定是平衡⼆叉树。折半查找的判定树中，只有最下⾯⼀层是不满的。因此，元素个数为 n 时树⾼ h = ⌈ l o g 2 ( n + 1 ) ⌉ 。
• 判定树结点关键字：左<中<右，满⾜⼆叉排序树的定义。失败结点：n+1个（等于成功结点的空链域数量）
• 折半查找的查找效率：折半查找的时间复杂度 = O ( l o g 2 n ) 。

4、分块查找

分块查找所针对的情况：块内⽆序、块间有序。

​

 索引表及顺序表代码

// 索引表
typedef struct{ElemType maxValue;int low,high;
}Index;// 顺序表存储实际元素
ElemType List[100];

• 查找目标关键字所在分块可使用顺序查找和折半查找两种方式。
• 若使用折半查找且索引表中不包含⽬标关键字，则最终要停在 low > high，要在 low 所指分块中查找目标关键字。
• 查找效率分析（ASL）：假设⻓度为 n 的查找表被均匀地分为 b 块，每块 s 个元素。设索引查找和块内查找的平均查找⻓度分别为 ASL=LI​+LS​

二、树

1、B树 

B树，⼜称多路平衡查找树，B树中所有结点的孩⼦个数的最⼤值称为B树的阶，通常⽤m表示。⼀棵m阶B树或为空树，或为满⾜如下特性的m叉树：

• 树中每个结点⾄多有 m 棵⼦树，即⾄多含有 m-1 个关键字。
• 若根结点不是终端结点，则⾄少有两棵⼦树。
• 除根结点外的所有⾮叶结点⾄少有 ⌈ m / 2 ⌉棵⼦树，即⾄少含有 $\lceil m/2\rceil-1 $个关键字。（为了保证查找效率，每个结点的关键字不能太少）

• 所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

 

m阶B树的核⼼特性：

• 根节点的⼦树数∈ [ 2 , m ] ∈[2, m]∈[2,m]，关键字数 ∈ [ 1 , m − 1 ] ∈[1, m-1]∈[1,m−1]。
• 其他结点的⼦树数∈ [ ⌈ m / 2 ⌉ , m ] ∈[⌈m/2⌉ , m]∈[⌈m/2⌉,m]；关键字数∈ [ − 1 , m − 1 ] ∈[ -1, m-1]∈[−1,m−1]。
• 对任⼀结点，其所有⼦树⾼度都相同。
• 关键字的值：⼦树0 < 关键字1 < ⼦树1 < 关键字2 < ⼦树2 <…. (类⽐⼆叉查找树左<中<右)

B树的⾼度：含 n 个关键字的 m叉B树，最⼩⾼度、最⼤⾼度是多少？

• logm​n+1≤h≤log⌈m/2⌉​2n+1​+1

2、B树的基本操作

B树的查找：

• B树的查找操作与二叉查找树类似。B树的查找包含两个基本操作：① 在B树中找结点；② 在结点中找关键字。B树常存储在磁盘上，因此前一个查找操作在磁盘上进行，后一个查找操作在内存中进行。在B树中查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应指针信息到所指的子树中去查找。查找到叶子结点（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

B树的插入：将关键字 key 插入到B树的过程： 

• 定位：利用B树的查找算法，找到插入该关键字的最底层中的某个非叶子结点。（插入位置一定是最底层的某个非叶子结点！）
• 插入：B树中，每个非失败节点的关键字个数都在区间[ ⌈ m / 2 ⌉ − 1 , m − 1 ] [⌈m/2⌉- 1,m-1][⌈m/2⌉−1,m−1]内。若插入关键字 key 之后结点关键字个数小于m，则可以直接插入；否则必须对结点进行分裂。
• 分裂：从结点的中间位置（⌈ m / 2 ⌉ ⌈m/2⌉⌈m/2⌉）将其中的关键字分为两部分，左半部分包含的关键字放到原结点中，右半部分包含的关键字放到新节点中，中间位置（⌈ m / 2 ⌉ ⌈m/2⌉⌈m/2⌉）的关键字则插入原节点的父节点。若此时父节点的关键字也超过了上限，则对父节点继续进行分裂操作，直到这个过程传到根节点为止，进而导致B树的高度增加。

B树的删除：

1. 非终端结点的删除：使用直接前驱或者直接后继来代替被删除的关键字，转换为删除终端结点。
2. 终端结点的删除，具体分为三种情况

• 直接删除关键字：若删除关键字所在结点关键字个数 ≥ ⌈ m / 2 ⌉ ≥⌈m/2⌉≥⌈m/2⌉，则可直接删除。
• 兄弟够借：若删除关键字所在结点关键字个数 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉-1=⌈m/2⌉−1，且与此结点相邻的左（或右）兄弟结点关键字个数 ≥ ⌈ m / 2 ⌉ ≥⌈m/2⌉≥⌈m/2⌉，则需调整该节点、左（或右）兄弟结点及其双亲结点（父子换位法）以达到新的平衡。
• 兄弟不够接：若删除关键字所在结点关键字个数 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉-1=⌈m/2⌉−1，且与此结点相邻的左（或右）兄弟结点关键字个数 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉-1=⌈m/2⌉−1，则将该节点、左（或右）兄弟结点及其双亲结点中的关键字进行合并。
   

3、B+树

一棵m阶的B+树需满足以下条件： 

• 每个分支节点最多有m棵子树（孩子结点）。
• 非叶根结点至少有两颗子树，其他每个分支结点至少有⌈ m / 2 ⌉ ⌈m/2⌉⌈m/2⌉棵子树。
• 结点的子树个数与关键字个数相同。
• 所有叶子结点包含所有关键字及指向相应记录的指针，叶子结点中将关键字按大小排列，并且相邻叶子结点按大小顺序相互链接起来。（说明B+树支持顺序查找）
• 所有分支节点仅包含它的各个节点中关键字的最大值及指向其子节点的指针。
   

4、散列查找及其性能分析 

散列表的基本概念

• 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记作H a s h ( k e y ) = A d d r Hash(key)=AddrHash(key)=Addr。
• 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突。发生碰撞的不同关键字称为同义词。
• 散列表：根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的一种直接映射关系。

散列函数的构造方法

1. 直接定址法：直接取关键字的某个线性函数值为散列地址，散列函数为 H ( k e y ) = k e y  或 H ( k e y ) = a × k e y + b 。这种方法计算简单，不会产生冲突。缺点是空位较多，会造成存储空间浪费。
2. 除留余数法：假定散列表表长 m，取一个不大于但最接近 m 的质数 p，利用散列函数 H ( k e y ) = k e y % p将关键字转换为散列地址。p取质数是因为这样可以使关键字通过散列函数转换后等概率地映射到散列空间上的任一地址。
3. 数字分析法：假设关键字是 r进制数，而r个数码在个位上出现的频率不一定相同，可能在某些位上分布的均匀一些，而在某些位分布的不均匀。此时应选数码分布均匀的若干位作为散列地址。
4. 平方取中法：这种方法取关键字平方值的中间几位作为散列地址，具体取多少位视具体情况而定。这种方法得到的散列地址与关键字的每一位都有关系，因此使得散列地址分布比较均匀。适用于关键字每位取值都不够均匀或均小于散列地址所需的位数。

5、散列查找及性能分析

散列查找执行步骤如下

1. 初始化：A d d r = H a s h ( k e y ) 
2. 检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它和 key 的值，若相等则返回查找成功，否则执行步骤③。
3. 用给定的处理冲突方式计算“下一个散列表地址”，并把 Addr 置为此地址，转入步骤②。

平均查找长度（ASL）：散列表查找成功的平均查找长度即找到表中已有表项的平均比较次数；散列表查找失败的平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数。