C++ 实现 AVL 平衡二叉搜索树详解

注意：AVL 树不支持重复元素，插入已存在的键值对应直接返回失败。

bool Insert(const pair<T, K>& x) {
    if (root == nullptr) {
        root = new Node(x);
        return true;
    }

    Node* cur = root;
    Node* parent = nullptr;

    while (cur) {
        if (cur->_val.first < x.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_val.first > x.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false; // 不允许重复
        }
    }

    cur = new Node(x);
    if (parent->_val.first > x.first) {
        parent->_left = cur;
    } else {
        parent->_right = cur;
    }
    cur->_parent = parent;

    // 更新平衡因子
    while (parent) {
        if (parent->_left == cur) {
            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 && cur->_bf == -1) {
                RotateR(parent);
            } else if (parent->_bf == 2 && cur->_bf == 1) {
                RotateL(parent);
            } else if (parent->_bf == -2 && cur->_bf == 1) {
                RotateLR(parent);
            } else if (parent->_bf == 2 && cur->_bf == -1) {
                RotateRL(parent);
            }
            break;
        }
    }
    return true;
}

2. 旋转策略

当平衡因子超出 [-1, 1] 范围时，必须通过旋转恢复平衡。旋转需遵循两个原则：保持 BST 性质，降低树高。

右单旋：适用于左子树过高且左孩子的平衡因子为 -1 的情况。

void RotateR(Node* Parent) {
    Node* SubL = Parent->_left;
    Node* SubLR = SubL->_right;

    if (SubLR != nullptr) {
        SubLR->_parent = Parent;
    }

    Node* ppNode = Parent->_parent;
    Parent->_left = SubLR;
    Parent->_parent = SubL;
    SubL->_right = Parent;

    if (ppNode != nullptr) {
        if (ppNode->_left == Parent) {
            ppNode->_left = SubL;
        } else {
            ppNode->_right = SubL;
        }
        SubL->_parent = ppNode;
    } else {
        root = SubL;
        SubL->_parent = nullptr;
    }

    Parent->_bf = 0;
    SubL->_bf = 0;
}

左单旋：适用于右子树过高且右孩子的平衡因子为 1 的情况。

void RotateL(Node* Parent) {
    Node* SubR = Parent->_right;
    Node* SubRL = SubR->_left;

    if (SubRL != nullptr) {
        SubRL->_parent = Parent;
    }

    Node* ppNode = Parent->_parent;
    Parent->_right = SubRL;
    Parent->_parent = SubR;
    SubR->_left = Parent;

    if (ppNode != nullptr) {
        if (ppNode->_left == Parent) {
            ppNode->_left = SubR;
        } else {
            ppNode->_right = SubR;
        }
        SubR->_parent = ppNode;
    } else {
        root = SubR;
        SubR->_parent = nullptr;
    }

    SubR->_bf = 0;
    Parent->_bf = 0;
}

左右双旋：先左旋左孩子，再右旋当前节点。适用于左子树较高但左孩子的右子树更高的情况。

void RotateLR(Node* Parent) {
    Node* SubL = Parent->_left;
    Node* SubLR = SubL->_right;
    int bf = SubLR->_bf;

    RotateL(SubL);
    RotateR(Parent);

    if (bf == 0) {
        SubL->_bf = 0; SubLR->_bf = 0; Parent->_bf = 0;
    } else if (bf == 1) {
        SubL->_bf = -1; Parent->_bf = 0; SubLR->_bf = 0;
    } else if (bf == -1) {
        SubL->_bf = 0; SubLR->_bf = 0; Parent->_bf = 1;
    } else {
        assert(false);
    }
}

右左双旋：先右旋右孩子，再左旋当前节点。适用于右子树较高但右孩子的左子树更高的情况。

void RotateRL(Node* Parent) {
    Node* SubR = Parent->_right;
    Node* SubRL = SubR->_left;
    int bf = SubRL->_bf;

    RotateR(SubR);
    RotateL(Parent);

    if (bf == 0) {
        SubR->_bf = 0; SubRL->_bf = 0; Parent->_bf = 0;
    } else if (bf == 1) {
        SubR->_bf = 0; SubRL->_bf = 0; Parent->_bf = -1;
    } else if (bf == -1) {
        SubRL->_bf = 0; Parent->_bf = 0; SubR->_bf = 1;
    } else {
        assert(false);
    }
}

查找与验证

查找逻辑与普通 BST 一致，时间复杂度 O(logN)。

Node* Find(const T& x) {
    if (root == nullptr) return nullptr;
    Node* cur = root;
    while (cur) {
        if (cur->_val.first < x) {
            cur = cur->_right;
        } else if (cur->_val.first > x) {
            cur = cur->_left;
        } else {
            return cur;
        }
    }
    return nullptr;
}

为了验证实现是否正确，我们可以编写检测程序，检查每棵子树是否满足平衡条件以及平衡因子是否与计算高度一致。

bool IsBalanceTree() {
    return _IsBalanceTree(root);
}

int _Height(Node* cur) {
    if (cur == nullptr) return 0;
    int Left = _Height(cur->_left);
    int Right = _Height(cur->_right);
    return Left > Right ? Left + 1 : Right + 1;
}

bool _IsBalanceTree(Node* root) {
    if (root == nullptr) return true;
    int HLeft = _Height(root->_left);
    int HRight = _Height(root->_right);
    int diff = HRight - HLeft;

    if (abs(diff) >= 2) {
        cout << root->_val.first << " 高度差异常" << endl;
        return false;
    }
    if (root->_bf != diff) {
        cout << root->_val.first << " 平衡因子异常" << endl;
        return false;
    }
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

通过大量随机数据的插入测试，可以观察到树的高度始终维持在 logN 附近，验证了 AVL 树的高效性。例如插入 10 万条数据，查找操作仅需约 20 次比较。

至此，AVL 树的基本插入与平衡维护逻辑已完成。理解旋转的时机与细节是掌握 AVL 树的关键，建议结合图示多动手模拟几次插入过程。