AVL树是一种自平衡的二叉搜索树（BST）。它最早由G.M. Adelson-Velsky和E.M. Landis在1962年提出。AVL树的特点是任何节点的两个子树的高度最多相差1，这确保了树的平衡性，从而保证了树的操作（如查找、插入和删除）的时间复杂度为O(log n)。
什么是AVL树？
AVL树是一种特殊的二叉搜索树，其中每个节点的左子树和右子树的高度差（称为平衡因子）最多为1。如果任何时候这个条件被违反，将会通过一系列的旋转操作来重新平衡树。
AVL树的特性
- 二叉搜索树：对于任何节点，左子树的所有节点的值都小于该节点，右子树的所有节点的值都大于该节点。
- 自平衡：任何节点的两个子树的高度最多相差1。
- 时间复杂度：查找、插入和删除操作的最坏情况时间复杂度为O(log n)。
AVL树的实现
AVL树的结构
template<class K, class V>
struct AVLTreeNode
{// 需要parent指针，后续更新平衡因⼦可以看到pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://...
private:Node* _root = nullptr;
};AVL树的插入操作
插入操作与普通的二叉搜索树类似，但插入后需要检查树是否平衡。如果不平衡，需要通过旋转操作来恢复平衡。
- 插入节点：按照二叉搜索树的规则插入新节点。
- 更新高度：从插入点向上更新每个节点的高度。
- 检查平衡：从插入点向上检查每个节点的平衡因子。
- 执行旋转：如果发现不平衡，执行相应的旋转操作。
平衡因子更新
更新原则：
• 平衡因⼦ = 右⼦树⾼度 - 左⼦树⾼度
• 只有⼦树⾼度变化才会影响当前结点平衡因⼦
• 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦--
• parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
更新停止条件：
更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为 - 1->0 或者 1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束。
更新后parent的平衡因⼦等于1 或 - 1，更新前更新中parent的平衡因⼦变化为0->1 或者 0-> - 1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上更新。更新后parent的平衡因⼦等于2 或 - 2，更新前更新中parent的平衡因⼦变化为1->2 或者 - 1-> - 2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。
插入结点及更新平衡因子的代码实现
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->_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->_right){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){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}AVL树的旋转操作
旋转的原则：
1.保持搜索树的规则
2.让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度
为了保持树的平衡，AVL树使用四种基本的旋转操作：
右旋（Right Rotation）：用于处理左左（LL）情况，即左子树的左子树插入或删除导致不平衡。
在a⼦树中插⼊⼀个新结点，导致a⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平衡因⼦从-1变成-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要往右边旋转，控制两棵树的平衡。
旋转核⼼步骤，因为5 < b⼦树的值 < 10，将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 需要注意除了要修改孩⼦指针指向，还要修改⽗亲parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;// parent有可能是整棵树的根，也可能是局部的⼦树// 如果是整棵树的根，要修改_root// 如果是局部的指针要跟上⼀层链接if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}subL->_bf = 0;parent->_bf = 0;
}左旋（Left Rotation）：用于处理右右（RR）情况，即右子树的右子树插入或删除导致不平衡。
跟右旋类似
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parent == ppNode->_left){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;
}
左右旋（Left-Right Rotation）：用于处理左右（LR）情况，即左子树的右子树插入或删除导致不平衡。
场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1并为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。场景3：h == 0时，a/b/c都是空树，不断更新5->10平衡因⼦，引发旋转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0){subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else{assert(false);}
}
右左旋（Right-Left Rotation）：用于处理右左（RL）情况，即右子树的左子树插入或删除导致不平衡。
与左右旋类似
void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}
AVL树的查找
⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)
Node* Find(const K& key)
{Node* cur = _root;while(cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}AVL树平衡检测
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}else if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(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;
}// 测试代码
void TestAVLTree1()
{AVLTree<int, int> t;// 常规的测试用例//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });cout << "Insert:" << e << "->";cout << t.IsBalanceTree() << endl;}t.InOrder();cout << t.IsBalanceTree() << endl;
}
void TestAVLTree2()
{const int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << t.IsBalanceTree() << endl;cout << "Insert:" << end2 - begin2 << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*/// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}
