数据基础及结构 1

第八章查找数据结构与算法数据结构与算法查找的重要性与应用场景核心目标从数据集合中快速定位目标元素，是计算机科学中最基础且高频的操作之一，直接影响系统运行效率。实际应用搜索引擎、电商平台商品检索、通讯录联系人查找、数据库查询等，均以查找为底层支撑。算法分类根据数据结构特性，可分为顺序查找、折半查找、树型查找（如二叉搜索树）、哈希表查找等，体现了不同的设计思想和效率权衡。问题导入：图书馆书籍查找系统任务背景：海量书籍管理在一个大型图书馆中，有大量的书籍需要管理和查找。每本书都有唯一的ISBN编号，图书馆希望设计一个系统，能够快速根据读者提供的ISBN编号找到相应书籍的位置信息。核心挑战：快速定位目标如何在海量书籍中，根据给定的关键字（ISBN）快速定位目标元素（书籍），这直接影响系统的响应效率和用户体验。问题本质：数据查找与索引这是一个典型的查找问题，即从数据集合中快速定位目标元素。不同的查找策略和数据结构会带来截然不同的效率。解决这个问题的关键在于选择合适的索引结构，如哈希表或二叉搜索树，以实现O(1)或O(logn)的查找时间复杂度。基本概念：查找表查找表定义由同一类型的数据元素（或记录）构成的集合。数据元素之间关系松散，是一种应用灵活的结构。基本操作1.查询元素是否存在；2.检索元素属性；3.插入新元素；4.删除指定元素。查找表分类根据是否允许修改操作，分为静态查找表（仅查询）和动态查找表（支持插入和删除）。核心特点查找表不要求数据元素之间有严格的逻辑顺序，主要关注数据元素的存在性及属性检索，是实现高效数据管理的基础。基本概念：关键字关键字定义数据元素中用于标识自身的数据项，是查找操作的依据。主关键字能够唯一识别一个记录的关键字。例如，学生的学号、书籍的ISBN编号。次关键字能够识别若干记录的关键字。例如，学生的姓名、商品的类别。关键字的作用关键字是数据检索的核心，建立数据间的索引关系，大幅提高查找效率，是数据库和数据结构中的基础概念。基本概念：查找的定义与结果查找的定义根据给定值，在查找表中确定关键字等于该值的数据元素的过程。查找结果查找成功：返回元素信息或位置；查找失败：返回空记录或空指针。示例：学生成绩查找关键字(Key)关键字是数据元素中标识元素的数据项。主关键字可唯一标识记录，次关键字则不能。数据结构定义：关键字类型关键字类型定义typedeffloatKeyType;//实型关键字typedefintKeyType;//整型关键字typedefchar*KeyType;//字符串型关键字typedefstruct{ KeyTypekey;//关键字域 ...//其他属性域}ElemType;概念与作用解析通用性设计：通过typedef定义KeyType，使代码不依赖具体数据类型，便于维护和扩展。比较操作基础：关键字是数据元素中用于标识和比较的字段，是实现查找、排序等算法的核心依据。类型灵活切换：只需修改KeyType的定义，即可将算法应用于整数、实数或字符串等不同类型的数据。数据结构定义：数值型关键字比较宏数值型关键字比较宏定义#defineEQ(a,b)((a)==(b))//等于#defineLT(a,b)((a)<(b))//小于#defineLQ(a,b)((a)<=(b))//小于等于//...其他比较宏（如GT,GQ,NE等）宏定义设计说明抽象数据类型：通过宏定义将具体的比较操作抽象化，屏蔽底层数据类型细节。代码健壮性：使用双层括号包裹参数，防止宏展开时因运算符优先级导致逻辑错误。通用性扩展：若关键字类型变更（如字符串），仅需修改此处宏定义，无需重构算法逻辑。数据结构定义：字符串型关键字比较宏字符串型关键字比较宏定义#defineEQ(a,b)(!strcmp((a),(b)))//等于：a与b字符串相等时返回真#defineLT(a,b)(strcmp((a),(b))<0)//小于：a字典序小于b时返回真#defineLQ(a,b)(strcmp((a),(b))<=0)//小于等于：a字典序小于等于b时返回真代码解析与应用说明核心函数：使用C标准库函数strcmp进行字符串比较，该函数按ASCII码值逐字符比较。返回值逻辑：strcmp返回0表示相等，返回负数表示前者小于后者，正数表示前者大于后者。宏定义优势：通过宏定义将复杂的比较逻辑封装为EQ/LT/LQ，提高代码可读性与复用性，常用于查找、排序等算法中。8.1静态查找表静态查找表的抽象数据类型与实现数据结构与算法静态查找表的抽象数据类型(ADT)数据对象DD是具有相同特性的数据元素的集合，每个元素含有关键字，可唯一标识自身。数据关系R数据元素同属一个集合，关系松散，元素间无复杂的层级或依赖关系。基本操作PCreate(&ST,n)：构造含n个元素的静态查找表Destroy(&ST)：销毁查找表Traverse(ST,Visit())：遍历表中元素Search(ST,key)：查找关键字为key的元素ADT核心价值将查找表的逻辑结构与物理实现分离，定义了标准的操作接口，为后续实现顺序查找、折半查找等算法奠定基础。8.1.1顺序表的查找顺序表查找定义顺序表查找是最基础的查找方法，从表的一端开始，依次将每个元素与给定值比较，直到找到目标或遍历结束。顺序表存储结构typedefstruct{ElemType*elem;//数据元素存储空间基址intlength;//表的长度}SSTable;查找效率分析查找成功时的平均查找长度为(n+1)/2，时间复杂度为O(n)。适用于数据量较小或无序的线性表。算法特点总结优点：算法简单，无需对数据进行排序预处理。缺点：效率较低，数据量越大，平均查找时间越长。顺序表查找的过程查找步骤（一）从顺序表的第一个元素开始遍历将当前元素与目标查找值进行比较若两者相等，则查找成功，返回当前位置查找步骤（二）若两者不等，则继续比较下一个元素若遍历完所有元素仍未找到，返回查找失败顺序查找表示意图算法特点与性能时间复杂度：平均与最坏情况均为O(n)适用场景：数据量较小或无序的顺序表优势：实现简单，无需数据有序排列顺序表查找代码实现(算法8.1)Search_Seq函数实现intSearch_Seq(SSTable&ST,KeyTypekey){//设置哨兵，避免每次循环都检查数组边界ST.elem[0].key=key;inti=ST.length;//从表尾开始向前查找while(!EQ(ST.elem[i].key,key)){--i;}//返回找到的位置，若为0则表示查找失败returni;}性能分析：平均查找长度(ASL)ASL定义查找过程中关键字比较次数的数学期望值，是衡量查找算法效率的重要指标。ASL公式

查找效率意义ASL值越小，说明查找算法的平均效率越高。它综合考虑了元素的查找概率和比较次数，是评价算法优劣的核心标准。主要影响因素

顺序表查找的ASL分析（等概率）比较次数$c_i$

ASL计算

时间复杂度

核心结论与优化

顺序表查找的ASL分析（不等概率）ASL极小值条件

改进策略若查找概率无法预先测定，可在每次查找成功后，将该记录移至表尾，以便提高后续查找效率。核心思想利用概率分布特性优化查找结构，将高频访问元素置于更优位置，从而降低平均查找长度(ASL)。8.1.2有序表的查找-折半查找核心思路利用数据的有序性，通过不断将查找区间减半来快速缩小目标范围，从而减少比较次数。适用条件数据必须有序排列，并且存储在顺序存储结构中（如数组）。折半查找的步骤分解查找步骤（初始化与比较）确定初始查找区间[low,high]，要求表有序计算中间位置mid=(low+high)/2（整数除法）比较目标值与ST.elem[mid].key的大小查找步骤（调整与循环）若相等则查找成功；若目标值小，在左半区[low,mid-1]继续查找；若大则在右半区[mid+1,high]查找重复步骤直到找到目标或区间为空（失败）折半查找示意图核心原理与特性

折半查找的指针定义low指针指示当前查找区间的下界（起始位置）。初始时通常指向数组的第一个元素。high指针指示当前查找区间的上界（结束位置）。初始时通常指向数组的最后一个元素。mid指针指示当前比较的中间位置。为避免整数溢出，推荐公式：mid=low+(high-low)/2。核心作用通过不断缩小low和high的范围，实现对数级的查找效率。仅适用于有序的线性表结构。折半查找示例ST.elemST.length例如:key=64

的查找过程如下：lowhighmidlow

highmidlow

指示查找区间的下界high

指示查找区间的上界mid=(low+high)/2折半查找代码实现(算法8.2)Search_Bin函数实现intSearch_Bin(constSSTable&ST,KeyTypekey){intlow=1;inthigh=ST.length;while(low<=high){intmid=low+(high-low)/2;//防止溢出if(EQ(key,ST.elem[mid].key)){returnmid;//查找成功}elseif(LT(key,ST.elem[mid].key)){high=mid-1;//在前半区查找}else{low=mid+1;//在后半区查找}}return0;//查找失败}折半查找的ASL分析：判定树模型判定树概念折半查找的过程可以用一棵二叉树来描述，称为判定树。树中每个节点代表一次比较，节点所在的层数即为比较次数。树的高度

平均查找长度(ASL)平均查找长度是衡量查找算法效率的核心指标，指在查找过程中找到目标元素所需的平均比较次数，反映了算法的时间性能。折半查找的效率

折半查找的ASL计算（满二叉树）ASL求和公式

公式推导

时间复杂度

核心结论折半查找效率较高，适用于有序表的静态查找，其性能取决于树的高度。折半查找的性能总结时间复杂度

优点查找效率远高于顺序查找，尤其在数据量庞大的有序表中，能大幅减少比较次数。缺点要求数据必须有序排列，且仅适用于顺序存储结构，数据的插入和删除操作不方便。适用场景适用于静态查找表，即数据一旦建立后不常变动、但需要频繁进行查找操作的有序数组场景。8.1.3静态树表的查找问题提出折半查找在等概率下性能优异，但在数据元素查找概率不均的情况下，并非最优选择。如何优化不等概率下的查找效率？解决方案引入静态树表，如次优查找树，它在构建时考虑节点的查找概率，以优化平均查找长度。不等概率折半查找示例示例数据关键字序列：A,B,C,D,E查找概率：0.2,0.3,0.05,0.3,0.15折半查找的ASL计算

计算逻辑图示优化思考在不等概率查找中，若按概率高低调整节点位置（如使用最优二叉树），可显著降低平均查找长度。例如：若将概率最高的节点（B,D）调整至更上层，理论上ASL可降至1.9左右。次优查找树的概念定义次优查找树是一种在构建时考虑节点查找概率，以近似优化平均查找长度（ASL）的树形查找结构。核心思想基于贪心策略，选择使左右子树概率和差值最小的节点作为根，以平衡树的带权路径长度。目标在不进行复杂动态规划计算的前提下，使ASL尽可能接近最优查找树。核心特点构建效率高，避免了最优二叉查找树（OBST）的高时间复杂度；在实际应用中，其性能往往能满足需求。次优查找树构建步骤：预处理步骤一：预处理概述预处理是构建次优查找树的基础，目的是通过计算概率分布，为后续选择最优根节点提供数据支持。操作步骤一：排序与前缀

操作步骤二：区间概率

关键公式说明

次优查找树构建步骤：根节点选择步骤二：根节点选择

选择原则选择概率和最接近的节点作为根，使左右子树的权重尽可能平衡，从而降低整体查找的平均比较次数。步骤三：递归构造

终止条件当区间的起始索引大于结束索引时，递归终止。次优查找树构建示例构建过程示意图示例说明图中展示了根据节点权重递归选择根节点，最终构建出次优查找树的过程。通过计算ΔPi选择最优分割点，平衡树的高度。构建核心逻辑计算所有节点的累计权重和寻找使|ΔPi|最小的节点作为根递归构建左子树和右子树算法优势构建效率高：时间复杂度为O(n²)查找性能接近最优二叉查找树避免了最优树构建的高复杂度(O(n³))次优查找树代码实现(算法8.3)SecondOptimal函数逻辑

SecondOptimal函数代码实现StatusSecondOptimal(BiTree&T,ElemTypeR[],floatsw[],intlow,inthigh){//选择使|w(low,m-1)-w(m+1,high)|最小的m作为根//...(选择根节点m的代码省略)if(!(T=(BiTree)malloc(sizeof(BiTNode))))returnERROR;T->data=R[m];//生成根节点if(m==low)T->lchild=NULL;//左子树为空elseSecondOptimal(T->lchild,R,sw,low,m-1);if(m==high)T->rchild=NULL;//右子树为空elseSecondOptimal(T->rchild,R,sw,m+1,high);returnOK;}次优查找树代码实现-CreateSOSTre(算法8.4)核心逻辑解析判空处理：若有序表为空，直接返回空树。权值计算：调用FindSW函数计算累计权值表sw，为选择次优根节点做准备。递归构建：调用SecondOptimal递归生成次优查找树。资源释放：释放动态分配的累计权值数组sw。CreateSOSTre函数实现StatusCreateSOSTre(SOSTree&T,SSTableST){

if(ST.length==0)T=NULL;

else{

floatsw=(float)malloc((ST.length+1)*sizeof(float));FindSW(sw,ST);//计算累计权值表swSecondOptimal(T,ST.elem,sw,1,ST.length);free(sw);}

returnOK;}8.1.4索引顺序表的查找索引顺序表概念将线性表分块存储，每块内元素可以无序，但块之间必须有序。为每块建立一个索引项，包含块的最大关键字和块的起始地址。分块原则块内无序，便于插入和删除；块间有序，便于建立索引和查找。这种结构结合了顺序查找和折半查找的优点。索引表结构索引表是一个有序表，每个索引项对应一个数据块，包含该块的最大关键字和该块在内存中的起始地址。索引表按关键字有序排列。分块查找过程先在索引表中确定待查记录所在的块（可折半/顺序）。然后在该块中进行顺序查找。索引顺序表的查找过程第一步：确定块在索引表中进行折半查找或顺序查找，确定目标元素所在的块。第二步：块内查找在确定的块内进行顺序查找，找到目标元素。查找过程总结分块查找结合了折半查找和顺序查找的优点，先通过索引快速定位块，再在块内进行详细查找。索引顺序表的查找过程索引顺序表的性能分析ASL构成要素分块查找的平均查找长度（ASL）由两部分组成：索引表的平均查找长度和块内的平均查找长度。计算公式

性能定位分块查找的性能介于顺序查找和折半查找之间。它通过分块有序的特性，平衡了查找速度和数据组织的复杂度。效率关键：块大小

8.2动态查找表二叉搜索树与自平衡树数据结构与算法动态查找表简介动态查找表定义支持插入和删除操作的查找表，能够动态地调整数据结构以适应数据的变化，保证查找效率。常见结构包括二叉搜索树（BST）、平衡二叉树（AVL树、红黑树）、B-树/B+树等。这些结构能够高效地支持动态查找、插入和删除操作。学习要点后续章节将深入学习这些动态查找结构，重点关注其自平衡机制和性能保证，理解不同场景下的结构选择。核心特点

哈希表简介核心思想利用哈希函数将关键字直接映射到数据存储位置，实现“一次查找”，体现了“空间换时间”的极致应用。时间复杂度平均情况下的查找、插入、删除时间复杂度均为O(1)，是效率最高的查找方法之一。关键问题哈希冲突的解决是哈希表设计的核心，常见方法有开放定址法、链地址法等。动态查找表的定义与特点定义(Definition)支持插入和删除操作的查找表，能够动态地调整数据结构以适应数据的变化。特点(Characteristics)在查找的同时，可以对表进行修改，结构会根据操作动态调整，以保持高效的查找性能。常见结构(CommonStructures)二叉搜索树（BST）平衡二叉树（AVL树、红黑树）B-树/B+树核心优势(Advantages)解决了静态查找表在频繁插入删除后效率低下的问题，保证了数据操作的时间复杂度在可控范围内，适用于数据动态变化的场景。动态查找表ADTDynamicSearchTable{数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT)；//构造一个空的动态查找表DT。SearchDSTable(DT,key)；//动态查找表DT存在，key为和关键字类型相同的给定值；若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。DestroyDSTable(&DT)；//动态查找表DT存在，销毁动态查找表DT。InsertDSTable(&DT,e)；//动态查找表DT存在，e为待插入的数据元素；若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&T,key)；//动态查找表DT存在，key为和关键字类型相同的给定值；若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT,Visit())；//动态查找表DT存在，Visit是对结点操作的应用函数；按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败。}ADTDynamicSearchTable8.2.1二叉排序树(BST)定义(Definition)二叉排序树（BST）是一种基于二叉树的动态查找表，其左子树节点值小于根节点，右子树节点值大于根节点。核心性质(Properties)左子树上所有节点的值均小于根节点的值右子树上所有节点的值均大于根节点的值左右子树也分别是二叉搜索树主要特点(Features)中序遍历可得到有序序列查找效率与树的高度相关，理想为O(logn)支持动态插入和删除操作应用场景(Applications)高效的动态查找表实现数据排序与去重实现关联数组（如C++STL中的map/set）8.2.1二叉排序树(BST)二叉排序树的查找操作查找步骤1.从根节点开始。2.若目标值等于当前节点值，查找成功。3.若目标值小于当前节点值，向左子树查找。4.若目标值大于当前节点值，向右子树查找。5.若子树为空，则查找失败。时间复杂度查找的时间复杂度取决于树的高度h。平均情况为O(logn)。最坏情况为O(n)（树退化为链表）。算法特点查找操作是二叉搜索树的核心功能，利用其左小右大的特性，能够快速缩小查找范围，效率通常高于线性查找。应用场景广泛应用于需要动态维护有序数据且频繁进行查找操作的场景，如数据库索引、编译器符号表等。二叉排序树的插入操作步骤一：查找位置从根节点开始，按照二叉搜索树的性质（左小右大）进行查找，直到找到合适的空位置。步骤二：插入节点将新节点作为叶子节点插入到上一步找到的位置，保持树的结构特性不变。潜在风险：有序插入如果插入的元素序列是有序的（递增或递减），二叉搜索树可能会退化为单链表结构。严重后果：效率下降

二叉排序树的插入操作二叉搜索树的插入StatusInsertBST(BiTree&T,ElemTypee){BiTreep=nullptr;if(!SearchBST(T,e.key,nullptr,p)){BiTrees=(BiTree)malloc(sizeof(BiTNode));//创建新节点if(!s)returnFALSE;//未找到s->data=e;//初始化新节点s->lchild=s->rchild=nullptr;//Insertnodeif(!p){T=s;//作为根节点插入}elseif(LT(e.key,p->data.key)){p->lchild=s;//作为左孩子插入}else{p->rchild=s;//作为右孩子插入}returnTRUE;//插入成功}returnFALSE;//Key已存在}二叉排序树的删除操作情况一：删除叶子节点直接删除该节点即可，不影响树的结构平衡。情况二：删除单孩子节点将该节点的孩子节点提升到被删除节点的位置，保持树的连通性。情况三：删除双孩子节点找到该节点的中序后继（右子树的最小节点）或前驱，用其值替换被删除节点的值，然后删除后继或前驱节点。操作要点总结删除操作需保持二叉搜索树的性质。删除双孩子节点是最复杂的情况，通常采用“替换法”。二叉排序树的删除操作二叉排序树的删除StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;//没找到if(EQ(key,T->data.key)){

DeleteNode(T);returnTRUE;}elseif(LT(key,T->data.key)){returnDeleteBST(T->lchild,key);}else{returnDeleteBST(T->rchild,key);}}二叉排序树的删除voidDelete(BiTree&p){if(!p->rchild){//右子树为空树则只需重接它的左子树q=p;p=p->lchild;free(q);}elseif(!p->lchild){//左子树为空树只需重接它的右子树q=p;p=p->rchild;free(q);}else{//左右子树均不空q=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;}//s指向被删结点的前驱p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;//重接*q的左子树free(s);}}//删除二叉排序树的性能问题理想情况

最坏情况

解决方案引入自平衡二叉搜索树，如AVL树和红黑树，通过旋转操作保持树的平衡。核心启示保持树的高度平衡是确保高效操作的关键，自平衡机制是解决性能退化的核心手段。8.2.2自平衡二叉搜索树：AVL树定义(Definition)AVL树是一种高度平衡的二叉搜索树，由G.M.Adelson-Velsky和E.M.Landis于1962年提出。平衡条件(BalanceCondition)对于树中的任意一个节点，其左子树的高度与右子树的高度的差的绝对值不能超过1。核心特性(KeyFeatures)

平衡因子(BalanceFactor)定义：节点的左子树高度减去右子树高度。取值：在AVL树中，任何节点的平衡因子只能是-1、0或1。8.2.2自平衡二叉搜索树：AVL树平衡二叉树的定义typedefstructBSTNode{ElemTypedate;intbf;//结点的平衡因子structBSTNode*lchild,*rchild;//左、右孩子指针}BSTNode,*BSTree;AVL树的平衡因子平衡因子定义(BF)平衡因子（BalanceFactor）是衡量节点平衡状态的指标。计算公式为：BF=左子树高度-右子树高度。合法取值范围AVL树要求每个节点的平衡因子只能是-1、0或1。当平衡因子的绝对值大于1时，树失去平衡，不再是AVL树。平衡的核心意义通过严格的平衡条件，确保二叉搜索树的高度始终保持在O(logn)级别，从而保证增删查改等操作的时间复杂度为最优。失衡与旋转调整当插入或删除节点导致失衡时，需通过旋转操作恢复平衡。常见旋转类型：LL、LR、RL、RR旋转。AVL树的旋转操作：LL与RR旋转LL旋转（右旋）当节点的左孩子的左子树插入新节点导致失衡时，进行右旋操作。RR旋转（左旋）当节点的右孩子的右子树插入新节点导致失衡时，进行左旋操作。旋转示意图左图展示右旋操作，右图展示左旋操作。旋转是AVL树维持平衡的核心机制。旋转的目的通过旋转操作，可以调整节点位置，降低树的高度，从而恢复AVL树的平衡因子条件（-1,0,1），保证查找效率。AVL树的旋转操作：LL与RR旋转AVL树的旋转操作：LL与RR旋转AVL树的旋转操作：LR与RL旋转LR旋转当节点的左孩子的右子树插入新节点导致失衡时，先对左孩子进行左旋，再对当前节点进行右旋。RL旋转当节点的右孩子的左子树插入新节点导致失衡时，先对右孩子进行右旋，再对当前节点进行左旋。旋转示意图左图展示了AVL树在发生LR和RL型失衡时，通过两次旋转操作恢复平衡的过程。旋转核心目的

AVL树的旋转操作：LR与RL旋转AVL树的旋转操作：LR与RL旋转平衡二叉树构建//-------平衡二叉排序树R_Rotate函数--------voidR_Rotate(BSTree&p){lc=p->lchild;//lc指向的*p的左子树根结点p->lchild=lc->rchild;//lc的右子树挂接为*p的左子树lc->rchild=p;p=lc;//p指向新的根结点}//R_Rotate//-------平衡二叉排序树L_Rotate函数--------voidL_Rotate(BSTree&p){rc=p->rchild;//rc指向的*p的右子树根结点p->rchild=rc->lchild;//rc的左子树挂接为*p的右子树rc->lchild=p;p=rc;//p指向新的根结点}//L_Rotate平衡二叉树构建平衡二叉树构建StatusInsertAVL(BSTree&T,ElemTypee,Boolean&taller){if(!T){T=(BSTree)malloc(sizeof(BSTNode));//插入新节点T->data=e;T->lchild=T->rchild=nullptr;T->bf=EH;taller=true;return1;}if(EQ(e.key,T->data.key)){taller=false;return0;//Key已存在}平衡二叉树构建if(LT(e.key,T->data.key)){//插入左子树if(!InsertAVL(T->lchild,e,taller))return0;if(taller){switch(T->bf){caseLH:LeftBalance(T);taller=false;break;caseEH:T->bf=LH;taller=true;break;caseRH:T->bf=EH;taller=false;break;}}平衡二叉树构建}else{//插入右子树if(!InsertAVL(T->rchild,e,taller))return0;if(taller){switch(T->bf){caseLH:T->bf=EH;taller=false;break;caseEH:T->bf=RH;taller=true;break;caseRH:RightBalance(T);taller=false;break;}}}return1;}平衡二叉树左平衡旋转voidLeftBalance(BSTree&T){lc=T->lchild;//lc指向*T的左子树根结点switch(lc->bf){//检查*T的左子树的平衡度，并作相应平衡处理caseLH;//新结点插入在*T的左孩子的左子树，要作单右旋处理T->bf=lc->bf=EH;R_Rotate(T);break;caseRH;//新结点插入在*T的左孩子的右子树，要作双旋处理rd=lc->rchild;//rd指向*T的左孩子的右子树根switch(rd->bf){//修改*T及其左孩子的平衡因子caseLH:T->bf=RH;lc->bf=EH;break;caseEH:T->bf=lc->bf=EH;break;caseRH:T->bf=EH;lc->bf=LH;break;}//switch(rd->bf)rd->bf=EH;L_Rotate(T->lchild);//对*T的左子树作左旋平衡处理R_Rotate(T);//对*T的作右旋平衡处理}//switch(lc->bf)}//LeftBalanceAVL树的性能分析时间复杂度查找、插入、删除操作的时间复杂度均为O(logn)，保证了操作的高效性。优点严格平衡，查找效率极高，是所有平衡BST中查找性能最优的结构之一。缺点插入和删除操作可能需要多次旋转，实现复杂，开销较大，在更新频繁的场景中性能不如红黑树。适用场景适用于查询操作远多于更新操作的场景，如数据库索引、高频读缓存系统等，能最大化利用其查找优势。8.2.2B-树和B+树多路平衡搜索树的原理与实现数据结构与算法B-树的定义与特性B-树定义一种自平衡的多路搜索树，通过控制节点子树和关键字数量范围保证平衡，实现高效的查找、插入和删除，广泛应用于数据库索引和文件系统。m阶B-树特性（一）

3阶B-树结构示例m阶B-树特性（二）4.叶子节点：全部在同一层次，不带信息（外部节点）。5.节点结构：关键字升序排列，子树指针数比关键字数多1。B-树示例B-树的结构定义（C语言）B-树节点结构体定义typedefstructBTNode{intkeynum;//结点中关键字个数，即结点大小structBTNode*parent;//指向双亲结点的指针KeyTypekey[m+1];//关键字向量（0号单元不用）structBTNode*ptr[m+1];//子树指针向量Record*recptr[m+1];//记录指针向量（0号单元不用）}BTNode,*BTree;//B-树结点和B-树的类型B-树的查找过程查找步骤（一）：起始与定位起始：从B-树的根节点开始遍历节点内查找：在关键字序列中确定目标范围查找步骤（二）：递归与终止递归搜索：选择对应子树指针向下查找终止：找到目标值或到达叶节点失败核心算法逻辑初始化指针指向根节点节点内查找确定子树范围沿子树指针继续查找直到终止条件算法特点总结多路查找：每次选择一个子树分支高效：树高较矮，减少磁盘I/O次数应用：数据库索引、文件系统等B-树的查找typedefstruct{BTNode*pt;//指向找到的结点的指针inti;//1..m，在结点中的关键字序号inttag;//标志查找成功(=1)或失败(=0)}Result;//在B树的查找结果类型ResultSearchBTree(BTreeT,KeyTypeK){p=T;q=NULL;found=FALSE;i=0;//初始化，p指向待查接点，q指向p的双亲while(p&&!found){i=Search(p,K);//在p->key[1..keynum]中查找

，//i使得 p->key[i]<=K<p->key[i+1]if(i>0&&p->key[i]==K)found=TRUE;//找到待查关键字else{q=p;p=p->ptr[i];}}if(found)return(p,i,1);//查找成功elsereturn(q,i,0);//查找不成功，返回k的插入位置信息}//SearchBTreeB-树的插入操作与节点分裂插入步骤详解定位：找到新关键字应插入的叶节点直接插入：若节点未满(<m-1)，按序插入节点分裂：若满则中间关键字上移，递归处理核心算法逻辑(InsertBTree)从叶节点开始尝试插入新关键字若节点溢出(关键字数=m)，执行分裂操作递归向上检查父节点，必要时创建新根B-树结构与分裂示意操作关键特性平衡性：分裂保证了所有叶子节点在同一层树高变化：仅当根节点分裂时，树高才增加1效率：分裂操作的局部性保证了插入的高效性B-树的插入操作B-树的插入StatusInsertBTree(BTree&T,KeyTypeK,BTreeq,inti){x=K;ap=NULL;finished=FALSE;while(q&&!finished){Insert(q,i,x,ap);//将x和ap分别插入到q->key[i+1]和q->ptr[i+1]if(q->keynum<m)finished=TRUE;//插入完成

else{s=[m/2];split(q,s,ap);x=q->key[s];//将q->key[s+1..m],q->ptr[s..m]和q>recptr[s+1..m]，移入新结点*apq=q->parent;if(q)i=Search(q,x);//在双亲结点*q中查找x的插入位置}//else}//whileif(!finished)//T是空树(参数q初值为NULL)或者根结点已分裂为结点*q和*apNewRoot(T,q,x,ap);//生成含信息(T,x,ap)的新的根结点*T，原T和ap为子树指针returnOK;}//InsertBTreeB-树的删除操作与节点合并删除步骤：定位与转换定位：找到待删除关键字所在的节点。转换：若非叶节点，用其后继或前驱关键字替换，转为删除叶节点中的关键字。删除情况：直接删除情况一：删除后叶节点关键字数仍≥下限，则操作完成。删除步骤：调整与合并借关键字：从兄弟节点借一个关键字，并调整父节点。合并节点：若兄弟节点也达下限，则与兄弟节点及父节点的分隔关键字合并。删除情况：借位与合并情况二：向兄弟节点借关键字，需调整父节点指针。情况三：与兄弟节点合并，并可能递归向上调整。B-树的性能分析时间复杂度查找、插入、删除操作的时间复杂度均为O(log_mn)，其中m是B-树的阶，n是关键字总数。磁盘I/O效率树的高度很低，每次操作只需访问少量节点，对应少量磁盘块读取，处理海量数据时效率极高。二叉搜索树对比二叉搜索树时间复杂度为O(log_2n)，树高较高，导致磁盘I/O次数显著增加，不适合海量数据场景。B-树核心优势通过多路节点设计显著降低树高，极大减少磁盘I/O次数，这是其在数据库索引中替代二叉树的关键原因。B+树的定义与特性B+树定义B+树是B-树的重要变种，核心是数据与索引分离。所有数据存于叶子节点，非叶节点仅作索引，更适配数据库系统。核心特性（一）1.存储：数据仅在叶节点，非叶节点存关键字与指针；2.结构：非叶节点m个关键字对应m棵子树；3.连接：叶节点通过指针形成双向链表。3阶B+树结构示意图核心特性（二）与优势4.平衡：所有叶节点在同一层次；5.副本：非叶关键字是叶节点副本；优势：降低树高，大幅提升范围查询效率。B+树示例B-树与B+树的结构差异对比对比维度B-树B+树数据存储位置非叶节点和叶节点均存储数据指针仅叶节点存储数据，非叶节点为纯索引关键字重复性关键字在树中唯一，不重复非叶节点关键字是叶节点的副本，允许重复叶节点连接叶节点无指针连接叶节点通过双向链表连接，支持高效范围查询查找路径可能在非叶节点命中必须到达叶节点才能命中适用场景通用的平衡多路查找树数据库索引、文件系统，适合范围查询B+树的插入操作插入步骤详解定位：从根节点沿索引找到目标叶节点。直接插入：若叶节点未满，则直接插入并维护链表。节点分裂：若节点已满，中间关键字复制至父节点，原节点分裂为二。核心特点插入操作始终发生在叶子节点。分裂时中间关键字的副本提升至父节点。分裂后需维护叶节点双向链表的连续性。B+树结构示意图关键差异(B+vsB-)索引方式：B+树非叶节点仅作索引，不存数据。查询路径：B+树所有查询都必须到达叶子节点。分裂代价：B+树分裂时仅复制关键字，原数据保留。B+树的插入操作B+树的删除操作步骤一：定位与删除定位：从根节点出发，沿索引找到关键字所在的叶节点。删除：若存在该关键字，直接从叶节点中删除。步骤二：节点调整借关键字：若兄弟节点充足，借一个关键字并更新父节点索引。合并节点：若兄弟节点也不足，则与兄弟节点及父节点分隔关键字合并。步骤三：递归调整合并操作可能导致父节点关键字数不足。需递归向上调整，直至根节点，可能导致树高降低。核心特点总结操作仅在叶子节点完成，非叶节点仅作为索引。非叶节点关键字是副本，删除后可能需同步更新索引。B+树的应用场景主要应用：数据库索引MySQL、Oracle等主流关系型数据库的索引底层几乎都采用B+树实现。主要应用：文件系统如NTFS、HFS+等文件系统也使用B+树来管理文件目录和元数据。核心优势：高效范围查询叶节点通过链表连接，可快速进行范围查询和顺序访问，是相比B-树最大的优势。核心优势：稳定I/O与缓存树高稳定，I/O次数可预测；非叶节点仅存索引，占用空间小，更易被缓存到内存。8.2.3键树基于字符的字符串查找树数据结构与算法键树的结构与查找过程键树结构特点字符分支：关键字的每个字符作为树的分支路径代表关键字：根到叶子的路径字符连接成关键字结束标记：叶子节点设结束标志(如'$')表示完整关键字高效前缀处理：共享公共前缀，减少比较次数查找示例(查找"apply")从根节点出发，根据首字母'a'找到对应分支依次沿'p'->'p'->'l'->'y'分支深入到达终点节点，若有结束标志，则查找成功键树结构示意图应用场景与效率适用场景：字符串集合（如字典、单词表）的查找与排序时间复杂度：取决于关键字的平均长度L，平均查找长度为O(L)空间效率：利用公共前缀压缩存储空间，优于散列表键树示例以查找"apply","bababa"单词为例以查找"apply"为例，从根节点开始，根节点无实际字符，依据单词首字母'a'，找到根节点下以'a'为标识的分支并进入；接着遇到第二个字母'p'，继续沿着当前节点下'p'标识的分支深入；随后是字母'p'，再次沿对应分支前进；到字母'l'时，依旧沿着'l'标识分支移动；最后碰到字母'y'，沿'y'分支到达终点节点，若该节点设置了单词结束的特殊标志位，如'$'，即表明单词"apply"存在于集合中。键树的应用场景典型应用场景(一)字典查询：实现快速查找功能。IP地址查找：路由表匹配与转发。核心优势(一)高效处理公共前缀：查找效率高。空间效率高：公共前缀共享存储。典型应用场景(二)自动补全：文本编辑器/IDE提示。搜索建议：搜索引擎关键词联想。核心优势(二)支持前缀搜索：天然支持模糊匹配。动态扩展性：易于插入和删除操作。8.2.3自平衡二叉搜索树：红黑树定义(Definition)红黑树是一种近似平衡的二叉搜索树，通过节点着色和一系列规则来保证树的大致平衡。核心性质(Properties)每个节点非红即黑。根节点是黑色。所有叶子节点（NIL）是黑色。红色节点的子节点必须是黑色。从任一节点到其所有叶子的路径都包含相同数目的黑色节点。红黑树的插入操作与修复插入步骤1.按二叉搜索树(BST)规则找到插入位置，将新节点着色为红色。2.检查红黑树性质是否被破坏，若违反则进行修复。修复情况一：叔叔节点为红色处理方式：重新着色。将父节点和叔叔节点设为黑色，祖父节点设为红色，然后将祖父节点作为新的当前节点继续向上检查。修复情况二：叔叔黑且为LL型处理方式：一次旋转+重新着色。对祖父节点进行右旋转；将父节点设为黑色，祖父节点设为红色。修复情况三：叔叔黑且为LR型处理方式：两次旋转+重新着色。先对父节点左旋转，再对祖父节点右旋转；将新父节点（原兄弟）设为黑色，祖父设为红色。红黑树的性能分析时间复杂度查找、插入、删除操作的时间复杂度均为O(logn)，确保了在最坏情况下的高效性能。核心优点近似平衡，插入和删除操作所需的调整（旋转和着色）较少，综合性能优异，是应用最广泛的自平衡BST。与AVL树对比红黑树查找效率略低于AVL树（高度稍高），但插入删除效率更高，实现更简单，空间开销更小。典型应用场景广泛应用于C++STL（map/set）、Java集合框架（TreeMap/TreeSet）、Linux内核调度及高性能缓存系统中。8.3哈希表高效的键值对存储与查找数据结构与算法哈希表的基本概念定义(Definition)哈希表（HashTable）是一种通过哈希函数将关键字映射到数组对应位置，从而实现高效存取的数据结构。哈希函数(HashFunction)建立关键字到数组下标的映射关系的函数，是哈希表的核心。核心思想(CoreIdea)“空间换时间”，通过哈希函数直接定位数据，平均时间复杂度为O(1)。应用场景(Applications)缓存系统：如Redis、Memcached等，利用其快速查找特性。数据库索引：加速数据的检索过程。哈希表示例哈希函数的设计原则与方法设计原则计算高效：哈希函数的计算必须是快速的。映射均匀：尽可能减少冲突，使数据均匀分布。范围适配：哈希值范围应适配哈希表的大小。常用方法直接定址法：hash(key)=a*key+b除留余数法：hash(key)=key%m(m为质数)平方取中法：取关键字平方后的中间几位核心价值哈希函数是哈希表实现高效查找（平均O(1)时间复杂度）的核心。一个优秀的哈希函数能最大程度地减少冲突，从而保证哈希表在增删查改操作上的卓越性能。冲突处理机制开放定址法：发生冲突时，继续寻找下一个空的哈希地址。链地址法（拉链法）：将所有哈希地址相同的记录链接在同一个链表中。直接定址法哈希函数为关键字的线性函数

H(key)=key

或者

H(key)=a

key+b此法仅适合于：地址集合的大小==关键字集合的大小数字分析法此方法仅适合于：

能预先估计出全体关键字的每一位上各种数字出现的频度。

假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。平方取中法

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。

此方法适合于:

关键字中的每一位都有某些数字重复出现频度很高的现象。折叠法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。

此方法适合于:

关键字的数字位数特别多。除留余数法

设定哈希函数为:H(key)=keyMODp其中，

p≤m(表长)并且

p

应为不大于m

的素数，或是不含20以下的质因子随机数法设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数

通常，此方法用于对长度不等的关键字构造哈希函数。哈希冲突的定义与不可避免性定义(Definition)不同的关键字通过哈希函数计算得到相同的哈希地址，这种现象称为哈希冲突（HashCollision）。不可避免性(Inevitability)根据鸽巢原理，当关键字的数量大于哈希表的大小时，冲突必然发生。因此，冲突解决机制是哈希表设计的关键。影响(Impact)哈希冲突会降低哈希表的查找效率，理想的O(1)时间复杂度会退化为O(n)。严重的冲突会导致哈希表性能急剧下降，影响系统整体响应速度。解决思路(Solutions)开放定址法：发生冲突时，通过某种探测技术在哈希表中寻找下一个空的位置。链地址法：将哈希地址相同的元素构成一个单链表，挂接在相应的哈希桶后。8.3.1哈希冲突解决方法：开放定址法核心思想发生冲突时，按照某种探测规则在哈希表中寻找下一个空闲位置来存储数据。线性探测(LinearProbing)

二次探测(QuadraticProbing)

双重哈希(DoubleHashing)

8.3.1哈希冲突解决方法：开放定址法线性探测与二次探测线性探测-优点算法逻辑简单直观，易于编码实现和理解；计算探测位置的时间开销较小，在数据量不大时效率尚可。线性探测-缺点容易产生“一次聚集”现象，即连续的空闲位置被占用，导致查找、插入和删除的效率显著下降。二次探测-优点通过跳跃式的探测序列，有效缓解了“一次聚集”问题，使数据在哈希表中分布更加均匀，减少冲突。二次探测-缺点可能存在“二次聚集”问题；且探测序列有限，无法覆盖哈希表的所有位置，容易造成空间浪费。8.3.2哈希冲突解决方法：再哈希法

RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。Hi=RHi(key)i=1,2,…,k8.3.2哈希冲突解决方法：再哈希法8.3.3哈希冲突解决方法：链地址法核心思想哈希表的每个位置（桶）维护一个链表