C++ AVL 树：概念、结构与旋转实现

二叉搜索树存在自身缺陷，若插入元素有序或接近有序，会退化成单支树，时间复杂度降为 O(N)。因此 map、set 等关联式容器的底层结构采用平衡树来实现。

1.AVL 树的概念

我们已经从多种树型结构走到现在，每一次变化都是为了提高搜索的效率，即时间复杂度。

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下，因此发明了 AVL 树。

那么什么是 AVL 树呢？

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1 (需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵 AVL 树或者是空树，应该是具有以下性质的二叉搜索树：

• 它的左右子树都是 AVL 树
• 左右子树高度之差 (简称平衡因子) 的绝对值不超过 1(-1/0/1)

二叉搜索树在理想情况下时间复杂度与二叉平衡搜索树相同，均为 O(log n)，但在极端情况下二叉平衡搜索树优于二叉搜索树，因为二叉平衡搜索树会自己调整平衡（后面会详细解释）。

为什么是严格的绝对值为 1，不是 0 或者更大的数字？

若要求高度差为 0，即严格平衡，树的结构会过于 rigid（僵化）。每次插入或删除节点都可能需要大量调整操作，导致性能下降。允许高度差为 1，在保持较好平衡性的同时，减少了不必要的调整 若允许高度差为 2，树的平衡性会明显下降，可能出现一侧子树比另一侧高很多的情况，导致查找等操作的时间复杂度增加 所以平衡因子为 1 是最合适的

2.AVL 树的结构

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){}
};