C++ 实现 AVL 树：从结构到自平衡操作详解

2. 更新平衡因子

插入完成后，从新节点向上回溯，更新路径上所有祖先的平衡因子。如果某节点平衡因子变为 0，说明该子树高度未变，停止更新；若变为 ±1，继续向上；若变为 ±2，则必须旋转。

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 = cur->_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);
        else assert(false);
        break;
    }
}

旋转操作详解

当平衡因子绝对值为 2 时，根据失衡形态选择旋转策略。

右单旋 (RotateR)

适用于左子树较高的情况（LL 型）。将左子树提升为根，原根变为右子树。

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* ppNode = parent->_parent;

    parent->_left = subLR;
    if (subLR) subLR->_parent = parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (parent == _root) {
        subL->_parent = nullptr;
        _root = subL;
    } else {
        subL->_parent = ppNode;
        if (parent == ppNode->_right) ppNode->_right = subL;
        else ppNode->_left = subL;
    }
    parent->_bf = 0;
    subL->_bf = 0;
}

左单旋 (RotateL)

适用于右子树较高的情况（RR 型）。逻辑与右单旋对称。

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* ppNode = parent->_parent;

    parent->_right = subRL;
    if (subRL) subRL->_parent = parent;

    subR->_left = parent;
    parent->_parent = subR;

    if (parent == _root) {
        _root = subR;
        subR->_parent = nullptr;
    } else {
        subR->_parent = ppNode;
        if (parent == ppNode->_right) ppNode->_right = subR;
        else ppNode->_left = subR;
    }
    parent->_bf = 0;
    subR->_bf = 0;
}

双旋操作 (LR / RL)

当出现'左子树的右子树高'或'右子树的左子树高'时，需先对子节点进行反向旋转，再对当前节点进行正向旋转。

例如左右双旋（RotateLR）：先对左子树左旋，再对当前节点右旋。注意旋转后需根据中间节点原来的平衡因子调整三个节点的 _bf。

void RotateLR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

    RotateL(subL);
    RotateR(parent);

    if (bf == 1) {
        subLR->_bf = 0;
        subL->_bf = 0;
        parent->_bf = -1;
    } else if (bf == -1) {
        subLR->_bf = 0;
        subL->_bf = 1;
        parent->_bf = 0;
    } else {
        subL->_bf = 0;
        subLR->_bf = 0;
        parent->_bf = 0;
    }
}

其他基础操作

除了插入，AVL 树还需支持查找、计算高度和验证平衡性。

查找 (Find)

与普通 BST 一致，时间复杂度 O(log N)。

Node* Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) cur = cur->_right;
        else if (cur->_kv.first > key) cur = cur->_left;
        else return cur;
    }
    return nullptr;
}

验证平衡 (_IsBalanceTree)

递归检查每个节点的平衡因子是否与实际高度差一致，且绝对值不超过 1。

bool _IsBalanceTree(Node* root) {
    if (!root) return true;
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = leftHeight - rightHeight;

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

完整代码示例

以下是 AVLTree.h 的核心类定义及测试入口。

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

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

template <class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv) {
        if (!_root) {
            _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);
        cur->_parent = parent;
        if (parent->_kv.first < kv.first) parent->_right = cur;
        else parent->_left = cur;

        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 = cur->_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);
                else assert(false);
                break;
            }
        }
        return true;
    }

    void InOrder() { _InOrder(_root); cout << endl; }
    bool IsBalanceTree() { return _IsBalanceTree(_root); }
    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_kv.first < key) cur = cur->_right;
            else if (cur->_kv.first > key) cur = cur->_left;
            else return cur;
        }
        return nullptr;
    }
    int Height() { return _Height(_root); }
    int Size() { return _Size(_root); }

private:
    int _Size(Node* root) {
        if (!root) return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }
    int _Height(Node* root) {
        if (!root) return 0;
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }
    bool _IsBalanceTree(Node* root) {
        if (!root) return true;
        int leftH = _Height(root->_left);
        int rightH = _Height(root->_right);
        int diff = leftH - rightH;
        if (abs(diff) >= 2) {
            cout << root->_kv.first << " 高度差异常" << endl;
            return false;
        }
        if (root->_bf != diff) {
            cout << root->_kv.first << " 平衡因子异常" << endl;
            return false;
        }
        return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    }
    void _InOrder(Node* root) {
        if (!root) return;
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << " ";
        _InOrder(root->_right);
    }
    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        Node* ppNode = parent->_parent;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root) {
            subL->_parent = nullptr;
            _root = subL;
        } else {
            subL->_parent = ppNode;
            if (parent == ppNode->_right) ppNode->_right = subL;
            else ppNode->_left = subL;
        }
        parent->_bf = 0;
        subL->_bf = 0;
    }
    void RotateL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* ppNode = parent->_parent;
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;
        subR->_left = parent;
        parent->_parent = subR;
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            subR->_parent = ppNode;
            if (parent == ppNode->_right) ppNode->_right = subR;
            else ppNode->_left = subR;
        }
        parent->_bf = 0;
        subR->_bf = 0;
    }
    void RotateLR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        RotateL(subL);
        RotateR(parent);
        if (bf == 1) {
            subLR->_bf = 0; subL->_bf = 0; parent->_bf = -1;
        } else if (bf == -1) {
            subLR->_bf = 0; subL->_bf = 1; parent->_bf = 0;
        } else {
            subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0;
        }
    }
    void RotateRL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(subR);
        RotateL(parent);
        if (bf == 0) {
            parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0;
        } else if (bf == 1) {
            subRL->_bf = 0; parent->_bf = 0; subR->_bf = -1;
        } else if (bf == -1) {
            subRL->_bf = 0; parent->_bf = 1; subR->_bf = 0;
        }
    }
    Node* _root = nullptr;
};

// 测试用例
void TestAVLTree1() {
    AVLTree<int, int> t;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        t.Insert({ e, e });
        cout << "Insert: " << e << " -> Balance: " << t.IsBalanceTree() << endl;
    }
    t.InOrder();
    cout << "Final Balance: " << t.IsBalanceTree() << endl;
}

void TestAVLTree2() {
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);
    srand((unsigned int)time(0));
    for (int i = 0; i < N; i++) v.push_back(rand() + i);

    size_t begin = clock();
    AVLTree<int, int> t;
    for (auto e : v) t.Insert(make_pair(e, e));
    size_t end = clock();

    cout << "Insert Time: " << end - begin << endl;
    cout << "Height: " << t.Height() << endl;
    cout << "Size: " << t.Size() << endl;
    cout << "Is Balanced: " << t.IsBalanceTree() << endl;
}

int main() {
    TestAVLTree1();
    TestAVLTree2();
    return 0;
}

总结

AVL 树通过严格的平衡因子控制，确保了在最坏情况下也能保持 O(log N) 的性能。虽然旋转操作增加了插入的常数开销，但在频繁查询的场景下，这种代价是值得的。理解旋转背后的指针变化逻辑，是掌握自平衡树的关键。