C++手写AVL平衡树：旋转、平衡因子与性能实测

插入

插入本身和二叉搜索树一样，先找到位置，新建节点并链接，然后向上调整平衡因子。

bool insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    Node* cur = _root;
    Node* prev = nullptr;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            prev = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            prev = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    cur = new Node(kv);
    if (prev->_kv.first > kv.first)
        prev->_left = cur;
    else
        prev->_right = cur;
    cur->_parent = prev;
    // 向上更新平衡因子...
}

向上更新的逻辑写在 while 循环里。prev 是当前节点的父亲，cur 是刚插入的节点。

• 插入左边：prev->_bf--
• 插入右边：prev->_bf++

然后根据 prev->_bf 分三种情况：

1. 0：原本左右不平衡，现在平衡了，高度没变，直接结束。
2. ±1：原本平衡，现在一边高，子树高度增加，需要继续向上更新（cur = prev; prev = cur->_parent;）。
3. ±2：已经违反平衡条件，必须旋转处理，旋转后结束。

while (prev != nullptr) {
    if (cur == prev->_left) {
        prev->_bf--;
    } else {
        prev->_bf++;
    }
    if (prev->_bf == 0) {
        break;
    } else if (prev->_bf == 1 || prev->_bf == -1) {
        cur = prev;
        prev = cur->_parent;
    } else if (prev->_bf == 2 || prev->_bf == -2) {
        // 旋转
        break;
    } else {
        assert(false);
    }
}

四种旋转

当 prev->_bf == ±2 时，根据 prev 和 cur 的平衡因子符号决定用哪种旋转。

右单旋

适合情况：prev->_bf == -2 && cur->_bf == -1（左子树左边高）。

一般情况示意：

subL 成为新根，parent 变成 subL 的右子树，subLR 成为 parent 的左子树。平衡因子都置 0。

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

    Node* pparent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;

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

左单旋

对称情况：prev->_bf == 2 && cur->_bf == 1（右子树右边高）。

subR 成为新根，parent 变成 subR 的左子树，subRL 成为 parent 的右子树。

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

    Node* pparent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;

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

左右双旋

当 prev->_bf == -2 && cur->_bf == 1 时，左子树的右边高，需要先对 subL 左旋，再对 parent 右旋。

旋转后平衡因子的更新要看 subLR 原来的 _bf：

• subLR->_bf == -1：新节点插在 subLR 的左子树，最终 parent->_bf = 1，subL->_bf = 0。
• subLR->_bf == 1：新节点插在 subLR 的右子树，最终 parent->_bf = 0，subL->_bf = -1。
• subLR->_bf == 0：subLR 本身就是新插入的节点，三个平衡因子都置 0。

void RotateLR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    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 if (bf == 0) {
        subLR->_bf = 0;
        subL->_bf = 0;
        parent->_bf = 0;
    } else {
        assert(false);
    }
}

右左双旋

与上面镜像：prev->_bf == 2 && cur->_bf == -1，先右旋 subR，再左旋 parent。

void RotateRL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    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;
    } else if (bf == 0) {
        subRL->_bf = 0;
        parent->_bf = 0;
        subR->_bf = 0;
    } else {
        assert(false);
    }
}

四种旋转补进插入逻辑后，插入函数就完整了：

// 在更新平衡因子循环中，遇到 ±2 时：
if (prev->_bf == -2 && cur->_bf == -1) {
    RotateR(prev);
} else if (prev->_bf == 2 && cur->_bf == 1) {
    RotateL(prev);
} else if (prev->_bf == -2 && cur->_bf == 1) {
    RotateLR(prev);
} else if (prev->_bf == 2 && cur->_bf == -1) {
    RotateRL(prev);
} else {
    assert(false);
}
break;

查找

和普通二叉搜索树完全一样。

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

验证

写完插入后最好立刻验证，不然旋转平衡因子写错一个，后面排查很麻烦。

验证思路：递归计算每个节点左右子树的高度，检查高度差是否与 _bf 一致，且绝对值不超过 1。

int height() { return _height(_root); }
bool isBalanceTree() { return _isBalanceTree(_root); }

private:
int _height(Node* root) {
    if (!root) return 0;
    int lh = _height(root->_left);
    int rh = _height(root->_right);
    return rh > lh ? rh + 1 : lh + 1;
}

bool _isBalanceTree(Node* root) {
    if (!root) return true;
    int lh = _height(root->_left);
    int rh = _height(root->_right);
    int diff = rh - lh;
    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);
}

简单测试：插入 1 千万个随机数，输出是否平衡、树高和节点数。

void TestAVLTree2() {
    const int N = 10000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i);
    }
    size_t begin2 = clock();
    AVLTree<int, int> t;
    for (auto e : v) {
        t.insert(make_pair(e, e));
    }
    size_t end2 = clock();
    cout << "Insert: " << end2 - begin2 << endl;
    cout << t.isBalanceTree() << endl;
    cout << "Height: " << t.height() << endl;
    cout << "Size: " << t.size() << endl;
}

可以看到 600 多万节点仍保持平衡，树高只有二十几层。

性能与取舍

用 1 亿数据量测试插入、查找、删除：

void AVLTreeTest6() {
    const int N = 100000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++)
        v.push_back(rand() + i);

    AVLTree<int, int> t;
    size_t begin2 = clock();
    for (auto e : v) t.insert(make_pair(e, e));
    size_t end2 = clock();
    cout << t.isBalanceTree() << endl;
    cout << "Insert: " << end2 - begin2 << endl;
    cout << "Height: " << t.height() << endl;
    cout << "Size: " << t.size() << endl;

    size_t begin1 = clock();
    for (auto e : v) t.find(e);
    size_t end1 = clock();
    cout << "Find: " << end1 - begin1 << endl;

    size_t begin3 = clock();
    for (auto e : v) t.erase(e);
    size_t end3 = clock();
    cout << "Erase: " << end3 - begin3 << endl;
}

六千万个节点，插入总共花了 44 秒，依次删除花了 18 秒，而查找基本在 1 毫秒以内。

AVL 树的优缺点很分明：

• 搜索效率极高：1 亿数据最多比较 29 次（树高只有 29 层）。
• 插入删除慢：每次都可能触发旋转，平衡因子的维护有额外开销。

如果数据是静态的，或者读远多于写，AVL 树非常合适。如果频繁插入删除，红黑树通常更优（它对平衡要求不那么严格，旋转次数更少）。

典型应用场景包括数据库索引、符号表、路由表、静态字典等，这些场景下用 AVL 树换来的查找性能提升是值得的。