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

C++-AVL树

news 2025/8/11 12:59:31

        前面对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.xdnf.cn/news/1266175.html

相关文章：

  • 词向量基础：从独热编码到分布式表示的演进
  • 微软将于 10 月停止混合 Exchange 中的共享 EWS 访问
  • Codeforces 思维训练（二）
  • [激光原理与应用-206]：光学器件 - SESAM - 基本结构与工作原理
  • 爬虫攻防战：反爬与反反爬全解析
  • 跨境电商系统开发：ZKmall开源商城的技术选型与代码规范实践
  • sqli-labs通关笔记-第40关 GET字符型堆叠注入(单引号括号闭合 手工注入+脚本注入两种方法)
  • 多级缓存详解
  • 【能碳建设1】用AI+开源打造物联网+能碳管理+交易SaaS系统的最短路径实施指南
  • 软件定义车辆加速推进汽车电子技术
  • 快速使用selenium+java案例
  • [Linux]学习笔记系列 -- [arm][lds]
  • 2022 RoboCom 世界机器人开发者大赛-本科组（国赛）
  • 前端工程化：从构建工具到性能监控的全流程实践
  • 2G内存的服务器用宝塔安装php的fileinfo拓展时总是卡死无法安装成功的解决办法
  • Ubuntu下搭建LVGL模拟器
  • 【第2.1话：基础知识】基于Ubuntu的ROS环境搭建与车辆可视化编程实践：初学者指南及RVIZ应用（含作业及代码）
  • Ubuntu Server 22 虚拟机空间扩容
  • ubuntu dpkg命令使用指南
  • 从零玩转Linux云主机：免费申请、连接终端、命令速查表
  • 【SQL进阶】用EXPLAIN看透SQL执行计划：从“盲写“到“精准优化“
  • 【JavaEE】(11) 前端基础三件套
  • 比亚迪第五代DM技术：AI能耗管理的深度解析与实测验证
  • 数学与应用数学：到底有啥区别？
  • Kafka学习记录
  • 建筑物实例分割数据集-9,700 张图片 城市规划与发展 灾害评估与应急响应 房地产市场分析 智慧城市管理 地理信息系统(GIS) 环境影响评估
  • Java安全-组件安全
  • 关于灰度图像相似度的损失函数（笔记）
  • C++安全异常设计
  • 华为交换机进阶功能和场景化配置