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

C++-AVL树

news 2025/8/10 5:18:32

        前面对map/multimap/set/multiset进行了简单的介绍，其中我们发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中 插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

1、AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

        如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log_2 n)。

2、AVL树节点结构解析

设计思路：

  • 每个节点存储键值对，用于排序和查找

  • 包含左右子节点指针实现树结构

  • 添加父节点指针便于回溯调整平衡

  • 平衡因子_bf记录子树高度差，用于判断是否需要旋转

template<class K,class V>
struct AVLTreeNode
{pair<K, V> _kv;                  // 存储键值对AVLTreeNode<K, V>* _left;        // 左子节点指针AVLTreeNode<K, V>* _right;       // 右子节点指针AVLTreeNode<K, V>* _parent;      // 父节点指针（方便回溯调整）int _bf;                         // 平衡因子：右子树高度 - 左子树高度AVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr),_parent(nullptr),_bf(0){}
};

3、AVL树插入操作详解

插入操作思路：

  1. 按照BST规则找到插入位置

  2. 插入新节点后，从插入点向上回溯更新平衡因子

  3. 根据平衡因子的变化决定是否需要旋转调整

  4. 旋转后局部子树恢复平衡，整棵树达到平衡状态

bool insert(const pair<K, V>& kv)
{// 1. 空树情况直接插入if (_root == nullptr){_root = new Node(kv);return true;}// 2. 寻找插入位置（标准BST插入逻辑）Node* cur = _root;Node* parent = nullptr;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;  // 键已存在，插入失败}}// 3. 创建新节点并插入到正确位置cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 4. 更新平衡因子并调整平衡（AVL核心）while (parent){// 更新父节点的平衡因子if (cur == parent->_left)  // 插入在左子树，平衡因子减1parent->_bf--;  else if (cur == parent->_right)  // 插入在右子树，平衡因子加1parent->_bf++;  // 判断平衡状态if (parent->_bf == 1 || parent->_bf == -1){// 树高度变化，但仍在平衡范围内，继续向上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == 0){// 树高度不变，更新结束break;}else if (parent->_bf == 2 || parent->_bf == -2){// 需要旋转调整（四种情况）if (parent->_bf == 2 && cur->_bf == 1)      // 右子树更高且右子树的右子树更高RotateL(parent);  // 左单旋else if (parent->_bf == -2 && cur->_bf == -1)// 左子树更高且左子树的左子树更高RotateR(parent);  // 右单旋else if (parent->_bf == 2 && cur->_bf == -1) // 右子树更高但右子树的左子树更高RotateRL(parent); // 右左双旋else if (parent->_bf == -2 && cur->_bf == 1) // 左子树更高但左子树的右子树更高RotateLR(parent);  // 左右双旋break;  // 旋转后子树高度恢复，停止更新}else{assert(false);  // 平衡因子异常，不应该出现}}return true;
}

4、四种旋转操作详解

1. 左单旋（LL型不平衡）

适用场景：当节点的右子树过高（平衡因子为2），且右子节点的右子树过高（右子节点平衡因子为1）

旋转思路：

  1. 将右子节点cur提升为新的根

  2. 将cur的左子树挂接到原parent的右侧

  3. 将原parent变为cur的左子节点

  4. 更新所有相关节点的父指针

  5. 重置平衡因子

void RotateL(Node* parent)
{Node* cur = parent->_right;  // 右子节点将成为新的根// 1. 处理cur的左子树（挂接到parent的右侧）parent->_right = cur->_left;if (cur->_left)cur->_left->_parent = parent;// 2. 提升cur为新的根cur->_left = parent;// 3. 更新父指针关系Node* pparent = parent->_parent;parent->_parent = cur;// 处理原parent的父节点指向if (pparent == nullptr)  // parent是根节点{_root = cur;cur->_parent = nullptr;}else  // parent不是根节点{if (pparent->_left == parent)pparent->_left = cur;elsepparent->_right = cur;cur->_parent = pparent;}// 4. 更新平衡因子（旋转后两边高度平衡）parent->_bf = 0;cur->_bf = 0;
}

2. 右单旋（RR型不平衡）

适用场景：当节点的左子树过高（平衡因子为-2），且左子节点的左子树过高（左子节点平衡因子为-1）

旋转思路：

  1. 将左子节点cur提升为新的根

  2. 将cur的右子树挂接到原parent的左侧

  3. 将原parent变为cur的右子节点

  4. 更新所有相关节点的父指针

  5. 重置平衡因子

void RotateR(Node* parent)
{Node* cur = parent->_left;  // 左子节点将成为新的根// 1. 处理cur的右子树（挂接到parent的左侧）parent->_left = cur->_right;if (cur->_right)cur->_right->_parent = parent;// 2. 提升cur为新的根cur->_right = parent;// 3. 更新父指针关系Node* pparent = parent->_parent;parent->_parent = cur;// 处理原parent的父节点指向if (pparent == nullptr)  // parent是根节点{_root = cur;cur->_parent = nullptr;}else  // parent不是根节点{if (pparent->_left == parent)pparent->_left = cur;elsepparent->_right = cur;cur->_parent = pparent;}// 4. 更新平衡因子parent->_bf = 0;cur->_bf = 0;
}

3. 右左双旋（RL型不平衡）

适用场景：当节点的右子树过高（平衡因子为2），但右子节点的左子树过高（右子节点平衡因子为-1）

旋转思路：

  1. 先对右子节点进行右旋，转换为LL情况

  2. 再对父节点进行左旋

  3. 根据旋转前curleft的平衡因子调整各节点的新平衡因子

    • 如果curleft是新增节点（bf=0），所有相关节点平衡因子归零

    • 如果新增节点在curleft左侧（bf=-1），调整cur和parent的平衡因子

    • 如果新增节点在curleft右侧（bf=1），调整parent的平衡因子

void RotateRL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;  // 保存旋转前的平衡因子// 1. 先对cur右旋（转换为LL情况）RotateR(parent->_right);// 2. 再对parent左旋RotateL(parent);// 3. 根据原curleft的平衡因子调整if (bf == 0)  // curleft是新增节点{cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == -1)  // 新增节点在curleft的左子树{cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1)  // 新增节点在curleft的右子树{cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else{assert(false);  // 不应该出现其他情况}
}

4. 左右双旋（LR型不平衡）

适用场景：当节点的左子树过高（平衡因子为-2），但左子节点的右子树过高（左子节点平衡因子为1）

旋转思路：

  1. 先对左子节点进行左旋，转换为RR情况

  2. 再对父节点进行右旋

  3. 根据旋转前curright的平衡因子调整各节点的新平衡因子

    • 如果curright是新增节点（bf=0），所有相关节点平衡因子归零

    • 如果新增节点在curright左侧（bf=-1），调整parent的平衡因子

    • 如果新增节点在curright右侧（bf=1），调整cur的平衡因子

void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;  // 保存旋转前的平衡因子// 1. 先对cur左旋（转换为RR情况）RotateL(parent->_left);// 2. 再对parent右旋RotateR(parent);// 3. 根据原curright的平衡因子调整if (bf == 0)  // curright是新增节点{cur->_bf = 0;curright->_bf = 0;parent->_bf = 0;}else if (bf == -1)  // 新增节点在curright的左子树{cur->_bf = 0;curright->_bf = 0;parent->_bf = 1;}else if (bf == 1)  // 新增节点在curright的右子树{cur->_bf = -1;curright->_bf = 0;parent->_bf = 0;}else{assert(false);  // 不应该出现其他情况}
}

5、平衡检查函数解析

设计思路：

  1. Height函数递归计算树的高度

  2. IsBalance函数递归检查：

    • 每个节点的平衡因子是否正确（与实际高度差一致）

    • 每个节点的左右子树高度差不超过1

    • 递归检查所有子树是否平衡

// 计算树的高度（递归实现）
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()
{return IsBalance(_root);
}// 递归检查子树是否平衡
bool IsBalance(Node* root)
{if (root == nullptr)return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);// 检查平衡因子是否正确（重要验证）if (rightHeight - leftHeight != root->_bf){cout << "平衡因子异常：" << root->_kv.first << "->" <<root->_bf << endl;return false;}// 检查高度差和子树平衡return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);
}

6、总结

AVL树通过四种旋转操作维持平衡：

  1. 左单旋：处理LL型不平衡

  2. 右单旋：处理RR型不平衡

  3. 右左双旋：处理RL型不平衡

  4. 左右双旋：处理LR型不平衡

        每种旋转操作都有其特定的适用场景，通过合理组合这些操作，AVL树能够在插入和删除节点后快速恢复平衡，保证高效的查找性能。平衡检查函数则用于验证树的正确性，是调试和测试的重要工具。

http://www.lryc.cn/news/614837.html

相关文章：

  • 微软将于 10 月停止混合 Exchange 中的共享 EWS 访问
  • SOLi-LABS Page-3 (Stacked injections) --39-53关
  • 使用 Vuepress + GitHub Pages 搭建项目文档（2）- 使用 GitHub Actions 工作流自动部署
  • 如何解决 Vue 项目启动时出现的 “No such module: http_parser” 错误问题
  • 2G内存的服务器用宝塔安装php的fileinfo拓展时总是卡死无法安装成功的解决办法
  • 企业级web应用服务器TOMCAT入门详解
  • kettle插件-kettle MinIO插件，轻松解决文件上传到MinIO服务器
  • 解决本地连接服务器ollama的错误
  • 大语言模型提示工程与应用：大语言模型对抗性提示安全防御指南
  • LLVM编译器入门
  • Java基础-TCP通信单服务器接受多客户端
  • 关于开发语言的一些效率 从堆栈角度理解一部分c java go python
  • 软考 系统架构设计师系列知识点之杂项集萃（119）
  • 数据结构（9）——排序
  • QT第三讲- 机制、宏、类库模块
  • 数字图像处理基础——opencv库（Python）
  • 算法_python_牛客华为机试笔记_01
  • 【Python 高频 API 速学 ③】
  • RecyclerView 中 ViewHolder
  • TDengine IDMP 快速体验（1. 通过云服务）
  • 【CVPR2025】计算机视觉|PX：让模型训练“事半功倍”！
  • vscode/trae 的 settings.json 中配置 latex 的一些记录
  • 设备点检系统二维码的应用
  • 我用C++和零拷贝重构了文件服务器，性能飙升3倍，CPU占用降低80%
  • Amazon Linux 训练lora模型的方式
  • 《算法导论》第 14 章 - 数据结构的扩张
  • ruoyi关闭shiro校验，任何接口可以直接访问
  • C++-红黑树
  • [C/C++线程安全]_[中级]_[多线程如何使用共享锁提升性能]
  • Meta AI水印计划的致命缺陷——IEEE Spectrum深度文献精读