深入理解 AVL 树：平衡因子与自旋调整

AVL 树概述

AVL 树本质上是一棵空树，或者满足以下条件的二叉搜索树：其左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。

这种结构让 AVL 树的节点分布接近完全二叉树，高度被控制在 logN 级别。这意味着增删查改的效率都能维持在 O(logN)，相比普通的二叉搜索树，它在极端情况下（如有序输入）不会退化成链表，稳定性有了本质提升。

平衡因子详解

为了判断树是否平衡，我们引入了平衡因子。结点的平衡因子定义为右子树高度减去左子树高度。在 AVL 树中，任何结点的平衡因子只能是 0、1 或 -1。

虽然 AVL 树的核心是高度差限制，但引入平衡因子就像装了一个'风向标'，让我们能更方便地观察和控制树的平衡状态。你可能会问，为什么要求高度差不超过 1，而不是必须为 0？因为对于某些结点数量（比如 2 个或 4 个），很难做到所有层都完美对齐，允许 ±1 的偏差能在保持高效的同时降低实现的复杂度。

代码实现

节点结构设计

为了实现上述逻辑，我们需要在普通 BST 节点的基础上增加父指针和平衡因子字段。这里特意加了 _parent 指针，因为在插入过程中，我们需要从下往上回溯更新平衡因子，没有父指针会很麻烦。

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; // balance factor

    AVLTreeNode(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;
};

插入与平衡维护

插入过程和普通二叉搜索树类似，找到位置挂上即可。关键在于插入后如何维护平衡。

bool Insert( pair<K, V>& kv) {
     (_root == ) {
        _root =  (kv);
         ;
    }

    Node* parent = ;
    Node* cur = _root;
     (cur) {
         (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        }   (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        }  {
             ; 
        }
    }

    cur =  (kv);
     (parent->_kv.first < kv.first) {
        parent->_right = cur;
    }  {
        parent->_left = cur;
    }
    cur->_parent = parent;

    
     (parent) {
         (cur == parent->_left)
            parent->_bf--;
        
            parent->_bf++;

         (parent->_bf == ) {
            
            ;
        }   (parent->_bf ==  || parent->_bf == ) {
            
            cur = parent;
            parent = parent->_parent;
        }   (parent->_bf ==  || parent->_bf == ) {
            
            ;
        }  {
            ();
        }
    }
     ;
}