AVL 树核心原理与 C++ 模拟实现详解

AVL 树概述

在算法实践中，二叉搜索树（BST）常因极端数据退化导致性能下降。当插入有序序列时，树结构会退化成链表，查询效率从理论上的 $O( log n)$ 跌至 $O(n)$。AVL 树作为一种严格平衡的二叉搜索树，通过引入平衡因子机制，确保任意节点的左右子树高度差不超过 1，从而维持整体结构的平衡。

核心概念

AVL 树是空树或满足以下性质的二叉搜索树：

1. 左右子树均为 AVL 树。
2. 每个节点的平衡因子（左右子树高度差）绝对值不超过 1。

其增删查改的时间复杂度均稳定在 $O( log n)$。

节点结构与插入逻辑

实现前需定义包含平衡因子的节点结构。插入新节点后，需沿路径向上更新祖先节点的平衡因子。若某节点平衡因子变为 2 或 -2，则触发旋转操作以恢复平衡。

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

插入时的平衡因子更新策略如下：

• 新节点在左子树，父节点平衡因子减 1。
• 新节点在右子树，父节点平衡因子加 1。
• 若更新后平衡因子为 0，说明该子树高度未变，停止更新。
• 若为 ±1，继续向上传播。
• 若为 ±2，当前子树失衡，需执行旋转。

旋转操作详解

旋转是修复失衡的核心手段，分为单旋和双旋。旋转过程中必须保持二叉搜索树的性质，同时修正相关节点的平衡因子。

左旋 (Right Rotation)

适用于'右右'失衡情况。将根节点的左孩子提升为新根，原根节点变为左孩子的右孩子。

void RotateR(Node* parent) {
    Node* cur = parent->_left;
    Node* curright = cur->_right;
    
    parent->_left = curright;
    if (curright) curright->_parent = parent;
    
    Node* ppnode = parent->_parent;
    cur->_right = parent;
    parent->_parent = cur;
    
    if (ppnode == nullptr) {
        _root = cur;
        cur->_parent = nullptr;
    } else {
        if (ppnode->_left == parent) ppnode->_left = cur;
        else ppnode->_right = cur;
        cur->_parent = ppnode;
    }
    
    parent->_bf = cur->_bf = 0;
}

右旋 (Left Rotation)

适用于'左左'失衡情况。将根节点的右孩子提升为新根，原根节点变为右孩子的左孩子。

void RotateL(Node* parent) {
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
    
    parent->_right = curleft;
    if (curleft) curleft->_parent = parent;
    
    Node* ppnode = parent->_parent;
    cur->_left = parent;
    parent->_parent = cur;
    
    if (parent == _root) {
        _root = cur;
        cur->_parent = nullptr;
    } else {
        if (ppnode->_left == parent) ppnode->_left = cur;
        else ppnode->_right = cur;
        cur->_parent = ppnode;
    }
    
    parent->_bf = cur->_bf = 0;
}

双旋 (LR & RL)

当失衡形态为折线型（如'左右'或'右左'）时，需先对子节点进行反向旋转，再对父节点进行主旋转。双旋后的平衡因子修正较为复杂，需根据插入位置判断。

void RotateRL(Node* parent) {
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
    int bf = curleft->_bf;
    
    RotateR(parent->_right);
    RotateL(parent);
    
    if (bf == 0) {
        cur->_bf = 0; curleft->_bf = 0; parent->_bf = 0;
    } else if (bf == 1) {
        cur->_bf = 0; curleft->_bf = 0; parent->_bf = -1;
    } else if (bf == -1) {
        cur->_bf = 1; curleft->_bf = 0; parent->_bf = 0;
    }
}

验证与练习

验证 AVL 树是否正确，不能仅依赖平衡因子字段（可能更新出错），应通过计算实际高度差来校验。中序遍历有序只能证明是二叉搜索树，无法证明平衡性。

验证代码示例：

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 (abs(rightH - leftH) != abs(root->_bf)) return false;
    return abs(rightH - leftH) < 2 && IsBalance(root->_left) && IsBalance(root->_right);
}

思考题

现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是？ A. 根结点的度一定为 2 B. 树中最小元素一定是叶结点 C. 最后插入的元素一定是叶结点 D. 树中最大元素一定是无左子树

答案：D。解析：中序遍历降序意味着比较逻辑反转，此时最大元素位于最左侧，因此没有左子树。