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

右旋 (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。解析：中序遍历降序意味着比较逻辑反转，此时最大元素位于最左侧，因此没有左子树。