2025 高中信息技术数据结构的 AVL 树课件

一、引言：从二叉搜索树的局限到AVL树的诞生演讲人目录引言：从二叉搜索树的局限到AVL树的诞生01AVL树的删除操作：比插入更复杂的平衡维护04AVL树的插入操作：从失衡到平衡的调整艺术03总结与展望06AVL树的定义与基本性质02AVL树的应用与意义052025高中信息技术数据结构的AVL树课件01引言：从二叉搜索树的局限到AVL树的诞生引言：从二叉搜索树的局限到AVL树的诞生同学们，上节课我们系统学习了二叉搜索树（BinarySearchTree,BST）的结构与操作。大家是否还记得BST的核心规则？——左子树所有节点值小于根节点，右子树所有节点值大于根节点。这种规则让BST在理想情况下（如数据随机分布）能以O(logn)的时间复杂度完成查找、插入和删除操作，效率远高于线性表。但不知道大家是否观察过极端情况：如果我们按升序依次插入1、2、3、4、5……这时候BST会变成什么样？（展示动画：插入1为根，插入2成为右子节点，插入3成为2的右子节点……最终形成一条“右链”）没错，此时BST退化为单链表，时间复杂度退化为O(n)，查找效率与顺序表无异。这就像图书馆的书架，如果所有书都按顺序摆成一列，找书时只能从头翻到尾，效率低下。如何解决这个问题？引言：从二叉搜索树的局限到AVL树的诞生这正是AVL树诞生的背景。1962年，苏联数学家Adelson-Velsky和Landis提出了一种“自平衡二叉搜索树”，通过严格控制树的平衡状态，确保无论数据如何插入或删除，树的高度始终保持在O(logn)级别。这种树以两位发明者的姓氏首字母命名为“AVL树”，它是数据结构中“平衡”思想的经典实现，也是后续红黑树、B树等更复杂结构的基础。02AVL树的定义与基本性质1平衡因子：衡量平衡的核心指标要理解AVL树的“自平衡”特性，首先需要掌握“平衡因子”（BalanceFactor,BF）的概念。对于任意节点，其平衡因子定义为左子树的高度减去右子树的高度（注意：是左减右，而非右减左）。数学表达式为：[BF(node)=height(left_child)-height(right_child)]这里的“高度”指从该节点到其所在子树中最远叶子节点的边数（部分教材定义为节点数，需注意区分，但本质逻辑一致）。例如，叶子节点的左右子树高度均为0，因此BF=0；若一个节点的左子树高度为3，右子树高度为2，则BF=1。2AVL树的严格平衡条件AVL树的核心规则是：所有节点的平衡因子绝对值不超过1（即BF∈{-1,0,1}）。这意味着，AVL树中任意节点的左右子树高度差最多为1，从而避免了BST的“链化”问题。（展示对比图：左图为失衡的BST，根节点BF=3；右图为对应的AVL树，所有节点BF绝对值≤1）需要强调的是，AVL树的“平衡”是一种局部平衡，通过每个节点的平衡因子约束实现全局的高度控制。这种严格性使得AVL树的查找效率非常稳定，但也带来了插入/删除时可能需要多次调整的代价——这是“平衡”与“效率”的经典权衡。3AVL树与普通BST的关系STEP3STEP2STEP1AVL树是BST的“增强版”，它继承了BST的有序性（左小右大），同时增加了平衡约束。可以说：[AVL树=BST+平衡因子约束]这一关系决定了AVL树的操作逻辑：首先按BST规则插入/删除节点，然后检查平衡因子是否破坏，若破坏则通过旋转操作恢复平衡。03AVL树的插入操作：从失衡到平衡的调整艺术AVL树的插入操作：从失衡到平衡的调整艺术插入是AVL树最核心的操作之一，也是理解其平衡机制的关键。我们分三步解析：1插入的基本流程STEP1STEP2STEP3STEP4AVL树的插入操作遵循“先插入，后调整”的原则，具体步骤如下：按BST规则插入新节点：从根节点开始，比较新节点值与当前节点值，选择左或右子树递归插入，直到找到合适的叶子位置。更新路径上节点的高度：插入新节点后，需要从新节点向上回溯，逐层更新父节点的高度（高度=max(左子树高度,右子树高度)+1）。检查并调整失衡节点：在回溯过程中，检查每个节点的平衡因子。若某个节点的BF绝对值超过1（即失衡），则根据失衡类型选择相应的旋转操作。2失衡的四种类型与旋转调整插入操作可能导致四种类型的失衡，对应四种调整方式：LL型、RR型、LR型、RL型（L表示左子树，R表示右子树）。2失衡的四种类型与旋转调整2.1LL型失衡与右旋（RightRotation）1失衡条件：新节点插入在失衡节点（设为A）的左子树的左子树中（即A的左子节点B的左子树中），导致A的BF=2。2调整方法：以A为根进行右旋，将B提升为新根，A成为B的右子节点，B原来的右子树（设为T2）成为A的左子树。3（展示动画：原树结构A->B->C，插入C的左子节点后，A的BF=2；右旋后B为根，A为B的右子，T2挂到A的左）4数学验证：调整后，B的左右子树高度差为原A的左子树高度-原B的右子树高度，而A的左右子树高度差为原B的右子树高度-原A的右子树高度，最终所有节点BF绝对值≤1。2失衡的四种类型与旋转调整2.2RR型失衡与左旋（LeftRotation）失衡条件：新节点插入在失衡节点A的右子树的右子树中（即A的右子节点B的右子树中），导致A的BF=-2。调整方法：以A为根进行左旋，将B提升为新根，A成为B的左子节点，B原来的左子树（设为T2）成为A的右子树。（对比LL型，强调左右对称的逻辑）3.2.3LR型失衡与左右旋（Left-RightRotation）失衡条件：新节点插入在失衡节点A的左子树的右子树中（即A的左子节点B的右子树中），导致A的BF=2。调整方法：分两步进行：对B进行左旋，使其右子节点C提升为B的父节点（此时C成为A的左子节点）；2失衡的四种类型与旋转调整2.2RR型失衡与左旋（LeftRotation）对A进行右旋，将C提升为新根。（展示具体案例：A的左子B的右子C插入新节点后，A的BF=2。先左旋B得到A->C->B，再右旋A得到C为根，A为右子，B为左子）关键理解：LR型失衡的本质是左子树的右分支过长，单纯右旋无法平衡，需先“掰正”左子树的右分支，再整体右旋。3.2.4RL型失衡与右左旋（Right-LeftRotation）失衡条件：新节点插入在失衡节点A的右子树的左子树中（即A的右子节点B的左子树中），导致A的BF=-2。调整方法：分两步进行：对B进行右旋，使其左子节点C提升为B的父节点（此时C成为A的右子节点）；2失衡的四种类型与旋转调整2.2RR型失衡与左旋（LeftRotation）对A进行左旋，将C提升为新根。（强调与LR型的对称性，帮助学生通过“左右”“右左”的命名规律记忆调整顺序）3插入操作的完整示例为加深理解，我们以具体数值演示插入过程：案例：依次插入30、20、10、40、50、25插入30（根节点，高度1，BF=0）插入20（30的左子，高度2，根BF=1）插入10（20的左子，此时根节点30的BF=2（左子高度2，右子高度0），触发LL型失衡，右旋后根变为20，30成为20的右子，高度调整为2，所有节点BF=0）插入40（30的右子，根20的BF=0（左子高度2，右子高度2））插入50（40的右子，根20的BF=-1（左子高度2，右子高度3），40的BF=-1（右子高度2，左子高度0），未失衡）3插入操作的完整示例插入25（20的右子30的左子，此时检查路径：25→30→20。30的BF=1（左子高度1，右子高度0），20的BF=0（左子高度2，右子高度2），未失衡。但继续向上检查根节点，发现无失衡，插入完成。（展示每一步的树结构变化图，标注各节点的高度和BF值）04AVL树的删除操作：比插入更复杂的平衡维护AVL树的删除操作：比插入更复杂的平衡维护删除操作的逻辑与插入类似，但需要处理更多边界情况，因为删除可能导致多个祖先节点失衡（插入通常仅导致一个节点失衡）。1删除的基本流程21按BST规则删除节点：若为叶子节点直接删除；若只有一个子节点，用子节点替换；若有两个子节点，找到左子树最大值或右子树最小值替换，再删除该替换节点。检查并调整失衡节点：与插入不同，删除可能导致从被删除节点到根路径上的多个节点失衡，需逐个调整。更新路径上节点的高度：从被删除节点的父节点开始向上回溯，更新各节点的高度。32删除后的失衡调整删除操作导致的失衡类型同样是LL、RR、LR、RL型，但调整逻辑更复杂。例如，删除右子树的节点可能导致左子树过高（BF=2），此时需要判断左子树的平衡因子：若左子树的左子树更高（BF=1），执行右旋（LL型）；若左子树的右子树更高（BF=-1），执行左右旋（LR型）；若左子树的BF=0（左右子树等高），右旋后原根节点的BF变为-1，但树仍保持平衡。（通过具体案例演示：删除50后，40的BF=1，30的BF=2，触发LL型失衡，右旋调整）3高中阶段的教学建议考虑到删除操作的复杂性，高中阶段可重点掌握插入操作的调整逻辑，删除操作可作为拓展内容，通过动画演示或简化案例辅助理解，避免过度增加学习负担。05AVL树的应用与意义1实际场景中的应用AVL树的严格平衡特性使其在需要稳定查找效率的场景中表现优异，例如：01数据库索引：MySQL的InnoDB引擎虽主要使用B+树，但部分内存索引会采用AVL树，确保查询时间稳定；02文件系统：部分操作系统的文件目录管理使用AVL树，快速定位文件路径；03游戏开发：场景对象的空间索引（如按坐标排序），需频繁插入/删除并快速查询。04（举例：游戏中需要快速查找距离玩家最近的5个NPC，AVL树可按坐标排序，确保每次查询时间为O(logn)）052算法思想的传承与发展AVL树是“自平衡”思想的鼻祖，后续的红黑树（平衡条件更宽松，插入/删除调整更少）、Treap（结合堆与BST）、Splay树（基于访问频率调整）等结构均受其启发。理解AVL树的平衡机制，能为学习这些更复杂的数据结构奠定基础。3对计算思维的培养价值学习AVL树不仅是掌握一种数据结构，更是理解“约束与优化”的辩证关系：通过引入平衡因子的约束（牺牲部分插入/删除效率），换取查找效率的稳定性（保证O(logn)时间复杂度）。这种“权衡思维”是算法设计的核心思想之一。06总结与展望总结与展望同学们，今天我们从BST的局限性出发，逐步揭开了AVL树的神秘面纱：它通过平衡因子约束实现严格平衡，通过旋转操作在插入/删除后恢复平衡，最终保证了高效稳定的查找效率。回顾重点：AVL树是自平衡的BST，所有节点BF绝对值≤1；插入操作需经过“插入→更新高度→调整失衡”三步，调整方式包括LL/RR/LR/RL四种旋转；删除操作逻辑类似但更复杂，需处理多节点失衡；AVL树在需要稳定效率的场景中广泛应用，是后续高级数据结构的基础。总结与展望希望大家课后能动手绘