2.5-数据结构：AVL树

2.5-AVL树

🌲 定义与性质

AVL树（Adelson-Velsky and Landis Tree）是最早发明的自平衡二叉搜索树，通过维护平衡因子确保树的高度始终为 O(log N)。其核心特性为：

平衡因子：任意节点的左右子树高度差绝对值不超过 1
旋转操作：通过四种旋转操作（左旋、右旋、左右旋、右左旋）动态调整平衡

⚖️ 平衡因子

每个节点的平衡因子计算公式：

平衡因子 = 右子树高度 - 左子树高度

平衡因子范围：[-1, 0, 1]

🔄 旋转操作类型

旋转类型	触发条件	示意图
左旋	右子树右节点导致失衡	→ 右侧超重拉平
右旋	左子树左节点导致失衡	← 左侧超重拉平
左右旋	左子树右节点导致失衡	↙ 先左旋再右旋
右左旋	右子树左节点导致失衡	↘ 先右旋再左旋

🖥️ 核心代码实现（C++）

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;// 定义AVL树节点结构
template<class K, class V>
struct AVLTreeNode {AVLTreeNode<K, V>* _left;  // 左子节点指针AVLTreeNode<K, V>* _right; // 右子节点指针AVLTreeNode<K, V>* _parent; // 父节点指针pair<K, V> _kv;  // 键值对int _bf; // balance factor 平衡因子// 构造函数，初始化节点AVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};// 定义AVL树类
template<class K, class V>
class AVLTree {typedef AVLTreeNode<K, V> Node;
public:// 插入键值对bool Insert(const pair<K, 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->_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;} else if (parent->_kv.first < kv.first) {parent->_right = cur;}cur->_parent = parent;// 更新平衡因子while (parent) {if (cur == parent->_right) {parent->_bf++;} else {parent->_bf--;}if (parent->_bf == 1 || parent->_bf == -1) {parent = parent->_parent;cur = cur->_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) {RotateLR(parent); // 左右双旋} else if (parent->_bf == 2 && cur->_bf == -1) {RotateRL(parent); // 右左双旋}break;} else {assert(false);}}return true;}// 中序遍历AVL树void InOrder() {_InOrder(_root);cout << endl;}// 递归中序遍历辅助函数void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}// 判断AVL树是否平衡bool IsBalance() {return _IsBalance(_root);}private:Node* _root = nullptr;// 左单旋void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;// 处理 subRL 与 parent 的连接parent->_right = subRL;if (subRL) {subRL->_parent = parent;}// 保存原父节点的父节点Node* pparent = parent->_parent;// 处理 subR 与 parent 的连接subR->_left = parent;parent->_parent = subR;// 处理 subR 与 pparent 的连接if (pparent == nullptr) {_root = subR;subR->_parent = nullptr;} else {if (pparent->_left == parent) {pparent->_left = subR;} else {pparent->_right = subR;}subR->_parent = pparent;}// 更新平衡因子parent->_bf = subR->_bf = 0;}// 右单旋void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;// 处理 subLR 与 parent 的连接parent->_left = subLR;if (subLR) {subLR->_parent = parent;}// 保存原父节点的父节点Node* pparent = parent->_parent;// 处理 subL 与 parent 的连接subL->_right = parent;parent->_parent = subL;// 处理 subL 与 pparent 的连接if (pparent == nullptr) {_root = subL;subL->_parent = nullptr;} else {if (pparent->_left == parent) {pparent->_left = subL;} else {pparent->_right = subL;}subL->_parent = pparent;}// 更新平衡因子parent->_bf = subL->_bf = 0;}// 左右双旋void RotateLR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;RotateL(parent->_left);RotateR(parent);int bf = subLR->_bf;// 根据subLR的平衡因子更新各节点平衡因子if (bf == 1) {parent->_bf = -1;subLR->_bf = 0;subL->_bf = -1;} else if (bf == -1) {parent->_bf = 1;subLR->_bf = 0;subL->_bf = -1;} else if (bf == 0) {parent->_bf = 0;subLR->_bf = 0;subL->_bf = 0;} else {assert(false);}}// 右左双旋void RotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;RotateR(parent->_right);RotateL(parent);int bf = subRL->_bf;// 根据subRL的平衡因子更新各节点平衡因子if (bf == 1) {parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;} else if (bf == -1) {parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;} else if (bf == 0) {parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;} else {assert(false);}}// 计算树的高度int _Height(Node* root) {if(root == nullptr) { return 0; }int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}// 判断以root为根的子树是否平衡bool _IsBalance(Node* root) {if (root == nullptr) { return true; }return abs(_Height(root->_left) - _Height(root->_right)) < 2&& _IsBalance(root->_left) && _IsBalance(root->_right);}
};// 测试AVL树的插入和平衡性
void test_AVLTree() {int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTree<int, int> t1;for (auto e : a) {t1.Insert(make_pair(e, e));}t1.InOrder();cout << t1.IsBalance() << endl;
}