网站上传的流程图理财网站建设

当前位置： 首页 > news >正文

网站上传的流程图,理财网站建设,网站的关键词在哪设置,设计师网站十大网站摘要 本文深入探讨了 AVL 树#xff08;自平衡二叉搜索树#xff09;的概念、特点以及实现细节。我们首先介绍了 AVL 树的基本原理#xff0c;并详细分析了其四种旋转操作#xff0c;包括左旋、右旋、左右双旋和右左双旋#xff0c;阐述了它们在保持树平衡中的重要作用。…摘要 本文深入探讨了 AVL 树自平衡二叉搜索树的概念、特点以及实现细节。我们首先介绍了 AVL 树的基本原理并详细分析了其四种旋转操作包括左旋、右旋、左右双旋和右左双旋阐述了它们在保持树平衡中的重要作用。接着本文从头到尾详细描述了 AVL 树的插入、删除和查找操作配合完整的代码实现和详尽的注释使读者能够全面理解这些操作的执行过程。 此外我们还提供了 AVL 树的遍历方法包括中序、前序和后序遍历帮助读者更好地掌握 AVL 树的结构和节点间关系。通过对 AVL 树的优缺点进行分析本文揭示了其在不同应用场景中的适用性为读者选择合适的数据结构提供了参考。通过对 AVL 树的全面解析本文旨在为读者提供一个完整的学习路径帮助他们掌握这一强大的数据结构。 1、引言 在计算机科学中数据结构是程序设计的基石而二叉搜索树 (BST) 则是最基本的树形数据结构之一。二叉搜索树提供了高效的查找、插入和删除操作但在最坏情况下这些操作的时间复杂度可能退化为线性。这种退化主要发生在 BST 呈现为链状结构时例如在顺序插入数据时。因此为了保证二叉搜索树的性能出现了多种自平衡树如红黑树、AVL树、B树等。 关于二叉搜索树的更多细节请见我的这篇博客《 C 修炼全景指南九 》打破编程瓶颈掌握二叉搜索树的高效实现与技巧 关于红黑树的更多细节请见我的这篇博客《 C 修炼全景指南十一 》穿越数据的红与黑掌握数据平衡的极致艺术 在这些自平衡树中AVL 树是最早被发明的一种。它由 Adelson-Velsky 和 Landis 于 1962 年提出因其发明者名字的首字母缩写而得名。AVL 树在插入和删除节点后通过旋转操作保持树的平衡从而确保所有操作的时间复杂度始终维持在 O(log⁡n) 。这一特性使得 AVL 树成为实现高效动态集合的一种重要选择。本文将深入探讨AVL树的结构、插入和删除操作的实现以及其在实际应用中的优缺点。 本篇博客所涉及的所有代码均可从我的代码仓库获得https://git.lenyiin.com/Lenyiin/AVLTree 2、AVL树概述 AVL 树是一种自平衡二叉搜索树每个节点都存储一个平衡因子Balance Factor简称 BF用于表示该节点的左子树和右子树的高度差。AVL 树的基本特性是对于每个节点要求其左子树和右子树的高度差至多为 1。因此AVL 树的高度始终保持在 O(log⁡n) 从而保证查找、插入和删除操作的时间复杂度为 O(log⁡n) 。 2.1、平衡因子 AVL 树中每个节点的平衡因子是该节点右子树的高度减去左子树的高度即 ​ B F ( n o d e ) h e i g h t ( r i g h t s u b t r e e ) − h e i g h t ( l e f t s u b t r e e ) BF(node)height(right subtree)−height(left subtree) BF(node)height(rightsubtree)−height(leftsubtree) 当平衡因子为 0 时表示左子树和右子树高度相等。当平衡因子为正数时表示右子树比左子树高。当平衡因子为负数时表示左子树比右子树高。 AVL树通过限制每个节点的平衡因子在-1、0、1之间确保树始终保持平衡状态。 2.2、旋转操作 为了保持AVL树的平衡在插入或删除节点后如果某个节点的平衡因子超出范围即绝对值大于1则需要进行旋转操作来恢复平衡。AVL树主要有四种旋转操作 单右旋LL型用于修复左子树的左子节点插入导致的不平衡。单左旋RR型用于修复右子树的右子节点插入导致的不平衡。先左旋后右旋LR型用于修复左子树的右子节点插入导致的不平衡。先右旋后左旋RL型用于修复右子树的左子节点插入导致的不平衡。 通过这些旋转操作AVL树能够在插入和删除节点后迅速恢复平衡从而保持其高效的操作性能。 2.3、AVL树的应用场景 AVL 树适用于需要频繁查找和插入操作的数据场景并且对查询操作的效率要求较高。例如数据库索引、内存中的有序集合、符号表等。虽然 AVL 树在插入和删除操作中需要更多的旋转操作来保持平衡因此可能不如红黑树等自平衡树高效但在需要严格平衡以保证查询效率的场景下AVL 树仍然是一种理想的选择。 2.4、本文的结构 接下来本文将详细阐述 AVL 树的节点结构、插入与删除操作的具体实现以及旋转操作的原理。随后我们将对 AVL 树的优缺点进行分析并探讨其在实际应用中的表现。通过对 AVL 树的全面分析读者将能够深入理解这一数据结构并在实际开发中灵活运用。 3、AVL 树的实现 3.1、AVL树节点结构 首先我们需要定义一个基本的AVL树节点结构。该结构体将包含节点的键值对、左右子节点、父节点以及用于维护树平衡的平衡因子。平衡因子表示节点右子树高度与左子树高度的差值。 template class K, class V struct AVLTreeNode {AVLTreeNodeK, V* _left; // 左子节点AVLTreeNodeK, V* _right; // 右子节点AVLTreeNodeK, V* _parent; // 父节点int _bf; // 平衡因子 balance factorstd::pairK, V _kv; // 键值对// 构造函数AVLTreeNode(const std::pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {} };详细解释 _left指向左子节点的指针。_right指向右子节点的指针。_parent指向父节点的指针用于在平衡调整时便于向上回溯。_bf平衡因子用于判断树是否需要旋转。平衡因子为右子树高度减去左子树高度。_kv存储节点的键值对。 接下来我们将基于这个节点结构体开始AVL树的实现。我们将逐步构建各个功能模块包括插入、删除、平衡操作等。 3.2、插入操作 插入节点时首先遵循二叉搜索树的规则进行节点的插入然后通过调整平衡因子和旋转来维护树的平衡。 bool Insert(const std::pairK, V kv) {// 1. 先按搜索树的规则进行插入if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false; // 如果相等, 表示已经有了, 不需要插入}}// 找到位置cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}// 2. 更新平衡因子while (parent){if (cur parent-_right){parent-_bf; // 插在右边, 平衡因子}else{parent-_bf–; // 插在左边, 平衡因子–}if (parent-_bf 0){// 说明 parent 所在的子树高度不变, 更新结束break;}else if (parent-_bf 1 || parent-_bf -1){// 说明 parent 所在子树的高度变了, 继续往上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){// parent 所在的子树出现问题了, 需要旋转处理一下// 1. 旋转前提是保持它依旧是搜索二叉树// 2. 旋转成平衡树if (parent-_bf 2){if (cur-_bf 1){// 左旋RotateL(parent);}else if (cur-_bf -1){// 右左双旋RotateRL(parent);}}else if (parent-_bf -2){if (cur-_bf -1){// 右旋RotateR(parent);}else if (cur-_bf 1){// 左右双旋RotateLR(parent);}}// 旋转完成后, parent 所在的树的高度恢复到了插入节点前的高度// 如果是子树, 对上一层没有影响, 更新结束break;}}return true; }详细解释 Insert插入节点的函数。它根据键值对的大小关系选择插入到左子树还是右子树。 _bf 的调整如果插入在左子树平衡因子减 1如果插入在右子树平衡因子加 1。 插入节点后我们需要检查树是否仍然平衡。如果树失去平衡平衡因子的绝对值大于1就需要执行旋转操作来恢复平衡。 RotateL右子树的右子节点插入左单旋RotateR左子树的左子节点插入右单旋RotateRL右子树的左子节点插入右左双旋。RotateLR左子树的右子节点插入先左旋后右旋。 3.3、旋转操作 在 AVL 树中保持树的平衡性是至关重要的这主要通过四种旋转操作来实现左旋、右旋、左-右双旋和右-左双旋。这些旋转操作用于修复因插入或删除节点导致的树不平衡确保 AVL 树的高度维持在 O(log⁡n) 。下面我们详细描述这四种旋转方式。 3.3.1、左单旋 场景当新节点插入到某个节点的右子树的右子节点时可能导致该节点失衡。此时需要进行单左旋操作来恢复平衡。 旋转过程 假设不平衡节点为 A其右子节点为 B。B 的左子树 BL 将成为 A 的右子树。B 成为新的子树根节点而 A 成为 B 的左子节点。 示例图 插入导致的结构 A\B\C单左旋后的结构 B/ \A C代码实现 // 左单旋 void RotateL(Node* parent) {Node* ppNode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;// 1. 原来 parent 是这棵树的根, 现在 subR 是根if (parent _root){_root subR;subR-_parent nullptr;}// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}parent-_bf subR-_bf 0; }解释 subR 指向 A 的右子节点 B。B 的左子树 subRL 被挂接到 A 的右子树。B 成为新的根节点A 成为 B 的左子节点。 3.3.2、右单旋 场景当新节点插入到某个节点的左子树的左子节点时可能导致该节点失衡。此时需要进行右单旋操作来恢复平衡。 旋转过程 假设不平衡节点为 A其左子节点为 B。B 的右子树 BR 将成为 A 的左子树。B 成为新的子树根节点而 A 成为 B 的右子节点。 示例图 插入导致的结构 A/ B / C 单右旋后的结构 B/ \C A代码实现 // 右单旋 void RotateR(Node* parent) {Node* ppNode parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}parent-_bf subL-_bf 0; }详细解释 parent 是节点 AsubL 指向 A 的左子节点 B。B 的右子树 subLR 被挂接到 A 的左子树。B 成为新的根节点A 成为 B 的右子节点。 3.3.3、左右双旋 场景当新节点插入到某个节点的左子树的右子节点时可能导致该节点失衡。此时需要先对其左子树进行左旋再对整个子树进行右旋来恢复平衡。 旋转过程 左旋对左子节点 B 进行单左旋使得 B 的右子节点 C 成为新的根节点。右旋对不平衡节点 A 进行单右旋使得 C 成为新的根节点。 示例图 插入导致的结构 A/B\C左旋后的中间结构 A/C/ B右旋后的最终结构 C/ \B A代码实现 // 左右双旋 void RotateLR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;} }解释 首先对 A 的左子节点 B 进行单左旋使得 C 成为新的子树根节点。然后对不平衡节点 A 进行单右旋使得 C 成为新的根节点。 3.3.4、右左双旋 场景当新节点插入到某个节点的右子树的左子节点时可能导致该节点失衡。此时需要先对其右子树进行右旋再对整个子树进行左旋来恢复平衡。 旋转过程 右旋对右子节点 B 进行单右旋使得 B 的左子节点 C 成为新的根节点。左旋对不平衡节点 A 进行单左旋使得 C 成为新的根节点。 示例图 插入导致的结构 A\B/C右旋后的中间结构 A\C\B左旋后的最终结构 C/ \A B代码实现 // 右左双旋 void RotateRL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;} }解释 首先对 A 的右子节点 B 进行单右旋使得 C 成为新的子树根节点。然后对不平衡节点 A 进行单左旋使得 C 成为新的根节点。 3.3.5、旋转操作总结 通过这四种旋转操作AVL 树能够在插入或删除节点后迅速恢复平衡。无论是单旋转还是双旋转这些操作的时间复杂度都为 O(1) 因为它们只涉及常数级别的节点重新链接。这使得 AVL 树在保持自平衡状态的同时能够保证所有基本操作的时间复杂度为 O(log⁡n) 。 3.4、删除操作 在 AVL 树中节点的删除操作相对复杂因为删除节点后不仅要移除目标节点还需要重新平衡树以保持 AVL 树的平衡性质。AVL 树的删除操作可以分为以下几个步骤 找到并删除节点和普通的二叉搜索树BST删除操作类似。调整平衡因子从删除的节点开始沿着路径向上调整每个节点的平衡因子。执行旋转操作在调整平衡因子的过程中如果发现某个节点失衡平衡因子的绝对值大于1需要进行相应的旋转操作来恢复平衡。 我们将按照这三个步骤详细解释AVL树中节点的删除操作。 3.4.1、找到并删除节点 首先我们需要在AVL树中找到要删除的节点并按照 BST 的删除规则将其删除。BST中的删除操作有以下几种情况 节点是叶子节点直接删除该节点即可。节点有一个子节点用其唯一的子节点替换它。节点有两个子节点找到该节点的中序后继节点用后继节点的值替换该节点的值然后删除后继节点。 3.4.2、调整平衡因子 在删除节点后需要调整其祖先节点的平衡因子。沿着从删除节点到根节点的路径进行调整规则如下 如果删除的是左子树的节点则父节点的平衡因子增加1。如果删除的是右子树的节点则父节点的平衡因子减少1。 在调整平衡因子的过程中如果某个节点的平衡因子的绝对值超过1就需要通过旋转来恢复平衡。 3.4.3、执行旋转操作 在删除节点并调整平衡因子后如果发现某个节点失衡则需要根据不同的失衡情况进行旋转操作。 3.4.4、总结 删除操作是AVL树中较为复杂的一部分。需要仔细处理删除节点的不同情况及时更新平衡因子并在必要时进行旋转操作以保持树的平衡。每个步骤都需要在 O(log⁡n) 的时间内完成确保 AVL 树的效率。通过精心设计的平衡调整机制AVL 树在删除操作后能够快速恢复平衡保持所有操作的时间复杂度为 O(log⁡n) 。 3.5、遍历操作 在 AVL 树中遍历是一项基础操作用于访问树中的每个节点。AVL 树继承了二叉搜索树BST的性质因此可以使用与 BST 相同的遍历方法包括前序遍历Pre-order Traversal、中序遍历In-order Traversal、后序遍历Post-order Traversal、层序遍历Level-order Traversal等。下面将详细介绍这些遍历方法并给出相应的代码实现。 3.5.1、前序遍历Pre-order Traversal 前序遍历的顺序是先访问根节点再访问左子树最后访问右子树。其遍历顺序为 “根 - 左 - 右”。 前序遍历的递归实现 // 前序遍历的递归实现 // 辅助函数 void _PreOrder(Node* root) {if (root nullptr){return;}std::cout root-_kv.first : root-_kv.second std::endl; // 访问根节点_PreOrder(root-_left); // 访问左子树_PreOrder(root-_right); // 访问右子树 }void PreOrder() {_PreOrder(_root);std::cout std::endl; }前序遍历的非递归实现使用栈 // 前序遍历的非递归实现 void PreOrder() {if (_root nullptr){return;}std::stackNode* stack;stack.push(_root);while (!stack.empty()) {Node* cur stack.top();stack.pop();std::cout cur-_kv.first : cur-_kv.second std::endl; // 访问当前节点// 先压入右子树再压入左子树确保左子树先处理if (cur-_right ! nullptr){stack.push(cur-_right);}if (cur-_left ! nullptr) {stack.push(cur-_left);}}std::cout std::endl; }3.5.2、中序遍历In-order Traversal 中序遍历的顺序是先访问左子树再访问根节点最后访问右子树。其遍历顺序为 “左 - 根 - 右”。对于 AVL 树中序遍历会得到一个按序排列的节点序列。 中序遍历的递归实现 // 中序遍历 void _InOrder(Node* root) {if (root nullptr){return;}_InOrder(root-_left);std::cout root-_kv.first : root-_kv.second std::endl;_InOrder(root-_right); }void InOrder() {_InOrder(_root);std::cout std::endl; }中序遍历的非递归实现使用栈 // 中序遍历 非递归 void InOrder() {std::stackNode* stack;Node* cur _root;while (cur ! nullptr || !stack.empty()) {// 找到最左边的节点while (cur ! nullptr) {stack.push(cur);cur cur-_left;}// 处理当前节点cur stack.top();stack.pop();std::cout cur-_kv.first : cur-_kv.second std::endl;// 转向右子树cur cur-_right;}std::cout std::endl; }3.5.3、后序遍历Post-order Traversal 后序遍历的顺序是先访问左子树再访问右子树最后访问根节点。其遍历顺序为 “左 - 右 - 根”。 后序遍历的递归实现 // 后序遍历的递归实现 // 辅助函数 void _PostOrder(Node* root) {if (root nullptr){return;}_PostOrder(root-_left); // 访问左子树_PostOrder(root-_right); // 访问右子树std::cout root-_kv.first : root-_kv.second std::endl; // 访问根节点 }void PostOrder() {_PostOrder(_root);std::cout std::endl; }后序遍历的非递归实现使用栈 // 后序遍历的非递归实现 void PostOrder() {if (_root nullptr){return;}std::stackNode* st;Node* cur _root;Node* lastNode nullptr; // 最近访问的节点while (cur || !st.empty()){while (cur){st.push(cur);cur cur-_left;}Node* top st.top();if ((top-_right nullptr) || (lastNode top-_right)){std::cout top-_kv.first : top-_kv.second std::endl;lastNode top;st.pop();}else {cur top-_right;}}std::cout std::endl; }3.5.4、层序遍历Level-order Traversal 层序遍历是按层次逐层访问节点先访问根节点再访问其左右子节点依次类推。可以使用队列来实现。 层序遍历的实现 // 层序遍历 void LevelOrder() {if (_root nullptr){return;}std::queueNode* queue;queue.push(_root);while (!queue.empty()){Node* cur queue.front();queue.pop();std::cout cur-_kv.first : cur-_kv.second std::endl; // 访问当前节点if (cur-_left ! nullptr) {queue.push(cur-_left); // 将左子树压入队列}if (cur-_right ! nullptr) {queue.push(cur-_right); // 将右子树压入队列}}std::cout std::endl; }3.5.5、总结 AVL 树的遍历方法与普通二叉搜索树类似包括前序遍历、中序遍历、后序遍历和层序遍历。通过递归或非递归方式我们可以访问 AVL 树的所有节点并按照特定的顺序输出它们的键值。中序遍历是最常用的遍历方法之一特别是在需要输出一个有序序列时。层序遍历则常用于按层次输出或分析树的结构。每种遍历方法都有其独特的应用场景在编写和理解 AVL 树的相关算法时选择合适的遍历方式十分重要。 3.6、查找操作 在AVL树中查找操作主要依赖于树的有序性即对于任意一个节点左子树的所有节点都小于该节点右子树的所有节点都大于该节点。查找过程从根节点开始逐层向下比较查找值与当前节点的值并根据比较结果选择进入左子树或右子树。 3.6.1、查找操作的步骤 从根节点开始从AVL树的根节点开始查找。比较当前节点的键值 如果查找的键等于当前节点的键查找成功返回当前节点。如果查找的键小于当前节点的键进入左子树继续查找。如果查找的键大于当前节点的键进入右子树继续查找。 递归或迭代重复上述步骤直到找到匹配的节点或者子树为空查找失败。返回结果找到目标节点则返回否则返回 nullptr表示查找失败。 3.6.2、查找的递归实现 递归实现相对简单直接通过函数递归调用在树中查找目标节点。 // 查找的递归实现 // 辅助函数 Node* _find(Node* root, const K key) {if (root nullptr || root-_kv.first key){return root;}if (key root-_kv.first){return _find(root-_left, key);}else{return _find(root-_right, key);} }3.6.3、查找的非递归实现 非递归实现使用迭代方式避免了递归调用带来的额外栈空间开销。 // 查找 非递归 Node* Find(const K key) {Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_left;}else if (cur-_kv.first key){cur cur-_right;}else{return cur;}}return nullptr; }4、AVL 树的其他功能 除了基本的插入、查找、删除等操作AVL 树还可以实现一些高级操作如查找前驱和后继、区间查询、树的高度、判断是否是平衡二叉树等。这些操作可以扩展 AVL 树的功能增加其实用性。 4.1、查找后继节点 前驱是指比某个节点值小的最大节点后继则是比某个节点值大的最小节点。在 AVL 树中查找前驱和后继是常见的操作尤其在区间查询或范围搜索时非常有用。 查找后继的递归实现 // 查找后继节点 Node* findMin(Node* node) {while (node-_left ! nullptr){node node-_left;}return node; }Node* FindSuccessor(Node* node) {if (node-_right ! nullptr){return findMin(node-_right);}Node* cur _root;Node* successor nullptr;while (cur ! nullptr){if (node-_kv.first cur-_kv.first){successor cur;cur cur-_left;}else if (node-_kv.first cur-_kv.first){cur cur-_right;}else{break;}}return successor; }查找后继时如果节点有右子树则后继为右子树中最小的节点否则后继为第一个大于该节点的祖先节点。 4.2、查找前驱节点 查找前驱的递归实现 // 查找前驱节点 Node* findMax(Node* node) {while (node-_right ! nullptr){node node-_right;}return node; }Node* FindPredecessor(Node* node) {if (node-_left ! nullptr){return findMax(node-_left);}Node* cur _root;Node* predecessor nullptr;while (cur ! nullptr){if (node-_kv.first cur-_kv.first){cur cur-_left;}else if (node-_kv.first cur-_kv.first){predecessor cur;cur cur-_right;}else{break;}}return predecessor; }前驱的查找逻辑与后继类似只是方向相反。 4.3、获取树的高度 // 获取树的高度 int Height(Node* root) {if (root nullptr){return 0;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; }4.4、判断是否是平衡二叉树 // 判断是否是平衡二叉树 bool _IsBalance(Node* root) {if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (abs(leftHeight - rightHeight) 1){return false;}return _IsBalance(root-_left) _IsBalance(root-_right); }bool IsBalance() {return _IsBalance(_root); }5、完整实现代码和测试 5.1、AVLTree.hpp #pragma once#include iostream #include stack #include queuenamespace Lenyiin {template class K, class Vstruct AVLTreeNode{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf; // balance factor 平衡因子std::pairK, V _kv; // key-value// 普通构造AVLTreeNode(const std::pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}};template class K, class Vclass AVLTree{private:typedef AVLTreeNodeK, V Node;public:bool Insert(const std::pairK, V kv){// 1. 先按搜索树的规则进行插入if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false; // 如果相等, 表示已经有了, 不需要插入}}// 找到位置cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}// 2. 更新平衡因子while (parent){if (cur parent-_right){parent-_bf; // 插在右边, 平衡因子}else{parent-_bf–; // 插在左边, 平衡因子–}if (parent-_bf 0){// 说明 parent 所在的子树高度不变, 更新结束break;}else if (parent-_bf 1 || parent-_bf -1){// 说明 parent 所在子树的高度变了, 继续往上更新cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){// parent 所在的子树出现问题了, 需要旋转处理一下// 1. 旋转前提是保持它依旧是搜索二叉树// 2. 旋转成平衡树if (parent-_bf 2){if (cur-_bf 1){// 左旋RotateL(parent);}else if (cur-_bf -1){// 右左双旋RotateRL(parent);}}else if (parent-_bf -2){if (cur-_bf -1){// 右旋RotateR(parent);}else if (cur-_bf 1){// 左右双旋RotateLR(parent);}}// 旋转完成后, parent 所在的树的高度恢复到了插入节点前的高度// 如果是子树, 对上一层没有影响, 更新结束break;}}return true;}// 左单旋void RotateL(Node* parent){Node* ppNode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;// 1. 原来 parent 是这棵树的根, 现在 subR 是根if (parent _root){_root subR;subR-_parent nullptr;}// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}parent-_bf subR-_bf 0;}// 右单旋void RotateR(Node* parent){Node* ppNode parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}parent-_bf subL-_bf 0;}// 右左双旋void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}}// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (bf 1){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}}// 中序遍历//void _InOrder(Node* root)//{// if (root nullptr)// {// return;// }// _InOrder(root-_left);// std::cout root-_kv.first : root-_kv.second std::endl;// _InOrder(root-_right);//}//void InOrder()//{// _InOrder(_root);// std::cout std::endl;//}// 中序遍历 非递归void InOrder(){std::stackNode* stack;Node* cur _root;while (cur ! nullptr || !stack.empty()) {// 找到最左边的节点while (cur ! nullptr) {stack.push(cur);cur cur-_left;}// 处理当前节点cur stack.top();stack.pop();std::cout cur-_kv.first : cur-_kv.second std::endl;// 转向右子树cur cur-_right;}std::cout std::endl;}// 前序遍历的递归实现// 辅助函数//void _PreOrder(Node* root)//{// if (root nullptr)// {// return;// }// std::cout root-_kv.first : root-_kv.second std::endl; // 访问根节点// _PreOrder(root-_left); // 访问左子树// _PreOrder(root-_right); // 访问右子树//}//void PreOrder()//{// _PreOrder(_root);// std::cout std::endl;//}// 前序遍历的非递归实现void PreOrder(){if (_root nullptr){return;}std::stackNode* stack;stack.push(_root);while (!stack.empty()) {Node* cur stack.top();stack.pop();std::cout cur-_kv.first : cur-_kv.second std::endl; // 访问当前节点// 先压入右子树再压入左子树确保左子树先处理if (cur-_right ! nullptr){stack.push(cur-_right);}if (cur-_left ! nullptr) {stack.push(cur-_left);}}std::cout std::endl;}// 后序遍历的递归实现// 辅助函数//void _PostOrder(Node* root) {// if (root nullptr)// {// return;// }// _PostOrder(root-_left); // 访问左子树// _PostOrder(root-_right); // 访问右子树// std::cout root-_kv.first : root-_kv.second std::endl; // 访问根节点//}//void PostOrder()//{// _PostOrder(_root);// std::cout std::endl;//}// 后序遍历的非递归实现void PostOrder(){if (_root nullptr){return;}std::stackNode* st;Node* cur _root;Node* lastNode nullptr; // 最近访问的节点while (cur || !st.empty()){while (cur){st.push(cur);cur cur-_left;}Node* top st.top();if ((top-_right nullptr) || (lastNode top-_right)){std::cout top-_kv.first : top-_kv.second std::endl;lastNode top;st.pop();}else {cur top-_right;}}std::cout std::endl;}// 层序遍历void LevelOrder(){if (_root nullptr){return;}std::queueNode* queue;queue.push(_root);while (!queue.empty()){Node* cur queue.front();queue.pop();std::cout cur-_kv.first : cur-_kv.second std::endl; // 访问当前节点if (cur-_left ! nullptr) {queue.push(cur-_left); // 将左子树压入队列}if (cur-_right ! nullptr) {queue.push(cur-_right); // 将右子树压入队列}}std::cout std::endl;}// 查找后继节点Node* findMin(Node* node){while (node-_left ! nullptr){node node-_left;}return node;}Node* FindSuccessor(Node* node){if (node-_right ! nullptr){return findMin(node-_right);}Node* cur _root;Node* successor nullptr;while (cur ! nullptr){if (node-_kv.first cur-_kv.first){successor cur;cur cur-_left;}else if (node-_kv.first cur-_kv.first){cur cur-_right;}else{break;}}return successor;}// 查找前驱节点Node* findMax(Node* node){while (node-_right ! nullptr){node node-_right;}return node;}Node* FindPredecessor(Node* node){if (node-_left ! nullptr){return findMax(node-_left);}Node* cur _root;Node* predecessor nullptr;while (cur ! nullptr){if (node-_kv.first cur-_kv.first){cur cur-_left;}else if (node-_kv.first cur-_kv.first){predecessor cur;cur cur-_right;}else{break;}}return predecessor;}// 获取树的高度int Height(Node* root){if (root nullptr){return 0;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}// 判断是否是平衡二叉树bool _IsBalance(Node* root){if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (abs(leftHeight - rightHeight) 1){return false;}return _IsBalance(root-_left) _IsBalance(root-_right);}bool IsBalance(){return _IsBalance(_root);}// 查找 非递归//Node* Find(const K key)//{// Node* cur _root;// while (cur)// {// if (cur-_kv.first key)// {// cur cur-_left;// }// else if (cur-_kv.first key)// {// cur cur-_right;// }// else// {// return cur;// }// }// return nullptr;//}// 查找的递归实现// 辅助函数Node* _find(Node* root, const K key){if (root nullptr || root-_kv.first key){return root;}if (key root-_kv.first){return _find(root-_left, key);}else{return _find(root-_right, key);}}// 查找节点Node* Find(const K key){return _find(_root, key);}private:Node* _root nullptr;}; }5.2、AVLTree.cpp #include AVLTree.hppusing namespace Lenyiin;void test_AVLTree() {//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};AVLTreeint, int t;for (const auto e : a){t.Insert(std::make_pair(e, e));}t.InOrder();t.PreOrder();t.PostOrder();t.LevelOrder();std::cout t.IsBalance() std::endl;auto ret t.Find(6);if (ret nullptr){std::cout 没有找到 std::endl;}else{std::cout 找到了 std::endl;std::cout ret-_kv.first : ret-_kv.second std::endl;}auto pre t.FindPredecessor(ret);if (pre ! nullptr){std::cout ret-_kv.first 的前驱节点是: pre-_kv.first std::endl;}else{std::cout 前驱节点为空 std::endl;}auto suc t.FindSuccessor(ret);if (suc ! nullptr){std::cout ret-_kv.first 的后继节点是: suc-_kv.first std::endl;}else{std::cout 后继节点为空 std::endl;} }int main() {test_AVLTree();return 0; }6、AVL树的优缺点和总结 6.1、优点 平衡性保证AVL 树是自平衡二叉搜索树它严格保持了树的平衡状态。每个节点的左右子树高度差平衡因子最多为 1因此在最坏情况下AVL 树的高度被限制在 O(log⁡n) 级别。这保证了查找、插入、删除操作的时间复杂度始终为 O(log⁡n) 使其在各种场景中表现出较高的效率。快速查找由于 AVL 树保持了较高的平衡性查找操作的性能得到了优化。相比于未平衡的二叉搜索树AVL 树在查找操作中能够更快地找到目标节点。稳定的性能AVL 树的平衡性维护使得其在最坏情况下例如频繁的插入和删除操作也能提供稳定的性能。无论数据插入的顺序如何AVL 树都能保持平衡避免出现链表化的情况。较好的空间利用率AVL 树在保持平衡的同时并不需要额外的节点空间除了存储平衡因子。相比红黑树等其他自平衡树AVL 树的平衡性更严格查找性能更好。 6.2、缺点 插入和删除的复杂性AVL 树在插入和删除节点时需要进行旋转操作以保持树的平衡。每次插入或删除操作都可能导致树的不平衡从而触发重新平衡过程。虽然旋转操作的时间复杂度为 O(1) 但在频繁的插入和删除场景中这些旋转操作可能增加整体的处理时间。实现复杂性AVL 树的实现相对较复杂尤其是插入和删除操作。与红黑树相比AVL 树需要更多的旋转操作来维持平衡这使得其代码编写和维护的难度较大。额外的存储空间为了维护平衡性AVL 树的每个节点需要额外存储平衡因子(balance factor)这增加了节点的内存开销。虽然这一开销较小但对于内存非常敏感的系统可能会有一定的影响。性能折衷尽管 AVL 树在查找操作中表现优异但其插入和删除操作的性能可能会受到影响。在一些场景中如需要频繁插入和删除的情况下红黑树可能比 AVL 树更具优势因为红黑树的旋转操作次数通常比 AVL 树少。 6.3、总结 AVL 树是一种自平衡的二叉搜索树它通过在每次插入和删除节点时自动调整自身结构确保树的高度始终保持在 O(log⁡n) 级别从而提供高效的查找、插入和删除操作。AVL 树的核心优势在于其严格的平衡性这使得它在查找操作中具有较高的性能并且在最坏情况下也能保持较优的时间复杂度。 然而这种严格的平衡性也带来了更高的实现复杂性和插入、删除操作的额外开销。在需要频繁插入和删除的应用场景中AVL 树的性能可能不如红黑树等其他自平衡树。此外AVL 树的每个节点需要额外存储平衡因子略微增加了内存开销。 尽管如此AVL 树在追求高效查找操作的场景中仍然是一个非常实用的数据结构。它适用于需要快速数据访问、并且插入和删除操作相对较少的场景如字典、集合等。在实际应用中应根据具体的需求和场景综合考虑选择适合的自平衡二叉树结构。 通过本博客对 AVL 树的全面阐述希望能够帮助读者更好地理解和运用 AVL 树并在实际开发中合理选择和实现这一数据结构。 希望这篇博客对您有所帮助也欢迎您在此基础上进行更多的探索和改进。如果您有任何问题或建议欢迎在评论区留言我们可以共同探讨和学习。更多知识分享可以访问我的个人博客网站 https://blog.lenyiin.com/ 。本博客所涉及的代码也可以访问我的 git 仓库获取 https://git.lenyiin.com/Lenyiin/AVLTree