北京师范大学数据结构教学资料 第7章-搜索结构

第7章搜索结构北京师范大学数据结构课程教学资料Contents本章内容概览搜索算法与数据结构的核心原理与实现方法01搜索基本概念与静态搜索表02二叉搜索树的原理与操作03AVL树的平衡旋转机制04散列表的构造与冲突处理CHAPTER01搜索基本概念与静态搜索表从搜索的定义、关键码概念到静态与动态环境的区分SearchFundamentals搜索的基本概念搜索是在数据集合中定位满足条件对象的核心操作，其效率直接决定了信息系统的性能表现。01搜索的本质是在数据集合中查找满足特定条件的数据对象，结果分为搜索成功（返回对象位置及详细信息）和搜索失败（返回失败标志）两种形态。两种结果02搜索结构由同一数据类型的对象组成，每个对象包含若干属性，其中关键码是能唯一标识该对象的核心属性，基于关键码的搜索结果具有唯一性。关键码03实际应用中搜索条件往往是多维度的，可基于非关键码属性进行搜索，但此时搜索结果可能不唯一，需要额外的筛选和排序机制。多维搜索SEARCHENVIRONMENTS静态环境与动态环境搜索操作所处的环境可分为静态和动态两类，二者的核心区别在于数据结构在执行插入、删除等操作时是否需要自动调整。环境类型直接决定了搜索结构的设计策略和算法选择。静态数据集合：有序、固定、只读静态搜索环境01搜索结构在插入和删除等操作的前后保持不变，数据集合一旦建立即固定，仅执行查询操作02可对数据预先排序以优化搜索效率，典型应用包括字典查询、静态配置表、只读数据库等场景03代表数据结构为静态搜索表，利用数组下标作为存储地址，支持顺序搜索和折半搜索等算法动态索引结构：频繁读写、自动调整动态搜索环境01搜索结构在执行插入和删除操作后将自动进行调整，结构可能随操作发生动态变化02需要在保持搜索效率的同时支持频繁的增删操作，典型应用包括数据库索引、缓存系统、路由表等03代表数据结构包括二叉搜索树、AVL树、B树和散列表等，各自通过不同机制维持高效的搜索性能DataStructure静态搜索表的类定义静态搜索表采用数组存储数据元素，利用下标作为存放地址。通过C++模板机制实现泛型编程，dataNode封装单个数据结点，dataList管理整个搜索表的生命周期与核心操作接口。01模板类dataNode<E,K>定义数据结点结构，E为数据元素类型、K为关键码类型，通过友元声明允许dataList类访问其私有成员02模板类dataList<E,K>管理搜索表整体，维护数据数组和当前元素个数，提供Search、Insert、Remove等核心操作接口03动态数组与内存管理默认数组大小defaultSize设为100，支持动态扩容；构造函数初始化空表，析构函数释放动态分配的内存资源04线性搜索算法根据给定关键码值k在数组中逐一比较，直到找到匹配元素或遍历完所有元素确认搜索失败为止SearchAlgorithm顺序搜索算法顺序搜索从表头逐一比较直到找到目标或遍历完毕，实现简单但效率有限。其平均时间复杂度为O(n)，适用于小规模或无法预排序的数据集，是理解更复杂搜索算法的起点。01从数组下标0开始逐一将元素关键码与目标值k比较，匹配成功则返回当前下标位置，遍历至末尾仍未匹配则返回搜索失败标志02最好情况O(1)即首次命中，最坏情况O(n)即遍历全部元素，搜索成功的平均比较次数为(n+1)/2次03引入"哨兵"技巧可在数组末尾放置目标值k，省去每步的边界检查判断，将循环内比较次数减半，提升约一倍的常数因子效率04对数据排列顺序无要求，适用于链表等非连续存储结构，但在大规模有序数据集中效率远低于折半搜索顺序搜索不同情况下的比较次数n=100时的理论比较次数ALGORITHM·SEARCH折半搜索（二分查找）折半搜索利用有序表的特性，每次比较将搜索范围缩小一半，实现O(logn)的对数级时间复杂度。它是分治思想在搜索领域的经典应用，也是衡量其他搜索算法效率的重要参照基准。有序前提搜索表必须按关键码有序排列，算法维护low和high两个指针界定当前搜索区间，每次取mid位置元素进行比较。mid=(low+high)/2三路判定等于目标值则搜索成功；小于则在左半区间继续搜索；大于则在右半区间继续搜索，逐步逼近目标。[low,mid-1]对数效率以n=100万为例最多仅需20次比较，相比顺序搜索的平均50万次比较，效率提升数万倍。O(log₂n)平衡判定树判定树是一棵平衡二叉树，树的高度即为最大比较次数，ASL成功约为log₂(n+1)-1。⌊log₂n⌋+1COMPARISON静态搜索方法性能对比顺序搜索与折半搜索各有适用场景：前者灵活但效率线性增长，后者高效但要求数据有序且顺序存储。顺序搜索与折半搜索综合对比比较维度顺序搜索折半搜索数据有序性要求无需有序必须按关键码有序存储结构顺序表或链表均可仅支持顺序存储（数组）搜索时间复杂度O(n)O(logn)平均成功ASL(n+1)/2≈log₂(n+1)-1插入操作代价O(1)直接末尾追加O(n)需移动元素删除操作代价O(1)标记删除即可O(n)需移动元素适用场景小规模、频繁增删、无序数据大规模、查询为主、有序数据折半搜索在查询性能上优势显著，但插入删除代价高，适合读多写少场景CHAPTER02二叉搜索树的原理与操作从树的有序性约束到搜索、插入、删除的完整实现DataStructure二叉搜索树的定义与性质二叉搜索树通过左小右大的有序性约束实现高效搜索，其中序遍历结果自然形成递增序列，时间复杂度与树高直接相关。01递归定义BST或是空树，或满足左子树关键码均小于根节点、右子树均大于根节点，且左右子树本身也是BST。递归结构有序约束02中序递增对BST执行中序遍历（左-根-右）可得关键码递增序列，因此也称二叉排序树。该性质是BST区别于普通二叉树的核心特征。左-根-右有序输出03搜索效率平衡时h=O(logn)，搜索O(logn)；退化为单链时h=O(n)，退化为顺序搜索。保持平衡是BST高效的关键。O(logn)依赖平衡04动态操作插入和删除均可在O(h)时间内完成，兼顾搜索效率与动态更新需求。无需重构整棵树即可维护有序性。O(h)时间动态维护DATASTRUCTURE二叉搜索树的搜索操作BST搜索从根节点出发，依据关键码大小关系沿左或右子树逐层下降，形成一条从根到叶的搜索路径。递归实现简洁优雅，迭代实现便于控制栈空间，两者的时间复杂度均为O(h)。搜索过程与比较逻辑从根节点开始比较：等于当前节点则返回成功；小于则递归搜索左子树；大于则递归搜索右子树三路分支递归与迭代实现递归实现代码简洁，每层将问题缩小至一个子树；迭代使用while循环和指针遍历，避免函数栈开销O(h)栈深搜索路径与复杂度路径为根到目标节点的下行路径，长度即比较次数；最好O(1)命中根节点，最坏O(n)退化为链表O(1)—O(n)搜索失败与插入位置失败时指针到达空节点（NULL），确定目标值不存在；该空节点位置恰好是插入该元素时应放置的位置NULL定位INSERTOPERATION二叉搜索树的插入操作BST插入操作先通过搜索定位目标关键码应处的位置，若不存在则在该空位创建新的叶子节点。插入过程不改变已有节点结构，始终维持BST的有序性质，时间复杂度与搜索一致为O(h)。01插入操作首先执行搜索过程：从根节点出发沿关键码大小关系向下查找，若发现相同关键码则拒绝重复插入并返回失败标志搜索定位02搜索失败时到达的空指针位置即为新节点的插入点，在此创建包含目标元素的叶子节点，将其链接到父节点的左或右孩子指针上空位插入03新插入的节点始终是叶子节点，不会影响已有节点的父子关系和相对位置，因此BST的左小右大性质在插入后仍然严格成立性质保持04递归实现中，Insert函数接收引用参数ptr，当ptr为NULL时创建新节点并赋值给ptr，自动完成与父节点的链接递归实现BinarySearchTree二叉搜索树的删除操作BST删除操作根据被删节点的孩子数量分为三种情况：叶子节点直接删除、单子节点用孩子替代、双子节点用中序前驱或后继的值替换后递归删除。第三种情况是算法设计的难点与重点。CASE01叶子节点被删节点无左右孩子，直接释放该节点内存，并将父节点对应的左或右指针置为NULL即可完成删除直接释放CASE02单子节点被删节点仅有左孩子或右孩子，将其唯一的孩子节点提升到被删节点的位置，直接与祖父节点建立链接关系孩子替代CASE03双子节点找到被删节点的中序前驱或后继，用其关键码值替换被删节点的值替换后问题转化为删除前驱或后继节点，退化为情况一或情况二处理递归删除PERFORMANCEANALYSIS二叉搜索树的性能分析BST的操作效率直接取决于树的高度h：平衡状态下h=O(logn)性能优异，但在有序输入下可能退化为链表使h=O(n)。这种退化风险是引入AVL树等自平衡结构的根本动机。BST不同形态下的搜索比较次数（n=1000）退化链表的最大比较次数是完全平衡树的100倍最好情况O(logn)BST接近完全二叉树，高度h≈log₂n，搜索、插入、删除的时间复杂度均为O(logn)，与折半搜索效率相当，是理想状态下的最优性能表现最坏情况O(n)输入数据有序时BST退化为单链结构，高度h=n，所有操作退化为O(n)，等同于顺序搜索，性能急剧下降平均情况≈1.386log₂n对n个元素的随机排列构建BST，期望高度O(logn)，搜索成功的平均比较次数约为2ln(n)，实际性能接近最优退化根源AVLBST不强制维护平衡条件，连续插入有序数据会导致树严重偏向一侧，需要引入平衡机制保证最坏性能CHAPTER03AVL树的平衡旋转机制从平衡因子定义到四种旋转操作的完整平衡化策略DataStructure·Self-BalancingBSTAVL树的定义与平衡因子AVL树通过约束每个节点的平衡因子绝对值不超过1来维持平衡，保证n个节点的树高度不超过1.44log₂(n+2)，从根本上避免BST退化。01自平衡二叉搜索树：在BST的有序性基础上增加平衡条件——每个节点的左右子树高度差的绝对值不得超过1。|hL−hR|≤102平衡因子BF：定义为节点左子树高度减去右子树高度，AVL树中每个节点的BF只能取三个合法值。BF∈{−1,0,1}03高度上界：n个节点的AVL树最大高度比完全二叉树的log₂n略大，但保证了对数级别的最坏情况性能。h≤1.44log₂(n+2)04维护开销：节点需额外存储平衡因子字段，每次插入或删除后需沿路径回溯检查并修复所有受影响节点的平衡状态。回溯修复AVLTree·ImbalanceTypes插入导致的四种不平衡类型AVL树插入新节点后可能出现四种不平衡形态：LL型和RR型可通过单旋转修复；LR型和RL型需要双旋转修复。SINGLEROTATIONLL·左左新节点插入在不平衡节点的左孩子的左子树上，三节点呈左斜直线，需执行右单旋转修复RR·右右新节点插入在不平衡节点的右孩子的右子树上，三节点呈右斜直线，需执行左单旋转修复DOUBLEROTATIONLR·左右新节点插入在不平衡节点的左孩子的右子树上，三节点呈折线形，需先左旋后右旋的双旋转修复RL·右左新节点插入在不平衡节点的右孩子的左子树上，三节点呈反折线形，需先右旋后左旋的双旋转修复AVLTree·Rotation左单旋转与右单旋转单旋转通过提升子节点、交换父子关系来消除直线型不平衡。右旋处理LL型：左孩子上升为根、原根降为右孩子；左旋处理RR型：右孩子上升为根、原根降为左孩子。旋转操作保持BST有序性且时间复杂度为O(1)。右单旋转（RotateR）适用场景LL型不平衡——新节点插入在不平衡节点A的左孩子B的左子树上，导致A的平衡因子变为+2。此时左子树高度比右子树高2层，需要通过右旋重新平衡。操作步骤将B提升为子树新根节点，B的右子树转为A的左子树，A降为B的右孩子，最后更新A和B的平衡因子。旋转后子树高度恢复，BST有序性保持不变。LL·BF=+2左单旋转（RotateL）适用场景RR型不平衡——新节点插入在不平衡节点A的右孩子B的右子树上，导致A的平衡因子变为−2。此时右子树高度比左子树高2层，需要通过左旋重新平衡。操作步骤将B提升为子树新根节点，B的左子树转为A的右子树，A降为B的左孩子，最后更新A和B的平衡因子。旋转后子树高度恢复，BST有序性保持不变。RR·BF=−2DoubleRotation·AVLTree先左后右双旋转与先右后左双旋转双旋转通过两次单旋转的组合处理折线型不平衡：LR型先对左孩子左旋再对根右旋，RL型先对右孩子右旋再对根左旋。第一次旋转将折线转化为直线，第二次旋转完成平衡化修复。先左后右双旋转RotateLR01适用场景：LR型不平衡，新节点在不平衡节点A的左孩子B的右子树上。先对B执行左旋使其转化为LL型，再对A执行右旋完成平衡化。02结构调整：新根节点C（原B的右孩子）上升至根位置。C的左子树交给B，右子树交给A，三节点平衡因子根据C原始BF值更新。03复杂度分析：时间复杂度保持O(1)，仅需常数次指针调整。旋转后子树高度恢复至插入前状态，无需向上回溯更新。先右后左双旋转RotateRL01适用场景：RL型不平衡，新节点在不平衡节点A的右孩子B的左子树上。先对B执行右旋使其转化为RR型，再对A执行左旋完成平衡化。02结构调整：新根节点C（原B的左孩子）上升至根位置。C的右子树交给B，左子树交给A，三节点平衡因子根据C原始BF值更新。03复杂度分析：时间复杂度保持O(1)，仅需常数次指针调整。旋转后子树高度恢复至插入前状态，无需向上回溯更新。Algorithm·DataStructureAVL树插入操作的完整流程AVL树插入操作分为搜索定位、插入新节点、回溯检查平衡因子、执行旋转修复四个阶段。由于旋转后子树高度恢复至插入前的值，回溯过程最多触发一次旋转即可终止，整体时间复杂度仍为O(logn)。01搜索定位按BST规则从根节点出发搜索目标关键码的插入位置，到达空指针处创建新的叶子节点并完成链接Search&Insert02回溯更新从新插入节点沿父指针向上回溯，逐层更新每个祖先节点的高度和平衡因子BF值Backtrack&Update03平衡检查在回溯过程中检查每个节点的BF值，若发现|BF|=2则根据不平衡类型（LL/RR/LR/RL）选择对应的旋转操作Check|BF|=204旋转修复执行旋转操作恢复平衡，旋转后该子树高度恢复至插入前水平，更上层祖先的BF不受影响，回溯终止Rotate&TerminateCLASSDESIGNAVL树的C++类定义AVL树的类设计将公开接口与内部实现分离：公开的Insert/Remove接口调用protected区域的递归版本，递归过程中同步完成节点操作和平衡化旋转，对外呈现简洁的API同时内部维护严格的平衡约束。01公开接口默认构造函数初始化空树，带参构造函数设置哨兵值RefValue；Search/Insert/Remove提供搜索、插入、删除的统一入口，对外隐藏内部实现细节。02递归实现protected区域的Insert(AVLNode*&,E&)在递归插入中逐层检查平衡因子并执行旋转，Remove类似地在删除后修复平衡，确保树高始终保持对数级别。03旋转函数RotateL/RotateR分别实现左单旋和右单旋，RotateLR/RotateRL通过组合两次单旋实现双旋转操作，快速恢复被破坏的平衡结构。04辅助函数Height(ptr)递归计算以ptr为根的子树高度，空时返回0；友元函数重载>>和<<实现树的序列化与反序列化，支持持久化存储。DataStructures·AVLTreeAVL树的删除操作AVL树删除操作在BST删除逻辑基础上增加了平衡修复环节。与插入不同的是，删除后旋转修复可能不会恢复原子树高度，导致不平衡向上传播，最坏情况需O(logn)次旋转才能恢复全局平衡。01BST定位与删除：按BST规则定位目标节点，根据孩子数（0/1/2个）执行对应策略——直接删除、孩子替代或前驱后继替换0/1/2孩子02回溯检查平衡因子：从被删位置的父节点开始向上回溯，逐层更新高度和平衡因子，检查是否有节点的|BF|超过1|BF|>103与插入的关键区别：旋转修复后子树高度可能比删除前更矮，导致上层祖先BF继续变化，需持续回溯直到根节点或高度不再变化高度收缩04最坏情况复杂度：从删除位置到根的路径上每个节点都可能需要旋转修复，总旋转次数O(logn)，整体时间复杂度仍为O(logn)O(logn)DATASTRUCTUREBST与AVL树综合性能对比AVL树通过严格的平衡约束在最坏情况性能上全面优于普通BST，但付出了额外存储平衡因子和旋转操作的代价。BST与AVL树多维性能对比分数越高越优六维雷达图揭示两种树结构在不同场景下的适用性差异。最坏性能全面领先：AVL树在最坏搜索与插入效率上分别达到90和85分，远超普通BST的30分。高度稳定性突出：AVL树以95分保持高度平衡，普通BST仅25分，极端场景下退化为链表。实现与内存代价：普通BST实现简易度85、内存效率90；AVL树分别为40和70，需额外存储平衡因子。平均性能接近：两者平均搜索效率仅差5分（80vs85），随机数据下BST表现已足够优秀。CHAPTER04散列表的构造与冲突处理从散列函数设计到冲突解决策略的系统方法论DATASTRUCTURE散列的基本概念散列通过散列函数将关键码直接映射为存储地址，实现O(1)的理想搜索时间。但关键码空间远大于地址空间必然导致冲突，装填因子α（元素数/表长）是衡量冲突概率和散列性能的核心指标。01O(1)理想搜索散列的核心思想是通过散列函数h(key)将关键码直接映射为存储地址，搜索时仅需计算一次函数值即可定位目标，无需逐元素比较。时间复杂度最优可达常数级02地址空间压缩散列表由有限大小的数组构成，散列函数将大范围关键码空间压缩映射到[0,m−1]的地址空间，m为表长。这种压缩是散列高效存储的基础。关键码空间→有限地址空间03冲突不可避免不同关键码映射到同一地址即为冲突，关键码集合远大于地址空间，冲突只能减少和处理，无法消除。冲突处理策略直接影响散列性能。需设计合理的冲突解决方法04装填因子αα=n/m反映表的拥挤程度，α越大冲突概率越高，一般建议控制在0.6–0.8之间。α是评估散列效率和调整表大小的关键参数。α=0.75为工程常用阈值HASHFUNCTION散列函数的构造方法散列函数的设计目标是使关键码均匀分布在地址空间上以最小化冲突概率。不同方法适用于不同场景：除留余数法最通用，数字分析法适合已知分布的场景，平方取中法适合分布未知的情形。除留余数法h(key)=keymodp，p选不大于表长m的最大素数，可有效避免关键码中规律性分布导致的聚集冲突。modp直接定址法h(key)=a·key+b，适合关键码连续或基本连续的场景，无冲突但地址空间利用率可能较低。a·key+b数字分析法分析关键码各位数字分布频率，选取分布最均匀的若干位组合成地址，适合位数已知且分布可统计的场景。频率分析平方取中法将关键码平方后取中间若干位作为地址，利用平方运算使各位对结果均有影响，适合分布特征未知的情形。key²mid折叠法将关键码分成若干段后叠加求和，适合位数较多的场景，如身份证号分段折叠映射为较小地址值。分段求和HASHCOLLISION开放定址法处理冲突开放定址法在冲突发生时按探测序列寻找下一个空位：线性探测简单但易产生一次聚集，二次探测缓解聚集但探测不完全，双散列效果最优但计算开销略高。三者均在原表内解决冲突，无需额外存储空间。线性探测冲突时依次检查h(key)+1,h(key)+2,…位置直到找到空位，实现简单但连续占用区域会形成"堆积"，加剧后续冲突概率二次探测探测序列为h(key)+1²,h(key)−1²,h(key)+2²,h(key)−2²，跳跃式探测有效缓解一次聚集，但表长须为4k+3形式的素数才能保证探测完全双散列法使用第二个散列函数h₂(key)计算步长，探测序列为h(key)+i·h₂(key)，步长随关键码变化，几乎消除聚集现象，是开放定址法中效果最佳的策略共同缺点删除操作不能简单置空（会截断探测链），需使用"懒删除"标记；且当装填因子接近1时性能急剧下降HASHCOLLISIONRESOLUTION链地址法（拉链法）处理冲突链地址法将映射到同一位置的所有元素组织成链表，从根本上避免了聚集问题和懒删除的复杂性。它在装填因子较大时性能优于开放定址法，是JavaHashMap、Pythondict等主流编程语言哈希表实现的默认冲突处理策略。链表组织结构散列表每个位置维护链表头指针，散列到同一地址的关键码依次插入链表，搜索时先定位链表再在链内查找顺序查找插入与删除操作新元素插入链表头部或尾部，删除时直接摘除节点，无需懒删除标记，操作逻辑清晰直观无需懒删除搜索性能分析成功搜索平均比较次数约1+α/2，失败约α次；当α=1时平均仅需1.5次比较，性能优异α=1局限与混合策略链表指针占用额外存储空间，节点分散导致缓存命中率较低；实践中常与开放定址法混合使用混合使用PERFORMANCEANALYSIS散列表性能分析散列表的搜索效率主要由装填因子α和冲突处理策略决定。α<0.7时各策略均接近O(1)；α增大后线性探测因聚集效应性能急剧恶化，链地址法最为稳定。工程中通常设定α阈值触发自动扩容以维持高效。不同装填因子下搜索失败的平均比较次数高装填因子下线性探测性能急剧恶化，链地址法增长平缓更为稳定装填因子α是衡量散列表拥挤程度的核心指标，直接影响搜索、插入和删除操作的平均时间复杂度。01低装填因子：当α<0.5时，线性探测与链地址法的搜索失败比较次数均极低，两种策略性能差异微乎其微。02高装填因子：α超过0.75后线性探测因主聚集效应性能急剧恶化；α=0.95时平均比较次数达10.5次。03链地址法优势：即使α=0.95，链地址法搜索失败仅需0.95次比较，增长曲线极为平缓，稳定性显著优于线性探测。04工程实践：通常设定α阈值（如0.75）触发自动扩容，通过空间换时间策略维持散列表的高效运行。EngineeringApplications散列表的工程应用散列表是计算机科学中应用最广泛的数据结构之一，从编程语言的字典类型到数据库索引、从编译器符号表到网络路由器转发表，O(1)的搜索性能使其成为高性能系统的基石。编程语言内置实现Pythondict/JavaHashMap—均采用链地址法，表长取2的幂次以便用位运算替代取模运算，装填因子超过0.75时自动扩容并rehash0.75LoadFactorThresholdC++/Go—unordered_map使用链地址法，Go语言map采用桶数组加溢出桶的混合策略，兼顾缓存效率和冲突处理能力混合策略GoBucket+Overflow系统与基础设施数据库与缓存—散列索引用于加速等值查询，Redis使用渐进式rehash避免一次性迁移导致的延迟毛刺Redis渐进式Rehash基础软件—编译器符号表、操作系统页表缓存、网络路由器ARP缓存均依赖散列表实现高效键值查找O(1)LookupComple