目录1. 基本定义2. 核心特性3. AVL树节点的定义4. 自平衡机制旋转操作4.1 左单旋LeftRotate4.2 右单旋RightRotate4.3 左右双旋LRRotate4.4 右左双旋RLRotate5. AVL树的插入6. AVL树的删除了解7. AVL树的查找8. 获取树的高度9. AVL树的验证9.1 BST 性质验证9.2 AVL 平衡条件验证10. 总结1. 基本定义AVL 树Adelson-Velsky and Landis Tree是最早被发明的自平衡二叉搜索树由苏联数学家 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年提出。由于普通二叉搜索树在最坏情况下如顺序插入会退化为链表导致查找、插入删除操作的时间复杂度会从Olog n退化为On。AVL树通过严格控制树高确保所有操作的时间复杂度稳定在Olog n。2. 核心特性是二叉搜索树 (BST)满足 BST 性质左子树所有节点值 根节点值 右子树所有节点值。严格平衡条件每个节点的左右子树高度差 (平衡因子) 的绝对值不超过 1即平衡因子只能为 - 1、0 或 1。左右子树本身也必须是 AVL 树。平衡因子 (BF) 节点右子树高度 - 节点左子树高度3. AVL树节点的定义在二叉搜索树的基础上新增两个关键字段平衡因子_bf直接存储当前节点的平衡状态无需动态计算取值范围为-1, 0 ,1平衡状态若为2/-1则表示节点失衡需触发旋转操作。父节点指针parent用于插入或删除节点后从该节点向上回溯祖先节点逐个检查并更新它们的平衡因子。定义AVL树节点key/value 模型的AVL树templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; //平衡因子balance factor AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) //新节点为叶子平衡因子初始为0 {} };关于pair的使用在C中std::pair是标准模版库STL提供的一个轻量级模版类用于存储一对关联的数据两个元素它的核心作用是将两个值“捆绑”成一个单一的对象方便在函数返回、容器存储等场景中使用。std::pair定义在utility头文件中其模版声明如下template class T1, class T2 struct pair { T1 first; // 第一个元素 T2 second; // 第二个元素 // 构造函数等成员编译器自动生成 };pair的使用int main() { // 初始化一个 (int, string) 类型的pair pairint, string p1(10, hello); //直接构造 // 自动推导为 pairint, string auto p2 make_pair(10, world); //make_pair是一个辅助函数可自动推导类型简化初始化 pairstring, int p3{ age, 25 }; //列表初始化C11 pairint, int p4(1, 2); p4.first 100; // 访问并修改第一个元素 p4.second 200; // 访问并修改第二个元素 // 此时p4为 (100, 200) pairint, int p5; p5 p4; // 整体赋值p5 变为 (100, 200) //std::pair重载了常见的比较运算符、!、、、、比较规则为字典序 //1. 先比较first元素若不相等则结果由first决定; //2. 若first相等再比较second元素; if (p1 p2) //truefirst相等second hello world { cout p1 p2 endl; } if (p4 p5)//false { cout p4 p5 endl; } if (p4 p5)//true { cout p4 p5 endl; } return 0; }4.自平衡机制旋转操作4.1 左单旋LeftRotate左旋解决了右子树过高导致的失衡问题。它通过调整节点间的父子关系降低右子树高度使树重新满足平衡条件所有节点的平衡因子绝对值≤1。左旋的本质是将失衡节点的右子节点“提升”为新根节点原失衡节点成为新父节点的左子节点同时新父节点原来的左子树成为原失衡节点的右子树。插入操作左旋的触发条件该节点的平衡因子为2失衡节点。该节点右孩子的平衡因子为1。//左单旋 void LeftRotate(Node* parent) { Node* subR parent-_right; //失衡节点的右孩子(9) Node* subRL subR-_left; //失衡节点的右孩子的左孩子(6) parent-_right subRL; //6成为5的右子树 if (subRL)//判断subRL是否为空防止对空指针解引用6有可能不存在 subRL-_parent parent;//更改6的父指针为5 Node* parentparent parent-_parent;//5可能还有父亲节点记录5的父节点 subR-_left parent; //5成为9的左子树 parent-_parent subR;//更改5的父指针 if (parentparent nullptr)//如果5没有父节点那么9直接成为新根再将9的父指针置空 { _root subR; subR-_parent nullptr; } else //如果5存在父节点 { if (parentparent-_left parent) //5原来是pp的左子节点 { parentparent-_left subR; } else { parentparent-_right subR; //5原来是pp的右子节点 } subR-_parent parentparent; //更新9的父指针 } //更新平衡因子旋转后5和9的平衡因子均变为0 parent-_bf 0; subR-_bf 0; }4.2 右单旋RightRotate右旋用于解决左子树过高导致的失衡问题。通过调整节点间的父子关系降低左子树高度使树重新满足平衡条件所有节点的平衡因子绝对值≤1。右旋的本质是将失衡节点的左子节点 “提升” 为新的父节点原失衡节点则成为新父节点的右子节点同时新父节点原来的右子树将作为原失衡节点的左子树。插入操作右旋的触发条件该节点的平衡因子为-2失衡节点。该节点左孩子的平衡因子为-1。//右单旋 void RightRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentparent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parent parentparent-_left) { parentparent-_left subL; } else { parentparent-_right subL; } subL-_parent parentparent; } //更新平衡因子 subL-_bf 0; parent-_bf 0; }4.3 左右双旋LRRotate左右双旋是一种复合旋转操作用于处理左子树的右子树过高导致的特殊失衡场景。当单旋右旋无法直接修复失衡时需通过 “先左旋、后右旋” 的组合操作使树恢复平衡。左右双旋的触发条件该节点的平衡因子为-2失衡节点。失衡节点的左孩子平衡因子为1。左右双旋通过两步旋转将失衡调整为平衡状态第一步对失衡节点的左子节点进行左旋将“左—右”偏斜修正为“左—左”偏斜即一边高第二步对原失衡节点执行右旋修复“左—左”偏斜导致的失衡。情况1中由于对失衡节点的左孩子左旋操作将节点5和节点8的平衡因子都更新为0对失衡节点右旋操作将节点10和节点8的平衡因子更新为0通过图示我们发现计算出节点10的平衡因子并不为0而是1所以parent节点需要单独处理一下对于情况2需要单独处理subL节点情况3不需要单独处理不过为了保险起见可以在左右双旋代码中再次更新一边平衡因子。//左右双旋 void LRRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf;//记录subLR的平衡因子然后分三种情况讨论 LeftRotate(parent-_left);//左旋操作 RightRotate(parent);//右旋操作 //更新平衡因子 if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; //需要单独处理parent节点的平衡因子 } else if (bf 1) { subLR-_bf 0; subL-_bf -1; //需要单独处理subL节点的平衡因子 parent-_bf 0; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); //防御式编程 } }4.4 右左双旋RLRotate右左双旋复合旋转操作用于处理右子树的左子树过高导致的特殊失衡场景。当单旋左旋无法直接修复失衡时需通过 “先右旋、后左旋” 的组合操作使树恢复平衡。右左双旋的触发条件该节点的平衡因子为2失衡节点。失衡节点的右孩子平衡因子为-1。右左双旋通过两步旋转将失衡调整为平衡状态第一步对失衡节点的右子节点进行右旋将“右—左”偏斜修正为“右—右”偏斜即一边高第二步对原失衡节点执行左旋修复“右—右”偏斜导致的失衡。情况1中由于对失衡节点的右孩子右旋操作将节点9和节点6的平衡因子都更新为0对失衡节点左旋操作将节点4和节点6的平衡因子更新为0通过图示我们发现计算出节点9的平衡因子并不为0而是1所以subR节点需要单独处理一下对于情况2需要单独处理parent节点情况3不需要单独处理不过为了保险起见可以在左右双旋代码中再次更新一边平衡因子。//右左双旋 void RLRotate(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; //记录subRL的平衡因子然后分三种情况讨论 RightRotate(parent-_right);//右旋操作 LeftRotate(parent);//左旋操作 //更新平衡因子 if (bf -1) { subRL-_bf 0; subR-_bf 1; //需要单独处理subR节点的平衡因子 parent-_bf 0; } else if (bf 1) { subRL-_bf 0; subR-_bf 0; parent-_bf -1; //需要单独处理parent节点的平衡因子 } else if (bf 0) { subRL-_bf 0; subR-_bf 0; parent-_bf 0; } else { assert(false); } }5. AVL树的插入bool Insert(const pairK, V kv) { 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-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 更新平衡因⼦ while (parent) { if (cur parent-_left) parent-_bf--; else parent-_bf; if (parent-_bf 0) { // 更新结束 break; } else if (parent-_bf 1 || parent-_bf -1) { // 继续往上更新 cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { // 不平衡了旋转处理 if (parent-_bf -2 cur-_bf -1) { RightRotate(parent); //右旋 } else if (parent-_bf 2 cur-_bf 1) { LeftRotate(parent); //左旋 } else if (parent-_bf -2 cur-_bf 1) { LRRotate(parent); //左右双旋 } else if (parent-_bf 2 cur-_bf -1) { RLRotate(parent); //右左双旋 } else { assert(false); } break; } else { assert(false); } } return true; }6. AVL树的删除了解AVL树的插入操作最多只需一次失衡调整即可恢复整体平衡而删除操作与插入操作不同的是删除操作可能引发连锁的失衡传播可能不止调整一次失衡删除节点后需要依次对每个祖先节点进行检查。7. AVL树的查找Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) cur cur-_right; else if (key cur-_kv.first) cur cur-_left; else return cur; } return nullptr; }8. 获取树的高度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; }9. AVL树的验证AVL 树的验证是确保其同时满足二叉搜索树BST性质和AVL 平衡条件的过程。只有同时满足这两个条件才能称为合法的 AVL 树。9.1 BST 性质验证中序遍历有序void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); }9.2 AVL 平衡条件验证bool _IsBalanceTree(Node* root) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }优化方案在一次递归中同时计算高度和检查平衡通过返回值如pairbool,int同时携带 “是否平衡” 和 “子树高度”避免重复计算。优化后时间复杂度可降为O(n)示例如下// 返回值first为是否平衡second为子树高度 pairbool, int _IsBalanceTreeOptimized(Node* root) { if (root nullptr) { return {true, 0}; // 空树平衡高度0 } // 递归检查左子树 auto leftRes _IsBalanceTreeOptimized(root-_left); if (!leftRes.first) return {false, 0}; // 左子树失衡直接返回 // 递归检查右子树 auto rightRes _IsBalanceTreeOptimized(root-_right); if (!rightRes.first) return {false, 0}; // 右子树失衡直接返回 // 计算实际平衡因子 int diff rightRes.second - leftRes.first; // 检查结构平衡 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return {false, 0}; } // 检查平衡因子一致性 if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return {false, 0}; } // 返回当前子树高度1 左右子树最大高度 return {true, 1 max(leftRes.second, rightRes.second)}; }10. 总结总结AVL 树是一种自平衡二叉搜索树通过控制树高在 log₂n 级别使查找、插入、删除操作的时间复杂度稳定在 O (log n)。AVL树的实现删除操作这里不做研究templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; //平衡因子balance factor AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) // 新节点为叶子平衡因子初始为0 {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: //插入 bool Insert(const pairK, V kv) { 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-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 更新平衡因⼦ while (parent) { if (cur parent-_left) parent-_bf--; else parent-_bf; if (parent-_bf 0) { // 更新结束 break; } else if (parent-_bf 1 || parent-_bf -1) { // 继续往上更新 cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { // 不平衡了旋转处理 if (parent-_bf -2 cur-_bf -1) { RightRotate(parent); //右旋 } else if (parent-_bf 2 cur-_bf 1) { LeftRotate(parent); //左旋 } else if (parent-_bf -2 cur-_bf 1) { LRRotate(parent); //左右双旋 } else if (parent-_bf 2 cur-_bf -1) { RLRotate(parent); //右左双旋 } else { assert(false); } break; } else { assert(false); } } return true; } //右单旋 void RightRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentparent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parent parentparent-_left) { parentparent-_left subL; } else { parentparent-_right subL; } subL-_parent parentparent; } //更新平衡因子 subL-_bf 0; parent-_bf 0; } //左单旋 void LeftRotate(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentparent parent-_parent; subR-_left parent; parent-_parent subR; if (parentparent nullptr) { _root subR; subR-_parent nullptr; } else { if (parentparent-_left parent) { parentparent-_left subR; } else { parentparent-_right subR; } subR-_parent parentparent; } //更新平衡因子 parent-_bf 0; subR-_bf 0; } //左右双旋 void LRRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf;//记录subLR的平衡因子然后分三种情况讨论 LeftRotate(parent-_left);//左旋操作 RightRotate(parent);//右旋操作 //更新平衡因子 if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; //需要单独处理parent节点的平衡因子 } else if (bf 1) { subLR-_bf 0; subL-_bf -1; //需要单独处理subL节点的平衡因子 parent-_bf 0; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); //防御式编程 } } //右左双旋 void RLRotate(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; //记录subRL的平衡因子然后分三种情况讨论 RightRotate(parent-_right);//右旋操作 LeftRotate(parent);//左旋操作 //更新平衡因子 if (bf -1) { subRL-_bf 0; subR-_bf 1; //需要单独处理subR节点的平衡因子 parent-_bf 0; } else if (bf 1) { subRL-_bf 0; subR-_bf 0; parent-_bf -1; //需要单独处理parent节点的平衡因子 } else if (bf 0) { subRL-_bf 0; subR-_bf 0; parent-_bf 0; } else { assert(false); } } //中序遍历 void InOrder() { _InOrder(_root); cout endl; } //AVL树平衡检测 bool IsBalanceTree() { return _IsBalanceTree(_root); } //求树的高度 int Height() { return _Height(_root); } size_t Size() { return _Size(_root); } //查找 Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) cur cur-_right; else if (key cur-_kv.first) cur cur-_left; else return cur; } return nullptr; } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first : root-_kv.second endl; _InOrder(root-_right); } 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 _IsBalanceTree(Node* root) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } size_t _Size(Node* root) { if (root nullptr) return 0; return _Size(root-_left) _Size(root-_right) 1; } private: Node* _root nullptr; };
【数据结构】AVL树
发布时间：2026/7/10 11:03:07
目录1. 基本定义2. 核心特性3. AVL树节点的定义4. 自平衡机制旋转操作4.1 左单旋LeftRotate4.2 右单旋RightRotate4.3 左右双旋LRRotate4.4 右左双旋RLRotate5. AVL树的插入6. AVL树的删除了解7. AVL树的查找8. 获取树的高度9. AVL树的验证9.1 BST 性质验证9.2 AVL 平衡条件验证10. 总结1. 基本定义AVL 树Adelson-Velsky and Landis Tree是最早被发明的自平衡二叉搜索树由苏联数学家 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年提出。由于普通二叉搜索树在最坏情况下如顺序插入会退化为链表导致查找、插入删除操作的时间复杂度会从Olog n退化为On。AVL树通过严格控制树高确保所有操作的时间复杂度稳定在Olog n。2. 核心特性是二叉搜索树 (BST)满足 BST 性质左子树所有节点值 根节点值 右子树所有节点值。严格平衡条件每个节点的左右子树高度差 (平衡因子) 的绝对值不超过 1即平衡因子只能为 - 1、0 或 1。左右子树本身也必须是 AVL 树。平衡因子 (BF) 节点右子树高度 - 节点左子树高度3. AVL树节点的定义在二叉搜索树的基础上新增两个关键字段平衡因子_bf直接存储当前节点的平衡状态无需动态计算取值范围为-1, 0 ,1平衡状态若为2/-1则表示节点失衡需触发旋转操作。父节点指针parent用于插入或删除节点后从该节点向上回溯祖先节点逐个检查并更新它们的平衡因子。定义AVL树节点key/value 模型的AVL树templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; //平衡因子balance factor AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) //新节点为叶子平衡因子初始为0 {} };关于pair的使用在C中std::pair是标准模版库STL提供的一个轻量级模版类用于存储一对关联的数据两个元素它的核心作用是将两个值“捆绑”成一个单一的对象方便在函数返回、容器存储等场景中使用。std::pair定义在utility头文件中其模版声明如下template class T1, class T2 struct pair { T1 first; // 第一个元素 T2 second; // 第二个元素 // 构造函数等成员编译器自动生成 };pair的使用int main() { // 初始化一个 (int, string) 类型的pair pairint, string p1(10, hello); //直接构造 // 自动推导为 pairint, string auto p2 make_pair(10, world); //make_pair是一个辅助函数可自动推导类型简化初始化 pairstring, int p3{ age, 25 }; //列表初始化C11 pairint, int p4(1, 2); p4.first 100; // 访问并修改第一个元素 p4.second 200; // 访问并修改第二个元素 // 此时p4为 (100, 200) pairint, int p5; p5 p4; // 整体赋值p5 变为 (100, 200) //std::pair重载了常见的比较运算符、!、、、、比较规则为字典序 //1. 先比较first元素若不相等则结果由first决定; //2. 若first相等再比较second元素; if (p1 p2) //truefirst相等second hello world { cout p1 p2 endl; } if (p4 p5)//false { cout p4 p5 endl; } if (p4 p5)//true { cout p4 p5 endl; } return 0; }4.自平衡机制旋转操作4.1 左单旋LeftRotate左旋解决了右子树过高导致的失衡问题。它通过调整节点间的父子关系降低右子树高度使树重新满足平衡条件所有节点的平衡因子绝对值≤1。左旋的本质是将失衡节点的右子节点“提升”为新根节点原失衡节点成为新父节点的左子节点同时新父节点原来的左子树成为原失衡节点的右子树。插入操作左旋的触发条件该节点的平衡因子为2失衡节点。该节点右孩子的平衡因子为1。//左单旋 void LeftRotate(Node* parent) { Node* subR parent-_right; //失衡节点的右孩子(9) Node* subRL subR-_left; //失衡节点的右孩子的左孩子(6) parent-_right subRL; //6成为5的右子树 if (subRL)//判断subRL是否为空防止对空指针解引用6有可能不存在 subRL-_parent parent;//更改6的父指针为5 Node* parentparent parent-_parent;//5可能还有父亲节点记录5的父节点 subR-_left parent; //5成为9的左子树 parent-_parent subR;//更改5的父指针 if (parentparent nullptr)//如果5没有父节点那么9直接成为新根再将9的父指针置空 { _root subR; subR-_parent nullptr; } else //如果5存在父节点 { if (parentparent-_left parent) //5原来是pp的左子节点 { parentparent-_left subR; } else { parentparent-_right subR; //5原来是pp的右子节点 } subR-_parent parentparent; //更新9的父指针 } //更新平衡因子旋转后5和9的平衡因子均变为0 parent-_bf 0; subR-_bf 0; }4.2 右单旋RightRotate右旋用于解决左子树过高导致的失衡问题。通过调整节点间的父子关系降低左子树高度使树重新满足平衡条件所有节点的平衡因子绝对值≤1。右旋的本质是将失衡节点的左子节点 “提升” 为新的父节点原失衡节点则成为新父节点的右子节点同时新父节点原来的右子树将作为原失衡节点的左子树。插入操作右旋的触发条件该节点的平衡因子为-2失衡节点。该节点左孩子的平衡因子为-1。//右单旋 void RightRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentparent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parent parentparent-_left) { parentparent-_left subL; } else { parentparent-_right subL; } subL-_parent parentparent; } //更新平衡因子 subL-_bf 0; parent-_bf 0; }4.3 左右双旋LRRotate左右双旋是一种复合旋转操作用于处理左子树的右子树过高导致的特殊失衡场景。当单旋右旋无法直接修复失衡时需通过 “先左旋、后右旋” 的组合操作使树恢复平衡。左右双旋的触发条件该节点的平衡因子为-2失衡节点。失衡节点的左孩子平衡因子为1。左右双旋通过两步旋转将失衡调整为平衡状态第一步对失衡节点的左子节点进行左旋将“左—右”偏斜修正为“左—左”偏斜即一边高第二步对原失衡节点执行右旋修复“左—左”偏斜导致的失衡。情况1中由于对失衡节点的左孩子左旋操作将节点5和节点8的平衡因子都更新为0对失衡节点右旋操作将节点10和节点8的平衡因子更新为0通过图示我们发现计算出节点10的平衡因子并不为0而是1所以parent节点需要单独处理一下对于情况2需要单独处理subL节点情况3不需要单独处理不过为了保险起见可以在左右双旋代码中再次更新一边平衡因子。//左右双旋 void LRRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf;//记录subLR的平衡因子然后分三种情况讨论 LeftRotate(parent-_left);//左旋操作 RightRotate(parent);//右旋操作 //更新平衡因子 if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; //需要单独处理parent节点的平衡因子 } else if (bf 1) { subLR-_bf 0; subL-_bf -1; //需要单独处理subL节点的平衡因子 parent-_bf 0; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); //防御式编程 } }4.4 右左双旋RLRotate右左双旋复合旋转操作用于处理右子树的左子树过高导致的特殊失衡场景。当单旋左旋无法直接修复失衡时需通过 “先右旋、后左旋” 的组合操作使树恢复平衡。右左双旋的触发条件该节点的平衡因子为2失衡节点。失衡节点的右孩子平衡因子为-1。右左双旋通过两步旋转将失衡调整为平衡状态第一步对失衡节点的右子节点进行右旋将“右—左”偏斜修正为“右—右”偏斜即一边高第二步对原失衡节点执行左旋修复“右—右”偏斜导致的失衡。情况1中由于对失衡节点的右孩子右旋操作将节点9和节点6的平衡因子都更新为0对失衡节点左旋操作将节点4和节点6的平衡因子更新为0通过图示我们发现计算出节点9的平衡因子并不为0而是1所以subR节点需要单独处理一下对于情况2需要单独处理parent节点情况3不需要单独处理不过为了保险起见可以在左右双旋代码中再次更新一边平衡因子。//右左双旋 void RLRotate(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; //记录subRL的平衡因子然后分三种情况讨论 RightRotate(parent-_right);//右旋操作 LeftRotate(parent);//左旋操作 //更新平衡因子 if (bf -1) { subRL-_bf 0; subR-_bf 1; //需要单独处理subR节点的平衡因子 parent-_bf 0; } else if (bf 1) { subRL-_bf 0; subR-_bf 0; parent-_bf -1; //需要单独处理parent节点的平衡因子 } else if (bf 0) { subRL-_bf 0; subR-_bf 0; parent-_bf 0; } else { assert(false); } }5. AVL树的插入bool Insert(const pairK, V kv) { 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-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 更新平衡因⼦ while (parent) { if (cur parent-_left) parent-_bf--; else parent-_bf; if (parent-_bf 0) { // 更新结束 break; } else if (parent-_bf 1 || parent-_bf -1) { // 继续往上更新 cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { // 不平衡了旋转处理 if (parent-_bf -2 cur-_bf -1) { RightRotate(parent); //右旋 } else if (parent-_bf 2 cur-_bf 1) { LeftRotate(parent); //左旋 } else if (parent-_bf -2 cur-_bf 1) { LRRotate(parent); //左右双旋 } else if (parent-_bf 2 cur-_bf -1) { RLRotate(parent); //右左双旋 } else { assert(false); } break; } else { assert(false); } } return true; }6. AVL树的删除了解AVL树的插入操作最多只需一次失衡调整即可恢复整体平衡而删除操作与插入操作不同的是删除操作可能引发连锁的失衡传播可能不止调整一次失衡删除节点后需要依次对每个祖先节点进行检查。7. AVL树的查找Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) cur cur-_right; else if (key cur-_kv.first) cur cur-_left; else return cur; } return nullptr; }8. 获取树的高度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; }9. AVL树的验证AVL 树的验证是确保其同时满足二叉搜索树BST性质和AVL 平衡条件的过程。只有同时满足这两个条件才能称为合法的 AVL 树。9.1 BST 性质验证中序遍历有序void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); }9.2 AVL 平衡条件验证bool _IsBalanceTree(Node* root) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }优化方案在一次递归中同时计算高度和检查平衡通过返回值如pairbool,int同时携带 “是否平衡” 和 “子树高度”避免重复计算。优化后时间复杂度可降为O(n)示例如下// 返回值first为是否平衡second为子树高度 pairbool, int _IsBalanceTreeOptimized(Node* root) { if (root nullptr) { return {true, 0}; // 空树平衡高度0 } // 递归检查左子树 auto leftRes _IsBalanceTreeOptimized(root-_left); if (!leftRes.first) return {false, 0}; // 左子树失衡直接返回 // 递归检查右子树 auto rightRes _IsBalanceTreeOptimized(root-_right); if (!rightRes.first) return {false, 0}; // 右子树失衡直接返回 // 计算实际平衡因子 int diff rightRes.second - leftRes.first; // 检查结构平衡 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return {false, 0}; } // 检查平衡因子一致性 if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return {false, 0}; } // 返回当前子树高度1 左右子树最大高度 return {true, 1 max(leftRes.second, rightRes.second)}; }10. 总结总结AVL 树是一种自平衡二叉搜索树通过控制树高在 log₂n 级别使查找、插入、删除操作的时间复杂度稳定在 O (log n)。AVL树的实现删除操作这里不做研究templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; //平衡因子balance factor AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) // 新节点为叶子平衡因子初始为0 {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: //插入 bool Insert(const pairK, V kv) { 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-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 更新平衡因⼦ while (parent) { if (cur parent-_left) parent-_bf--; else parent-_bf; if (parent-_bf 0) { // 更新结束 break; } else if (parent-_bf 1 || parent-_bf -1) { // 继续往上更新 cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2) { // 不平衡了旋转处理 if (parent-_bf -2 cur-_bf -1) { RightRotate(parent); //右旋 } else if (parent-_bf 2 cur-_bf 1) { LeftRotate(parent); //左旋 } else if (parent-_bf -2 cur-_bf 1) { LRRotate(parent); //左右双旋 } else if (parent-_bf 2 cur-_bf -1) { RLRotate(parent); //右左双旋 } else { assert(false); } break; } else { assert(false); } } return true; } //右单旋 void RightRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentparent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parent parentparent-_left) { parentparent-_left subL; } else { parentparent-_right subL; } subL-_parent parentparent; } //更新平衡因子 subL-_bf 0; parent-_bf 0; } //左单旋 void LeftRotate(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentparent parent-_parent; subR-_left parent; parent-_parent subR; if (parentparent nullptr) { _root subR; subR-_parent nullptr; } else { if (parentparent-_left parent) { parentparent-_left subR; } else { parentparent-_right subR; } subR-_parent parentparent; } //更新平衡因子 parent-_bf 0; subR-_bf 0; } //左右双旋 void LRRotate(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf;//记录subLR的平衡因子然后分三种情况讨论 LeftRotate(parent-_left);//左旋操作 RightRotate(parent);//右旋操作 //更新平衡因子 if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; //需要单独处理parent节点的平衡因子 } else if (bf 1) { subLR-_bf 0; subL-_bf -1; //需要单独处理subL节点的平衡因子 parent-_bf 0; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); //防御式编程 } } //右左双旋 void RLRotate(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; //记录subRL的平衡因子然后分三种情况讨论 RightRotate(parent-_right);//右旋操作 LeftRotate(parent);//左旋操作 //更新平衡因子 if (bf -1) { subRL-_bf 0; subR-_bf 1; //需要单独处理subR节点的平衡因子 parent-_bf 0; } else if (bf 1) { subRL-_bf 0; subR-_bf 0; parent-_bf -1; //需要单独处理parent节点的平衡因子 } else if (bf 0) { subRL-_bf 0; subR-_bf 0; parent-_bf 0; } else { assert(false); } } //中序遍历 void InOrder() { _InOrder(_root); cout endl; } //AVL树平衡检测 bool IsBalanceTree() { return _IsBalanceTree(_root); } //求树的高度 int Height() { return _Height(_root); } size_t Size() { return _Size(_root); } //查找 Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) cur cur-_right; else if (key cur-_kv.first) cur cur-_left; else return cur; } return nullptr; } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first : root-_kv.second endl; _InOrder(root-_right); } 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 _IsBalanceTree(Node* root) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } size_t _Size(Node* root) { if (root nullptr) return 0; return _Size(root-_left) _Size(root-_right) 1; } private: Node* _root nullptr; };
