毕业设计网站建设体会做付费网站

毕业设计网站建设体会,做付费网站,免费网站app代码,免费招聘人才网前言#xff1a; 在二叉搜索树#xff08;BST#xff09;中#xff0c;若插入顺序有序#xff08;如递增或递减#xff09;#xff0c;树会退化为链表#xff0c;导致增删查效率从O(logN) 骤降至 O(N)。为解决这一问题#xff0c;AVL 树#xff08;自平衡二叉搜索树在二叉搜索树BST中若插入顺序有序如递增或递减树会退化为链表导致增删查效率从O(logN)骤降至O(N)。为解决这一问题AVL 树自平衡二叉搜索树应运而生 —— 它通过控制左右子树的高度差平衡因子确保树始终保持 “高度平衡”从而稳定维持O(logN)的高效操作。本文将从 AVL 树的核心概念切入结合完整代码实现详解插入逻辑、平衡因子更新与四种旋转操作帮你彻底掌握这一经典数据结构。一. AVL 树核心概念什么是 “高度平衡”AVL 树是一种特殊的二叉搜索树满足两个核心条件二叉搜索树特性左子树所有节点值 根节点值 右子树所有节点值高度平衡特性任意节点的左右子树高度差的绝对值 ≤ 1。为了更直观判断平衡状态引入了平衡因子balance factor平衡因子 右子树高度 - 左子树高度AVL 树中任意节点的平衡因子只能是-1、0、1若平衡因子为 2 或 -2说明树已失衡需通过 “旋转” 恢复平衡。思考为什么不要求平衡因子为 0某些场景下如 2 个节点、4 个节点树无法做到左右子树高度完全相等如根节点左子树高 1右子树高 0此时平衡因子为 1仍满足 “高度差≤1” 的平衡要求。二. AVL 树结构设计节点与类定义AVL 树的节点需存储键值对、左右孩子指针、父指针用于更新平衡因子和平衡因子。类定义如下#pragma once #includeiostream #includeassert.h using namespace std; // AVL树节点的结构 templateclass K, class V struct AVLTreeNode { pairK, V _kv; // 存储键值对Key-Value AVLTreeNodeK, V* _parent; // 父节点指针后续更新平衡因子要用到 AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; int _bf; // 平衡因子右子树高度 - 左子树高度 AVLTreeNode(const pairK, V kv) : _kv(kv) , _parent(nullptr) , _left(nullptr) , _right(nullptr) , _bf(0) {} }; // AVL树类 templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: // 插入、旋转等核心接口下文会详细解析 bool Insert(const pairK, V kv); void RotateR(Node* parent); // 右单旋 void RotateL(Node* parent); // 左单旋 void RotateLR(Node* parent); // 左右双旋 void RotateRL(Node* parent); // 右左双旋 Node* Find(const K key); // 查找(和二叉搜索树一样) private: Node* _root nullptr; };三. AVL 树插入从 BST 插入到平衡维护AVL树的插入流程分为两步按 BST 规则插入节点→回溯更新平衡因子失衡则旋转恢复。这是 AVL 树维持平衡的核心环节需重点理解平衡因子的更新逻辑与停止条件。3.1 插入完整代码带详细注释public: bool Insert(const pairK,V kv) { // 情况1树为空直接创建根节点 if (_root nullptr) { _root new Node(kv); return true; } // 情况2树非空遍历找插入位置 Node* parent nullptr;// 记录cur的父节点用于后续链接新节点 Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_right; // 比当前节点大向右走 } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left;// 比当前节点小向左走 } else return false;// 值已存在不支持插入返回false } // 创建新节点并链接到parent的左/右孩子 cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur;// 插入值比parent大作为右孩子 } else { parent-_left cur; // 插入值比parent小作为左孩子 } cur-_parent parent; // 更新平衡因子从新节点的父节点开始向上 while (parent) { // 更新当前父节点的平衡因子 if (cur parent-_left) { // 新节点在父节点的左子树 → 左子树高度1 → 平衡因子-1 parent-_bf--; } else { // 新节点在父节点的右子树 → 右子树高度1 → 平衡因子1 parent-_bf; } // 根据平衡因子判断是否继续更新或旋转 if (parent-_bf 0) { // parent所在的子树高度不变不会再影响上一层更新结束 // 平衡因子变为0 → 父节点子树高度不变插入前左 / 右高1插入后平衡 break; } else if (parent-_bf 1 || parent-_bf -1) { // parent 所在的子树高度变了会再影响上一层继续往上面更新 // 平衡因子变为1 / -1 → 父节点子树高度 1插入前平衡插入后单侧高1 cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { // parent 所在的子树已经不平衡了需要旋转处理 // 平衡因子变为2 / -1 → 父节点子树失衡需旋转恢复平衡 if (parent-_bf -2 cur-_bf -1) { // 父节点BF-2左子树高当前节点BF-1左子树高→ 右单旋 RotateR(parent); } else if (parent-_bf 2 cur-_bf 1) { // 父节点BF2右子树高当前节点BF1右子树高→ 左单旋 RotateL(parent); } else if (parent-_bf -2 cur-_bf 1) { // 父节点BF-2左子树高当前节点BF1右子树高→ 左右双旋 RotateLR(parent); } else { // 父节点BF2右子树高当前节点BF-1左子树高→ 右左双旋 RotateRL(parent); } // 旋转后失衡子树高度恢复到插入前不会影响上层更新结束 break; } else { // 异常情况平衡因子为其他值如3、-3) assert(false); } } return true; }3.2 平衡因子更新关键逻辑更新平衡因子时核心是判断“当前子树高度是否变化”进而决定是否继续向上更新BF0插入前父节点子树 “有一侧高 1”如 BF1 或 - 1插入后两侧平衡高度不变 → 停止更新BF1/-1插入前父节点子树 “平衡”BF0插入后 “有一侧高 1”高度 1 → 继续更新BF2/-2插入前父节点子树 “有一侧高 1”插入后 “有一侧高 2”失衡 → 旋转后停止更新。更新到根根的平衡因子是1或-1也停止。我们来看看下面几个情况图示更新到 10 结点平衡因子为210所在的子树已经不平衡需要旋转处理更新到中间结点3为根的子树高度不变不会影响上一层更新结束。最坏情况更新到根为止四. AVL 树旋转失衡恢复的四种方式当节点平衡因子为2或- 2时需通过 “旋转” 恢复平衡。旋转的核心目标有两个维持二叉搜索树特性 降低失衡子树高度。根据失衡形态分为四种旋转方式4.1 右单旋RotateR左子树过高父 BF-2子 BF-1下图中展现的是10为根的树有a/b/c抽象为三颗高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整颗树的根。这里a/b/c是高度为h的子树是一种概括抽象的表示他代表了所有右单旋的场景但实际右单旋的场景很多大家可以看看后面的实际场景图。在 a 子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树的左边太高了需要往右边旋转控制两颗树的平衡。旋转核心步骤记录父节点parent的左子树subL和 subL 的右子树subLR将 subLR 作为 parent 的左子树若 subLR 非空更新其 parent 指针将 parent 作为 subL 的右子树更新 parent 的 parent 指针(提前存一下祖父结点再更新)链接 subL 与祖父节点若 parent 是根节点更新_root重置 parent 和 subL 的平衡因子为 0。实际场景图代码实现注意看注释public: void RotateR(Node* parent) { Node* subL parent-_left; // parent的左子树即将成为新根 Node* subLR subL-_right; // subL的右子树需转移给parent // 步骤1将subLR作为parent的左子树 parent-_left subLR; if (subLR) subLR-_parent parent; Node* grandparent parent-_parent; // parent的父节点祖父节点 // 步骤2将parent作为subL的右子树 subL-_right parent; parent-_parent subL; // 步骤3链接subL与祖父节点或更新根节点 if (parent _root) { // parent是根节点则subL成为新根 _root subL; subL-_parent nullptr; } else { // parent是祖父节点的左/右孩子对应链接subL if (grandparent-_left parent) grandparent-_left subL; else grandparent-_right subL; subL-_parent grandparent; } // 步骤4重置平衡因子旋转后子树平衡BF均为0 parent-_bf subL-_bf 0; }4.2 左单旋RotateL右子树过高父 BF2子 BF1下图中展示的是10为根的树有a/b/c抽象为三颗高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整颗树的根也可能是一整颗树中局部的子树的根。这里a/b/c是高度为h的子树是一种概括抽象表示他代表所有左单旋的场景实际左单旋场景有很多具体跟上面的右旋类似。在a子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从1变成210为根的树左右高度差超过1违反平衡规则。10为根的树右边太高了。需要往左边旋转控制两颗树的平衡。旋转核心步骤记录父节点parent的右子树subR和 subR 的左子树subRL将 subRL 作为 parent 的右子树若 subRL 非空更新其 parent 指针将 parent 作为 subR 的左子树更新 parent 的 parent 指针(提前存一下祖父结点再更新)链接 subR 与祖父节点或更新_root重置 parent 和 subR 的平衡因子为 0。代码实现注意看注释public: void RotateL(Node* parent) { Node* subR parent-_right; // parent的右子树即将成为新根 Node* subRL subR-_left; // subR的左子树需转移给parent // 步骤1将subRL作为parent的右子树 parent-_right subRL; if (subRL) subRL-_parent parent; Node* grandparent parent-_parent; // parent的父节点 // 步骤2将parent作为subR的左子树 subR-_left parent; parent-_parent subR; // 步骤3链接subR与祖父节点或更新根节点 if (parent _root) { _root subR; subR-_parent nullptr; } else { if (grandparent-_left parent) grandparent-_left subR; else grandparent-_right subR; subR-_parent grandparent; } // 步骤4重置平衡因子 parent-_bf subR-_bf 0; }4.3 左右双旋RotateLR左子树的右子树过高父 BF-2子 BF1我们通过下面这两种场景图可以看出左边高时如果插入位置不是在a子树而是插入到b子树b子树高度从h变成h1,引发了旋转右单旋无法解决问题右单旋过后我们的树依旧不平衡。右单旋解决的纯粹的左边高但是插入到b子树中10为根的子树不再是单纯的左边高对于10是左边高但是对于5是右边高需要用两次旋转才能解决以5为旋转点进行一个左单旋以10为旋转点进行一个右单旋这颗树就平衡了。上面两个图片分别为左右双旋中 h0 和 h1的具体场景分析下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论。旋转核心步骤对父节点的左子树subL执行左单旋将 subL 的右子树 subLR 提升为 subL 的父节点对父节点parent执行右单旋将修正后的 subL 提升为 parent 的父节点根据 subLR 的原始平衡因子重置三个节点parent、subL、subLR的平衡因子三种场景。场景1h1时新增结点插入在e子树e子树高度从h-1变为h并不断更新subLR-subL-parent平衡因子引发旋转其中subLR的平衡因子为 -1旋转后subLR和subL平衡因子为0parent的平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新subLR-subL-parent平衡因子引发旋转其中subLR的平衡因子为1旋转后subLR和parent的平衡因子为0subL的平衡因子为-1。场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新subL-parent平衡因子引发旋转其中subLR的平衡因子为0旋转后subLR,subL和parent的平衡因子都为0。代码实现注意看注释void RotateLR(Node* parent) { Node* subL parent-_left; // parent的左子树 Node* subLR subL-_right; // subL的右子树关键节点决定平衡因子重置 int bf subLR-_bf; // 记录subLR的原始BF用于后续重置 // 步骤1先对subL执行左单旋修正左子树的失衡 RotateL(parent-_left); // 步骤2再对parent执行右单旋修正父节点的失衡 RotateR(parent); // 步骤3根据subLR的原始BF重置三个节点的平衡因子 if (bf 0) { // 场景3subLR是新插入节点BF0→ 旋转后三者BF均为0 parent-_bf 0; subL-_bf 0; subLR-_bf 0; } else if (bf 1) { // 场景2subLR的右子树高BF1→ parent的左子树高subL的右子树高 parent-_bf 0; subL-_bf -1; subLR-_bf 0; } else if(bf-1) { // 场景1subLR的左子树高BF-1→ parent的右子树高subL的左子树高 parent-_bf 1; subL-_bf 0; subLR-_bf 0; } else { assert(false); } }4.4 右左双旋RotateRL右子树的左子树过高父 BF2子 BF-1跟左右双旋类似下面我们将a/b/c子树抽象为高度h的AVL子树进行分析另外我们需要把b子树的细节进一步展开为12和左子树高度为h-1的e和f子树因为我们要对b的父亲15为旋转点进行右单旋右单旋需要动b树中的右子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察12的平衡因子不同不同这里我们要分三个场景讨论。旋转核心步骤对父节点的右子树subR执行右单旋对父节点parent执行左单旋根据 subRL 的原始平衡因子重置三个节点的平衡因子。场景1h1时新增结点插入在e子树e子树高度从h-1变为h并不断更新subRL-subR-parent平衡因子引发旋转其中subRL的平衡因子为-1旋转后parent和subRL平衡因子为0subR平衡因子为1。场景2h1时新增结点插入在f子树f子树高度从h-1变为h并不断更新subRL-subR-parent平衡因子,引发旋转其中subRL的平衡因子为1旋转后subR和subRL的平衡因子为0parent的平衡因子为-1。场景3h0时a/b/c都是空树b自己就是一个新增结点不断更新**subR-parent** 平衡因子引发旋转其中subRL的平衡因子为0旋转后三者的平衡因子都是0。代码实现注意看注释void RotateRL(Node* parent) { Node* subR parent-_right; // parent的右子树 Node* subRL subR-_left; // subR的左子树关键节点 int bf subRL-_bf; // 记录subRL的原始BF // 步骤1先对subR执行右单旋修正右子树的失衡 RotateR(parent-_right); // 步骤2再对parent执行左单旋修正父节点的失衡 RotateL(parent); // 步骤3根据subRL的原始BF重置三个节点的平衡因子 if (bf 0) { // 场景3subRL是新插入节点 → 三者BF均为0 subR-_bf 0; subRL-_bf 0; parent-_bf 0; } else if (bf 1) { // 场景2subRL的右子树高BF1→ parent的左子树高subR的左子树高 subR-_bf 0; subRL-_bf 0; parent-_bf -1; } else if (bf -1) { // 场景1subRL的左子树高BF-1→ parent的右子树高subR的右子树高 subR-_bf 1; subRL-_bf 0; parent-_bf 0; } else { // 异常情况 assert(false); } }五. AVL树的查找和平衡检查验证树的正确性5.1 AVL树的查找(与二叉搜索树一致,O(logN))Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; } } return nullptr; }5.2 AVL 树验证如何判断实现正确为确保 AVL 树实现无误需验证两个核心条件二叉搜索树特性 高度平衡特性。可添加以下辅助接口类内补充public: // 对外接口验证AVL树 bool IsBalanceTree() { return _IsBalance(_root); } // 对外接口中序遍历验证二叉搜索树特性中序递增 void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); }测试代码示例#define _CRT_SECURE_NO_WARNINGS 1 #includeAVLTree.h // 测试AVL树插入与平衡性 void TestAVL() { // 测试用例1包含双旋场景如4,2,6,1,3,5,15,7,16,14 int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTreeint, int t; for (auto e : a) { t.Insert({ e, e }); } // 验证1中序遍历应递增 cout 中序遍历结果; t.InOrder(); // 输出1 2 3 4 5 6 7 14 15 16 // 验证2平衡性应返回true if (t.IsBalanceTree()) { cout AVL树平衡验证通过 endl; } else { cout AVL树平衡验证失败 endl; } } int main() { TestAVL(); return 0; }