深入理解 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(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->_left)
            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) {
            // 不平衡了，需要旋转处理
            break;
        } else {
            assert(false);
        }
    }
    return true;
}

注意看这段循环，一旦某个节点的平衡因子变成 0，说明这棵树的高度没有增加，上面的祖先节点不需要再更新了，直接跳出循环即可。如果变成了 ±2，说明失衡，这时候就要准备进行旋转操作了。

旋转调整策略

当检测到失衡时，我们需要通过旋转来恢复平衡。旋转必须遵守两个基本原则：

1. 保持二叉搜索树的规则（左小右大）。
2. 让旋转后的树从不满足平衡条件变为平衡，同时尽可能降低树的高度。

通常分为四种情况：左单旋、右单旋、左右双旋、右左双旋。具体选择哪种旋转，取决于新插入节点相对于失衡节点的位置关系。