《数据结构》课件 第9章 查找

查找算法详解从基础到高级数据结构与算法核心课程·进阶篇课程导入-为什么学习查找？在数据爆发式增长的今天，我们面临的最大挑战不再是获取信息，而是如何从海量无序的数据中“秒级定位”目标。查找技术不仅是解决信息过载的钥匙，更是支撑现代计算机系统高效运转的底层基石。01生活中的查找场景通讯录检索：快速定位联系人信息，毫秒级响应全网搜索：从万亿级网页中精准匹配关键词资料查阅：利用目录索引快速定位书籍章节信息管理：电商订单、物流轨迹的实时追踪02计算机领域的核心应用数据库索引：B+树实现千万级数据秒级查询操作系统：内存页表映射与文件系统管理编译原理：符号表快速查找加速代码编译人工智能：向量检索赋能推荐系统与识别本章目标：构建高效检索的思维框架深入掌握顺序查找、二分查找及哈希查找等经典算法的原理与实现；学会分析算法的时间与空间复杂度，能够根据数据特征和业务场景（如高并发、大数据量）灵活选择最优策略，为开发高性能应用奠定坚实基础。本章内容大纲01基本概念深入理解查找的核心术语与定义，建立对数据检索问题的基础认知框架，为后续算法学习奠定坚实基础。02静态查找表系统学习顺序查找、折半查找与分块查找算法，对比不同静态数据结构下的检索效率与适用场景。03动态查找表探索二叉排序树、平衡二叉树的构建与操作，进阶学习高性能的多路平衡查找树（B-树与B+树）。04哈希表：高效映射与冲突解决剖析哈希函数的构造方法与常见冲突处理策略（开放定址法、链地址法），理解“以空间换时间”的极致效率及其在高频检索场景中的应用。05总结回顾与AI领域应用横向对比各类查找算法的时间空间复杂度，结合实际案例探讨其在数据库索引、搜索引擎及人工智能数据处理中的关键作用与优化思路。基本概念(1)-关键字与查找表01/关键字(Key)定义：数据元素中用于标识和区分不同记录的核心数据项，是查找操作的依据。主关键字(PrimaryKey)能唯一标识数据元素，不可重复。例如：学生的“学号”、身份证号。次关键字(SecondaryKey)无法唯一确定数据元素，可能重复。例如：学生的“姓名”、“专业”。02/查找表(SearchTable)定义：由同一类型的记录（数据元素）构成的集合，是查找算法操作的对象。查询(Query)判定特定元素是否存在，返回布尔结果。检索(Retrieve)查找并获取元素的具体属性或完整信息。插入(Insert)向表中添加新元素，保持结构的完整性。删除(Delete)从表中移除指定元素，更新表的结构。顺序查找-原理01核心别称也被称作“线性查找”，是算法设计中最基础、最直观的查找策略。它无需对数据进行任何预处理（如排序），可直接对原始数据进行检索。02基本思想从数据序列的一端开始，依次将元素与目标值比较：

✔匹配成功：立即返回该元素的位置索引

✘遍历结束：返回查找失败的状态标识03适用场景该算法在以下场景中优势明显：

•待查找的数据规模较小

•数据元素为无序排列

•数据采用链式存储结构（无法随机访问）算法效率洞察顺序查找的平均时间复杂度为O(n)（n为数据元素个数）。虽然在数据量大时效率不高，但它实现简单、无前置条件，是处理小规模或无序数据时的首选方案，也是理解更复杂查找算法的基础。顺序查找-算法实现(带监视哨)核心技巧：设置“监视哨”在数组下标为0的位置预置待查关键字（Sentinel），将其作为查找循环的终止标志，替代传统的数组越界判断条件。核心优势：减少冗余判断避免在循环体内每次执行“是否越界”的逻辑判断，减少约1/3的比较次数，在高频查找场景下显著提升算法效率。01.哨兵赋值将待查关键字kx存入数组首位data[0]，作为查找失败的终止点。02.逆向遍历从数组有效长度的末尾（length）开始，向前逐个元素进行比对。03.关键字比对若data[i].key==kx成立，则找到目标，退出循环。04.返回结果返回当前下标i；若i=0，代表查找失败（哨兵位置）。算法伪代码实现(C语言风格)：intS_Search(S_Table*t,KeyTypekx){

t->data[0].key=kx;//1.设立监视哨

inti=t->length;//2.从表尾开始查找

while(t->data[i].key!=kx)i--;//3.无需判断越界

returni;//返回位置，0表示未找到

}顺序查找-性能分析01查找成功·平均查找长度•最好情况：目标在首位，仅需比较1次

•最坏情况：目标在末位，需比较n次

•平均情况：等概率下，ASL=(n+1)/202查找失败·固定比较次数需遍历至监视哨（哨兵）才判定失败，比较次数固定为n+1次。

公式：ASL_failure=n+1

注：此结论适用于设置了哨兵的优化版本。03时间复杂度：O(n)算法效率与数据规模n呈线性关系。随着数据量的增加，平均查找长度也会线性增长，因此在数据量较大时性能会显著下降。04核心优劣势对比✅优点：实现简单，对数据结构无要求（有序或无序均可）。

❌缺点：查找效率低，平均查找长度大，不适用于海量数据。💡适用场景：仅推荐在数据量较小（如n<50）或数据本身无序且无法排序的场景下使用。对于大规模有序数据，建议优先选择折半查找等更高效的算法。折半查找-原理算法别称：二分查找一种针对有序数组的高效查找算法，时间复杂度为O(logn)，效率远高于顺序查找。核心前提：有序顺序表数据必须按关键字有序排列（升序或降序），且存储在连续的顺序表中，支持随机访问。01.划定查找范围初始化指针：设`low`为查找区间的起始索引，`high`为结束索引，初始覆盖整个数组范围。02.计算中间位置通过公式`mid=(low+high)//2`计算中间索引，将当前查找区间平分为左右两个子区间。03.比较并缩小区间若目标值<中间值，调整`high=mid-1`（搜左半区）；若目标值>中间值，调整`low=mid+1`（搜右半区）；相等则查找成功。04.终止条件重复步骤2-3，直到找到目标元素返回索引；若出现`low>high`，说明目标不存在，查找失败。折半查找-示例待查有序序列：[7,13,30,35,42,54,67,76,88,89,96]查找成功案例(目标值kx=35)①初始范围low=1,high=11→mid=6(值为54)

35<54，舍去右半区，调整high=5②新范围low=1,high=5→mid=3(值为30)

35>30，舍去左半区，调整low=4③最终范围low=4,high=5→mid=4(值为35)

35==35，匹配成功，返回索引4查找失败案例(目标值kx=87)①初始范围low=1,high=11→mid=6(值为54)

87>54，舍去左半区，调整low=7②新范围low=7,high=11→mid=9(值为88)

87<88，舍去右半区，调整high=8③最终范围low=7,high=8→mid=7(值为76)

87>76，调整low=8→low>high，区间为空，查找失败折半查找-算法实现intBinary_search(S_T*table,KeyTypetarget){intlow=0,high=table->length-1,mid;while(low<=high){mid=low+(high-low)/2;//避免溢出，等价于(low+high)/2if(table->data[mid].key==target)returnmid;elseif(table->data[mid].key>target)high=mid-1;elselow=mid+1;}return-1;//查找失败返回-1}💡核心要点：仅适用于有序的顺序表结构。通过不断将待查区间缩小为原来的一半，时间复杂度为O(log₂n)，相比顺序查找的O(n)效率有指数级提升。注意循环条件为low≤high，避免死循环或遗漏。折半查找-性能分析(判定树)判定树是分析折半查找效率的直观工具。树中每个节点代表一次关键码比较，从根节点到目标节点的路径长度即为查找所需的比较次数，树的高度决定了最坏情况下的查找代价。判定树模型逻辑将查找过程抽象为二叉树，节点代表比较操作，路径对应查找序列。比较次数等于节点所在层数，成功查找的路径是从根到目标节点的唯一路径。关键性能指标树高满足h=⌊log₂n⌋+1，最坏情况下需比较h次；平均查找长度约为log₂(n+1)-1；算法时间复杂度为O(logn)，效率远高于顺序查找。特性总结与局限优势：查找速度极快，效率稳定；局限：仅适用于有序的顺序表，插入和删除操作需要移动大量元素，因此不适用于频繁变动的数据集。分块查找-原理别称：索引顺序查找——融合“顺序查找”的灵活与“折半查找”的高效，是一种分阶段优化的查找策略，平衡了静态查找表的维护成本与查询效率。01数据分块规则•块内无序：单块内部元素无需排序，大幅降低数据插入与删除的维护成本。

•块间有序：块与块之间严格递增（如第i块的最大值<第i+1块的最小值），为快速索引提供基础。02构建索引表•索引项构成：每块对应一条索引，记录【块内最大关键字】和【块起始地址】。

•表特性：索引表整体按关键字升序排列，支持折半查找，实现对目标块的快速定位。STEP01：索引表定位块区间利用索引表的有序性，通过折半或顺序查找，快速锁定目标元素可能存在的块，将查找范围从全表缩小到单个块。STEP02：块内顺序查找元素进入定位到的具体块后，执行顺序查找。由于块内元素数量远小于全表，查找效率依然能得到有效保证。分块查找-示例核心机制：分块有序策略将线性表划分为若干“块”，块内元素允许无序，但块间必须保持有序（前一块的最大关键字小于后一块的最小关键字）。通过建立索引表快速缩小查找范围，再在目标块内进行顺序查找，平衡了查找效率与数据维护成本。01数据切块与索引建立将原始表分为3个独立块，提取每块的最大关键字建立索引：

•块1[14,30,8,22,18]→最大值30|块2[43,62,49,35,52]→最大值62|块3[90,78,71,80,85]→最大值9002索引表查询：锁定目标块目标值kx=49，在索引表中比较得：30<49<62。由此快速判定，49必然落在块2中，无需查看其他块。03块内检索：精准定位进入块2的具体数据[43,62,49,35,52]进行顺序查找，最终在块内第3个位置找到元素49，查找成功结束。分块查找-性能分析核心定义：平均查找长度总平均查找长度等于索引表查找与块内查找长度之和：

ASL=ASL(index)+ASL(block)

前者为查索引的平均长度，后者为在对应块内查找的平均长度。分析模型与前提假设设表长为n，均匀分为b块，每块含s个记录(n=b×s)。

通常假设：索引表采用折半查找以提高效率，而块内元素无序，采用顺序查找。平均查找长度公式基于上述模型，分块查找的平均查找长度近似为：

ASL≈log₂(b+1)+s/2

该公式量化了块数与块大小对整体查找效率的影响程度。算法特性与权衡优点：块内无序，插入/删除无需移动大量元素，维护成本低；效率介于顺序查找与折半查找之间。

缺点：需额外存储空间建立索引表；块的大小s是关键参数，选择不当会影响性能。静态查找表总结01顺序查找时间O(n)：线性扫描，随数据量增大效率线性降低空间O(1)：无需额外辅助空间，原地查找核心特点：实现最简单，不要求数据有序；但在数据量大时性能最差，仅适用于小规模或无序数据的场景。02折半查找时间O(logn)：效率极高，每次比较排除一半数据空间O(1)：仅需常数级辅助空间，效率最优核心特点：要求数据必须有序；插入和删除操作代价高，适合数据相对稳定、且需要频繁查询的静态表。03分块查找时间O(logb+s)：效率介于两者之间，b为块数，s为块长空间O(b)：需额外存储索引表，空间开销适中核心特点：块间有序，块内无序；插入删除方便，兼顾了动态性与查询效率，适合动态变化的大型线性表。💡选型建议：根据数据规模、有序性及动态性需求综合考量，静态高频查询选折半，动态数据选分块，小数据量直接用顺序查找。静态查找表-练习练习01·折半查找已知有序表：

[1,3,5,7,9,11,13,15,17,19]目标关键字：11任务：

1.手动模拟查找过程；

2.计算并统计比较次数。练习02·分块查找索引表：[10,20,30]

数据块：[1,5,8]、[12,14,18]、[22,25,28]目标关键字：14任务：

描述分块查找的两个核心步骤：

索引定位与块内查找。练习03·算法抉择场景：处理一个长度为100的无序数据表，要求实现高效查找。思考：1.你会优先选择哪种查找算法？

2.请说明选择理由及复杂度分析。💡思考提示：结合算法的时间复杂度、数据预处理成本及空间复杂度进行综合考量。动态查找表-概述01核心痛点在数据频繁插入和删除的高频场景下，传统静态结构难以兼顾查找速度与维护成本，性能瓶颈显著。02现实挑战静态查找表在动态更新时，为维护数据有序性需频繁移动元素，时间复杂度高，在海量数据下性能损耗巨大。03破局之道引入树形结构组织数据，利用其独特的动态分支特性，打破线性结构的局限，实现插入、删除与查找的高效协同。本章核心知识图谱二叉排序树(BST)基于二叉树“左小右大”的核心特性构建，是实现动态数据快速检索、插入与删除的基础结构。平衡二叉树(AVL)通过旋转机制主动维持树的高度平衡，彻底解决了二叉排序树在极端数据分布下的性能退化问题。B-树与B+树专为磁盘等外存设计的多叉平衡树，有效减少I/O次数，是现代数据库索引与文件系统的底层基石。二叉排序树(BST)-定义01核心定义一棵二叉树，或为空，或满足以下递归性质：

1.左子树所有结点值小于根结点值；

2.右子树所有结点值大于根结点值；

3.左右子树也均为二叉排序树。02关键特性对BST进行中序遍历，将得到一个严格的升序序列。这是判断二叉树是否为BST的重要依据，也是其支持高效查找、排序操作的理论基础。📊中序遍历输出示例序列结果：1→3→4→6→7→8→10→13→14

逻辑：严格遵循“左子树→根节点→右子树”的访问顺序，利用此特性可轻松实现数据的有序化输出。BST-查找操作01/核心查找逻辑❶若树为空，则查找失败，直接返回空。

❷若目标值等于根节点关键字，查找成功，返回该节点。❸若目标值小于根节点关键字，在左子树中继续查找。

❹若目标值大于根节点关键字，在右子树中继续查找。递归实现：代码简洁，逻辑直观defsearch_bst(node,key):

ifnodeisNoneornode.key==key:

returnnode

returnsearch_bst(node.left,key)ifkey<node.keyelsesearch_bst(node.right,key)迭代实现：避免栈溢出，性能更优defsearch_bst(root,key):

current=root

whilecurrent:

ifcurrent.key==key:returncurrent

current=current.leftifkey<current.keyelsecurrent.right

returnNoneBST-插入操作01基本思想1.查找定位：从根出发，按“左小右大”规则查找目标值kx。2.去重校验：若找到相同值，终止操作，避免树中出现重复关键字。3.空位插入：若查找失败，将kx作为新节点挂载到查找路径末端的空位置。02核心步骤1.初始化：指针指向根节点，开始遍历。2.循环查找：比较当前节点值，小于则向左，大于则向右，直到找到空的父节点。3.挂载节点：创建新节点，根据大小关系设为父节点的左/右孩子。03实例：插入5•查找路径：根节点8→左子3→右子6→左子4。•判定逻辑：5>4，且4无右孩子。•结果：将新节点5挂载为节点4的右孩子，树结构保持有序。💡关键结论：BST的插入操作本质上是一次“失败的查找”过程，新节点始终作为叶子节点加入，这保证了二叉搜索树的有序性不被破坏。BST-构造过程二叉搜索树（BST）的构造本质是逐个插入关键字序列中的元素，并严格遵循“左子树节点值小于根节点，右子树节点值大于根节点”的核心规则进行位置安放。演示序列：[8,3,10,1,6,14,4,7,13]——按顺序依次插入，逐步建立层级关系01-03基础骨架搭建

•插入8作为根节点，开启结构

•插入3(小)→8的左孩子

•插入10(大)→8的右孩子04-06左右子树延伸

•插入1(小)→3的左孩子

•插入6(大)→3的右孩子

•插入14(大)→10的右孩子07-09末梢节点补全

•插入4(小)→6的左孩子

•插入7(大)→6的右孩子

•插入13(小)→14的左孩子核心规律：BST的最终树形由插入顺序决定。同一组数据，不同的插入顺序会形成结构迥异的二叉搜索树，这对树的高度及查找效率有直接影响。BST-删除操作(情况一：删除叶子结点)核心特征待删除的目标结点为叶子结点，即该结点既没有左子树，也没有右子树，处于二叉搜索树的末端位置。

这是BST删除操作中逻辑最简单、无需复杂结构调整的基础场景。执行步骤1.定位节点：找到待删结点z及其直接父结点p。

2.断开连接：将父结点p中指向z的指针置为NULL。

3.资源回收：释放结点z占用的内存空间，避免内存泄漏。场景示例以二叉搜索树中的结点1为例：

•结点1是叶子，无左右子节点。

•其父结点为3，是结点1的直接上级。

•操作：将父结点3的左指针设为NULL，随后释放结点1的内存。💡核心要点：叶子结点无后续子树依赖，删除时仅需切断与父结点的引用关系，不会影响树的整体结构平衡，是最基础的删除场景。BST-删除操作(情况二：删除只有一棵子树的结点)01/触发条件待删除结点z仅拥有左子树或右子树其中之一。

此场景下无需寻找后继或前驱结点，只需通过简单的指针重定向即可完成删除，是BST删除中逻辑最直接的情况。02/执行步骤①定位：找到目标结点z及其直接父结点p；

②重连：将z的唯一子节点挂载到p的对应位置；

③释放：删除原结点z，回收内存空间。03/实例解析以删除值为10的结点为例：

1.结点10仅有右子树14；

2.将其父结点8的右指针指向14；

3.移除结点10，树结构仍满足BST有序性。💡核心心法：这是典型的“子承父业”模式。因为被删结点只有一个子节点，直接将该子节点提升到被删位置，既保证了树的连通性，又因BST的有序性，子树的所有节点必然都大于或小于父节点，从而维持了树的性质。BST-删除操作(情况三：删除有两棵子树的结点)核心场景：待删除结点z同时拥有左、右子树，无法直接移除。需通过“值替换+删除替代节点”的策略，将其降级为“删除叶子节点”或“删除单孩子节点”的简单情况。方法一：中序前驱法(左子树最大值)1.查找：找到待删结点z的中序前驱s（左子树中最右侧的最大结点）。

2.覆盖：将结点s的值复制到结点z的位置。

3.移除：删除原前驱结点s（s至多有一个左孩子，转化为情况一/二）。方法二：中序后继法(右子树最小值)1.查找：找到待删结点z的中序后继s（右子树中最左侧的最小结点）。

2.覆盖：将结点s的值复制到结点z的位置。

3.移除：删除原后继结点s（s至多有一个右孩子，转化为情况一/二）。📝实例演示：删除二叉搜索树中的关键值3前驱法：找左子树最大值1→替换根节点3→删除原1结点。后继法：找右子树最小值4→替换根节点3→删除原4结点。BST-性能分析01.平均情况：平衡形态当BST结构趋于平衡时，节点分布均匀，其查询效率与折半查找算法相当，是理想的使用场景。时间复杂度O(logn)平均查找长度≈log₂(n)02.最坏情况：退化为链表若插入序列本身有序（升序/降序），BST将失去树形特征，退化为线性单链表，查询效率显著降低。时间复杂度O(n)平均查找长度(n+1)/2关键洞察：形态决定性能，平衡化是破局关键BST的性能并非恒定，而是高度依赖于其结构形态。为规避有序插入带来的性能劣化问题，必须引入**自平衡机制**（如AVL树、红黑树），确保在动态增删操作后，树始终保持近似平衡，从而稳定维持高效的查找效率。平衡二叉树(AVL)-定义图示为一棵标准的AVL树结构。其核心特征是树中每个节点的左右子树高度差都被严格限制在1以内，从而保证了树的高度始终为O(logn)级别。核心定义：解决BST性能退化的自平衡机制平衡二叉树（AVL树）是一种特殊的二叉排序树。它要求树上任意节点的左、右子树的高度差的绝对值不超过1。这种约束彻底解决了普通BST在插入有序数据时退化为链表（O(n)时间复杂度）的问题。平衡因子(BF)：衡量树平衡的标尺计算公式：BF(node)=左子树高度-右子树高度。在AVL树中，所有节点的BF值只能是-1、0、+1。一旦某个节点的BF绝对值大于1，就称该树“失去平衡”，需要通过旋转操作来恢复平衡。平衡判定：临界条件与失衡示例平衡场景：节点30的左子树高2，右子树高1，高度差为1，符合AVL定义。

失衡场景：节点30仅有左子树（高度为2）而右子树为空（高度为0），BF=2，触发失衡，必须进行旋转调整。AVL-失衡与调整01失衡判定当插入或删除结点后，导致某个结点的平衡因子绝对值大于1（即|BF|>1），此时树的平衡状态被打破。02核心定位从插入/删除的结点开始向上追溯，找到的第一个失衡结点作为根的子树，它是我们需要调整的最小目标单元。03调整原则对最小不平衡子树执行旋转操作，这不仅能恢复树的高度平衡，还能严格保持二叉搜索树（BST）的有序性。LL型：右单旋插入在失衡结点的左孩子的左子树。执行一次右旋，将失衡结点的左孩子提升为新根，原根作为其右子树。RR型：左单旋插入在失衡结点的右孩子的右子树。执行一次左旋，将失衡结点的右孩子提升为新根，原根作为其左子树。LR型：先左后右双旋插入在失衡结点的左孩子的右子树。先对左孩子进行左旋转化为LL型，再对原失衡结点进行右旋。RL型：先右后左双旋插入在失衡结点的右孩子的左子树。先对右孩子进行右旋转化为RR型，再对原失衡结点进行左旋。AVL-LL型旋转(右单旋转)🔍触发条件：左子树的左子树过重当失衡节点A的平衡因子为+2，且其左孩子B的平衡因子为+1时，判定为LL型失衡，需执行**右单旋转**操作以恢复平衡。01.转移右子树(BR)将节点B的右子树BR摘下，挂载为原根节点A的左子树，保持二叉搜索树的有序性。02.提升节点B为新根将原根节点A作为节点B的右子树，此时B成为该子树的新根节点，完成结构调整。03.更新平衡因子将新根B和原根A的平衡因子统一置为0，整棵子树恢复平衡状态。💡核心逻辑：右旋减负LL型旋转是最基础的自平衡操作，通过“右单旋”将过高的左分支向上提升，从而降低整棵树的高度差。这一操作保证了AVL树始终维持在O(logn)的高度，确保了查询和插入的高效性。AVL-RR型旋转(左单旋转)01/失衡判定条件当失衡节点A的平衡因子为-2，且其右孩子B的平衡因子为-1时，判定为RR型失衡。这意味着树的右侧分支深度远超左侧，需通过左单旋转恢复平衡。02/三步旋转操作法1转移子树：将节点B的左子树(BL)挂载为A的右子树。2节点降级：将原根节点A调整为新根节点B的左孩子。3确立新根：节点B正式成为该子树的新根节点。结构优化效果旋转后，树的高度减少一层，完美解决了右子树过重的问题。此操作保持了二叉搜索树的有序性，且仅涉及常数次指针修改，时间复杂度为O(1)，是维持AVL树平衡的高效手段。AVL-LR型旋转(先左后右双旋转)01失衡场景判定当根节点A的平衡因子为+2（左重），且其左孩子B的平衡因子为-1（右重）时触发。这是一种“左偏后右拐”的折线型失衡，需通过双旋转修正。02双旋转执行步骤STEP1·左单旋(针对节点B)将B的右孩子C提升为该子树的根，B下沉为C的左子节点，消除B的右重，将结构转化为标准的LL型失衡。STEP2·右单旋(针对节点A)将C提升为整棵树的新根，A下沉为C的右子节点，彻底修复A的左重失衡，恢复树的全局平衡。💡核心逻辑：折线→直线→平衡LR型旋转的本质是将“折线型”的失衡结构，通过两次单旋转转化为“直线型”结构。这不仅修复了当前的失衡，还确保了旋转后所有节点的平衡因子回到[-1,0,1]的合法区间，从而保证了AVL树的高效查询性能。AVL-RL型旋转(先右后左双旋转)失衡触发条件当根节点A的平衡因子为-2（右侧子树过重），且其直接右孩子B的平衡因子为+1（左侧子树过重）时，即触发RL型失衡模式，需执行双旋转修正。双旋转调整执行步骤STEP1(右旋)：以失衡节点的右孩子B为轴心，进行一次LL型旋转（右单旋），将其左子节点提升，修正局部失衡。STEP2(左旋)：以原失衡节点A为轴心，进行一次RR型旋转（左单旋），完成整棵树的平衡恢复与结构重组。结构演化示意图原理总结：这是一种“先修正子树，再修正根”的策略。通过两次相反方向的旋转，将深层的失衡因子向上传递并消解，确保树的左右子树高度差始终不超过1，维持AVL树的高效查询性能。AVL-插入与调整示例初始构建：依次插入序列[12,24,37,53]，此时树的形态完全符合AVL树的平衡条件（所有节点平衡因子BF∈{-1,0,1}），树结构稳定，无需进行任何旋转调整。01插入与失衡触发将节点45插入至53的左子树位置。向上回溯检查平衡因子：发现节点37的BF变为-2（超出平衡范围），节点53的BF变为+1，树的平衡性被打破。02定位失衡类型确定以37为根的子树为“最小不平衡子树”。因新节点插入在失衡节点的右孩子的左子树上，判定为RL型失衡，这是双旋转的典型场景。03双旋转修复平衡执行“先右后左”的双旋转：①对53节点做右单旋转；②对37节点做左单旋转。最终45成为新子树根，37和53分别为其左右子节点，树恢复平衡。核心规律：RL型失衡的调整口诀是“先右旋、后左旋”。通过双旋转操作，将最小不平衡子树的高度差修正为≤1，从而保证AVL树在动态插入后仍能维持O(logn)的高效查询与操作性能。AVL-性能分析高度约束对于包含n个节点的AVL树，其最大高度被严格限制，避免退化为链表：h≈1.44·log₂(n+2)-1.328这一数学特性从根本上保证了树的平衡性，为高效查询奠定基础。效率表现得益于严格的平衡条件，核心操作的时间复杂度始终保持在对数级别：O(logn)无论是查找、插入还是删除操作，均展现出优异的性能稳定性，适合处理大规模动态数据。特性权衡优点：保证了最坏情况下的查找效率，数据分布极其均衡，适合对查询速度要求严苛的场景。缺点：维护成本高，插入和删除时需频繁进行旋转调整，实现逻辑较为复杂。总结：AVL树是计算机科学中经典的自平衡二叉搜索树（Self-balancingBST），它牺牲了部分插入和删除的效率来换取极致的查询稳定性，是理解红黑树等高级平衡树结构的重要基石。B-树-定义B-树是专为磁盘等外存设备设计的多路平衡查找树。它通过减少树的高度来降低磁盘IO次数，从而在处理大规模数据时，实现比二叉查找树更高效的查询性能。01节点容量：每个节点最多拥有m棵子树（m为阶数），承载多个关键字。02根节点：非空树的根节点至少有2棵子树，是结构的起点。03内部节点：除根与叶外，节点至少有⌈m/2⌉棵子树，维持结构紧凑。04平衡特征：所有叶子节点都在同一层，保证了从根到叶的路径长度一致。图示：5阶B-树结构示例如图所示，B-树呈现出典型的层级结构。根节点位于顶端，中间为分支节点，底层为叶子节点。这种结构确保了树的高度远低于二叉查找树，从而在磁盘读写时极大减少了IO开销，这是数据库索引等场景中广泛使用B-树的根本原因。B-树-查找操作01核心查找逻辑起点定位

查找操作始终从B-树的根结点开始，这是整个查找过程的初始入口。结点检索与分支

在当前结点内进行顺序或折半查找；若未命中，根据关键字大小关系，选择对应的子树指针进入下一层。终止判定

找到目标关键字则查找成功；若遍历至叶子结点仍未找到，则查找失败。02实战示例：查找关键字71Step1：根结点判定

访问根结点[51]，比较得71>51，因此选择右子树继续向下查找。Step2：层级深入

进入结点[66,75]，比较得66<71<75，选择中间子树继续。Step3：成功命中

进入结点[70,71,72]，在结点内找到目标关键字71，查找结束。B-树-插入操作01核心原则插入操作始终发生在叶子结点。这是B-树保持平衡的基石，确保新元素从底层融入，不会直接干扰上层结构，为后续的自平衡机制提供了稳定的起点。02执行步骤1.定位：从根节点向下搜索，找到待插入的目标叶子结点。

2.插入：将关键字按升序插入该结点的正确位置。

3.校验：若结点关键字数n>m-1，则触发溢出分裂。03分裂机制1.取中值：mid=⌊m/2⌋，以此为界拆分结点。

2.上移：中间关键字(key[mid])晋升至父结点。

3.递归：若父结点溢出则重复此过程，直至根结点，树高加1。分裂是B-树实现自平衡的核心手段。这种向上“冒泡”的分裂机制，保证了树的高度始终保持在log_mN的级别，从而在最坏情况下也能维持高效的O(logn)查找、插入和删除性能。B-树-插入示例场景设定：在m=5（5阶）B-树中，尝试将关键字71插入到一个已满的叶子结点[66,68,70,72]，从而触发经典的节点分裂机制。01.插入触发溢出插入后节点内容变为[66,68,70,71,72]，此时关键字数量n=5，超过了m-1=4的限制，节点发生溢出，必须进行分裂操作。02.定位分裂基准值计算中间位置mid=3（1-based索引），选取该位置的关键字70作为分裂的基准元素，该元素将被提升到父节点中。03.拆分为左右新节点原节点以基准值为界拆分：左子节点保留基准值左侧的[66,68]，右子节点保留基准值右侧的[71,72]，形成两个合法的子节点。04.提升与结构重构将基准关键字70插入到父节点中，并将拆分后的左右新节点设置为70在父节点中的左右子节点，完成整棵树的平衡调整。B-树-删除操作01核心原则：将非叶删除转化为叶删除•非叶结点：用其中序前驱或后继关键字替换目标值，将问题转化为删除叶子结点。

•叶子结点：若删除后关键字数量仍满足要求，则直接删除，操作完成。02触发调整：检查是否发生“下溢”删除后若结点关键字数n<⌈m/2⌉-1（m为B-树的阶数），则违反了B-树的结构性质，必须进行重新平衡调整。策略A：向兄弟借位(Borrow)若兄弟结点有多余的关键字（数量>最小值），通过父结点中转，从兄弟结点“借”一个关键字补充到当前结点，从而恢复平衡。策略B：与兄弟合并(Merge)若兄弟无多余关键字，将当前结点与兄弟结点合并，并吸收父结点中的分隔关键字。若父结点因此也发生下溢，则需递归向上继续调整。B+树-定义与特点核心应用：数据库索引基石广泛应用于现代数据库系统，是MySQLInnoDB引擎的默认索引结构。它完美平衡了随机查找与范围查询的性能，能够高效管理海量数据，是构建高性能存储引擎的关键数据结构。B+树是B-树的一种优化变形，专为磁盘和文件系统设计。它通过将所有数据记录下沉到叶子节点，并优化非叶节点的结构，极大提升了索引效率和空间利用率。关键字结构更紧凑n棵子树对应n个关键字，相比B-树减少了冗余存储，使非叶节点能容纳更多索引项，有效降低树的高度。数据仅存于叶子节点非叶节点仅作为索引指引，不存储实际数据。这使得索引层更轻量，同时保证了数据的集中管理。叶子节点链式相连所有叶子节点通过指针形成有序链表，支持快速的范围查询（如BETWEEN操作），无需回溯上层节点。查询路径稳定性高查找过程必须到达叶子节点才结束，保证了无论查找成功与否，IO次数相对稳定，避免了性能抖动。动态查找表总结01二叉查找树(BST)结构：基础二叉树结构，左子树值小于根，右子树值大于根，结构简单但可能退化为链表。性能与场景：平均O(logn)，最坏O(n)；适用于数据动态维护，适合随机查询但需注意平衡性。02平衡二叉树(AVL)结构：严格平衡的二叉树，所有节点平衡因子BF∈{-1,0,1}，失衡时通过旋转自动调整。性能与场景：稳定的O(logn)复杂度；适合对查询速度要求极高、数据频繁更新且追求稳定性的场景。03多路平衡查找树(B-树)结构：m阶多路平衡树，每个节点可包含多个关键字，有效降低树的高度，大幅减少IO操作。性能与场景：时间复杂度O(log_mn)；专为磁盘等外存设备设计，适合处理大规模数据的索引。04B+树(B-树变种)结构：仅叶子节点存储完整数据，非叶子仅作索引，且叶子节点通过链表相连，便于范围查找。性能与场景：查询效率稳定且范围查询极快；是现代数据库（如MySQL）和文件系统的核心索引结构。动态查找表-练习01BST基础构造实战给定初始为空的二叉查找树(BST)，依次插入关键字序列：

5,3,8,2,4,7,9

请手动画出最终的树形态结构。💡核心逻辑：严格遵循“左子树<根<右子树”原则，从根节点开始逐层向下查找插入位置。02BST节点删除（后继法）基于题1构建的BST，执行删除关键字5的操作。

要求：详细描述使用“后继法”的删除过程，并画出删除后的树结构。💡关键步骤：找到待删节点右子树的最小节点（后继），替换其值，再删除该后继节点。03AVL树失衡与调整向空AVL树依次插入10,20,30。

分析：会发生哪种类型的失衡？应采取何种旋转方式调整？画出调整前后对比。💡调整策略：属于典型的LL型失衡，需对失衡的最小子树的根节点进行“右旋”操作。📝练习建议：先在草稿纸上快速勾勒结构，重点关注节点变动时的指针引用变化，这是理解树操作的关键。哈希表-概述核心思想：以空间换时间

通过哈希函数将关键字直接映射到存储地址，避免了传统查找的比较过程，从而在理想情况下实现O(1)的时间复杂度，是解决高效查找问题的经典方案。01哈希函数(HashFunction)建立关键字到存储地址的映射关系：f(key)=address。它是哈希表的核心算法，决定了数据的存储位置，理想的哈希函数应尽可能减少冲突。02哈希表(HashTable)根据哈希函数构建的一种线性数据结构，由“哈希地址”和对应的“记录值”组成。它是实现快速存储和查找操作的物理载体，通常基于数组实现。03冲突(Collision)不同的关键字被哈希函数映射到同一个存储地址的现象，即key₁≠key₂但f(key₁)=f(key₂)。由于关键字空间远大于地址空间，冲突是不可避免的。04同义词(Synonyms)当多个不同的关键字通过哈希函数计算出相同的哈希地址时，这些关键字就互为同义词。同义词的存在是产生冲突的根本原因，需要专门的方法来处理。哈希函数的构造方法核心目标：构造一个均匀分布的哈希函数，使关键字尽可能均匀地映射到哈希表的地址空间中，从而最大化减少冲突，提升数据存取效率。01直接定址法公式：f(key)=a·key+b。原理简单，但仅适用于关键字分布连续的场景，易造成存储空间的浪费。02数字分析法选取关键字中分布最均匀的若干位作为哈希地址。前提是关键字集合已知且各位分布具有明显规律。03除留余数法(最常用)公式：f(key)=key%p。p通常取小于等于表长的素数，能使关键字分布更均匀，是应用最广泛的方法。04平方取中法将关键字平方后截取中间几位。让关键字的每一位都参与地址计算，适用于关键字各位分布不均的情况。05折叠法将关键字分割为等长的几部分后叠加求和。适用于关键字位数较多，且每一位的分布都不够均匀的场景。06随机数法公式：f(key)=random(key)。利用随机函数生成哈希地址，特别适合关键字长度不一、分布无规则的动态集合。处理冲突的方法核心问题：当不同的关键字通过哈希函数计算出相同的存储地址时，如何为这些“同义词”寻找新的可用存储位置，以确保哈希表的正确存储与高效检索。01开放地址法冲突发生时，按公式(Hash(key)+di)%m寻找下一个空槽。包含线性探测、二次探测等方式，实现简单但易产生“堆积”现象，影响查找效率。02拉链法(Chaining)将哈希地址相同的元素链入同一个单链表，表中单元存储链表头指针。该方法不会产生聚集，处理冲突简单，是解决哈希冲突最常用的方法之一。03双哈希法利用第二个哈希函数计算探测增量di，使探测序列更均匀，能有效减少聚集问题。但缺点是哈希函数设计难度大，且每次探测的计算成本相对较高。04公共溢出区设立基础表和独立的溢出表，冲突元素统一存入溢出表。查找时先查基础表，失败则查找溢出表。实现简单，适合冲突较少、数据稳定的场景。开放地址法-线性探测示例参数设定：哈希表长度m=11•哈希函数f(key)=key%11•关键字序列[1,13,34,38,33,27,22]💡核心原理

当哈希地址发生冲突时，从冲突地址开始，依次向后探测，直到找到下一个空闲地址或探测完整个表。这种方式能有效解决“地址冲突”问题。🔍典型冲突插入过程解析关键字34(首次冲突)

计算得地址1(冲突)→探测+1到地址2(仍冲突)→探测+2到地址3(空闲，存入)关键字22(连续冲突)

计算得地址0(冲突)→连续探测1/2/3均冲突→探测+4到地址4(空闲，存入)📊最终哈希表存储状态Addr0

33Addr1

1Addr2

13Addr3

34Addr4

22Addr5-6

38/27拉链法示例01/核心参数设定哈希表长度：m=11|哈希函数：f(key)=key%11

待插入关键字序列：[1,13,34,38,33,27,22]02/最终链式存储结构地址022→33→NULL

(解决22与33的冲突)地址134→1→NULL

(解决34与1的冲突)地址213→NULL

(无冲突，直接存储)地址527→38→NULL

(解决27与38的冲突)插入关键字34(冲突处理)计算得哈希地址为1，发现该地址已有元素1。执行“拉链”操作，将34插入到该地址链表的头部，形成链式结构。插入关键字27(冲突处理)计算得哈希地址为5，发现该地址已有元素38。同理，将27插入到该地址链表的头部，解决哈希冲突。哈希表的查找与性能分析01查找核心流程1.计算地址：利用哈希函数将关键字映射到表中对应位置。

2.冲突处理：若发生冲突，按既定策略（线性探测、拉链法等）沿地址序列比对，直至找到目标或判定不存在。02效率决定要素•哈希函数：均匀性越高，冲突概率越低。

•冲突策略：拉链法通常比开放地址法更稳定。

•装填因子α：核心指标，α越大冲突风险越高。03ASL关键特性平均查找长度(ASL)几乎与元素总数无关，主要取决于装填因子α。α越小，哈希表的查找效率越高，其平均查找长度越接近常数级。📊查找成功的平均查找长度(ASL)线性探测：ASL≈(1+1/(1-α))/2

拉链法：ASL≈1+α/2❌查找失败的平均查找长度(ASL)线性探测：ASL≈(1+1/(1-α)²)/2

拉链法：ASL≈α哈希表总结01哈希函数构造方法直接定址法

优点：计算极简，理论上无冲突；缺点：空间浪费大，仅适用于关键字分布连续的场景，对离散或大范围关键字不友好。除留余数法

优点：实现简单，分布均匀性好；缺点：哈希质量高度依赖模数p的选择（通常取素数）。这是最常用的通用构造方法。平方取中法

优点：充分利用关键字的每一位信息，减少冲突；缺点：计算稍复杂。适用于关键字位数较多且分布无明显规律的场景。02冲突处理策略对比开放地址法(OpenAddressing)

核心是“找下家”：发生冲突时，通过线性探测、二次探测或双重哈希寻找下一个空闲地址。

✅无需额外指针空间，数据存储紧凑；

❌易产生“二次聚集”，导致查找效率下降；删除操作复杂，需做墓碑标记。拉链法(Chaining)

核心是“挂链表”：将哈希到同一地址的元素组成一个链表（或红黑树）。

✅处理冲突简单，无聚集现象，删除操作方便，负载因子可大于1；

❌需要额外空间存储指针，极端情况下（如全冲突）退化为单链表，影响性能。哈希表-练习01线性探测实践条件设定：哈希表长度m=13，哈希函数为f(key)=key%13，采用线性探测法解决冲突。关键字序列：25,37,52,43,84,99,120,15,26,11,70,8任务：完成插入操作，并计算查找成功的平均查找长度(ASL)。02拉链法对比条件设定：沿用题1