引言
之前讲解了二叉搜索树，最优情况下它具有非常好的搜索性能，但是在极端场景下，它可能退化为单支树，可以形象地称为歪脖子树~
这样的话，它搜索的时间复杂度会从O(log2N)退化为O(N2)，完全丧失了其优良的搜索性能。那么AVL树就可以登场了，它就是为解决这类问题而生的！
一、AVL树的概念
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL树，AVL树满足两条性质：
- 它的左右子树都是AVL树
- 任意结点的左右子树高度差的绝对值不超过1
这样通过控制子树高度差，让AVL树几乎完美接近于平衡，便不会出现单支树的情况，保证了优良的搜索性能，因此AVL树又称为高度平衡二叉搜索树。
二、AVL树的模拟实现
2.1 结点
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) {} };
细节：
- 使用三叉链，增加了指向parent的指针
- 使用KV模型，数据存储键值对pair
- 结点存储平衡因子，用来记录左右子树高度差
注：平衡因子计算高度差，是 右子树高度 - 左子树高度
2.2 成员变量
template<class K, class V> class AVLTree { protected: typedef AVLTreeNode<K, V> Node; public: protected: Node* _root = nullptr; };
2.3 插入
因为AVL树也是二叉搜索树，所以默认成员函数和遍历与之前写的没什么不同，这里重点讲解AVL树的插入。
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 == 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); } else { assert(false); } break; } else { assert(false); } } return true; }
思路：
- 以二叉搜索树的方式正常插入
- 讨论平衡因子，以及调整结构
这里的重点在于如何讨论和调整平衡因子(bf)。
- 首先，插入cur结点，调整parent结点的bf，左减右加
- 讨论parent的bf
- bf为0
- bf为1或-1
- bf为2或-2
bf为0时：
分析：此时没有增加高度，而是补上缺口，整棵树是平衡的，直接break即可
bf为1或-1时：
分析：此时增加了局部子树的高度，不确定有没有影响整体的高度差，所以要继续向上调整
parent = parent->_parent; cur = cur->_parent;
bf为2或-2时：
此时bf已经超出平衡限制区间，需要进行结构调整，我们称之为旋转。
2.4 旋转
旋转分为两大类：单旋和双旋。而单旋分为左单旋和右单旋，双旋分为左右旋和右左旋。
2.4.1 左单旋
场景：右部外侧插入
过程：
- parent接过subR的左子树subRL
- subR左边再链接parent
void RotateL(Node* parent)//左单旋 { Node* grandparent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } subR->_left = parent; parent->_parent = subR; if (grandparent) { if (grandparent->_right == parent) { grandparent->_right = subR; } else { grandparent->_left = subR; } } else { _root = subR; } subR->_parent = grandparent; parent->_bf = subR->_bf = 0; }
细节：
- 大体是三步链接，注意双向链接
- 注意判空（subRL，grandparent）
- 如果判空，注意_root的传递
- 最后调整平衡因子_bf
2.4.2 右单旋
场景：左部外侧插入
过程：
- parent接过subL的右子树subLR
- subL右边再链接parent
void RotateR(Node* parent)//右单旋 { Node* grandparent = parent->_parent; Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } subL->_right = parent; parent->_parent = subL; if (grandparent) { if (grandparent->_right == parent) { grandparent->_right = subL; } else { grandparent->_left = subL; } } else { _root = subL; } subL->_parent = grandparent; parent->_bf = subL->_bf = 0; }
细节：同左单旋
2.4.3 左右旋
场景：左部内侧插入
过程：
- 先对subL进行左单旋
- 再对parent进行右单旋
void RotateLR(Node* parent)//左右旋 { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); if (bf == 1) { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else if (bf == -1) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 0) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else { assert(false); } }
细节：
- 这里旋转直接复用前面单旋的代码
- 主要的重点，在于平衡因子bf的讨论
- bf为1，在subLR的右侧插入
- bf为-1，在subLR的左侧插入
- bf为0，插入subLR（之前为空）
2.4.4 右左旋
场景：右部内侧插入
过程：
- 先对subR进行右单旋
- 再对parent进行左单旋
void RotateRL(Node* parent)//右左旋 { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); 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); } }
细节：同左右旋
综上所述，旋转的目的：保证平衡，同时降低树的高度。
三、AVL树的验证
我们主要验证左右子树高度是否平衡，即高度差是否小于等于1
bool IsBalance() { return _IsBalance(_root); } 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; } bool _IsBalance(Node* root) { if (root == nullptr) { return true; } int leftH = Height(root->_left); int rightH = Height(root->_right); if (rightH - leftH != root->_bf) { cout << root->_kv.first << "节点平衡因子异常" << endl; return false; } return abs(rightH - leftH) <= 1 && _IsBalance(root->_left) && _IsBalance(root->_right); }
细节：
- 为了方便计算高度，写一个Height函数
- 在子函数递归中，计算高度差是否小于等于1
- 与此同时，还要检查平衡因子是否正常
四、AVL树的性能
4.1 优势
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 l o g 2 ( N ) log_2 (N) log2(N)。
4.2 缺陷
但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
4.3 适用场景
因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
真诚点赞，手有余香
