C++ AVL 树详解：原理、旋转与实现

• bf 变为 0：说明该子树高度未变，无需继续向上更新，直接结束。
• bf 变为 ±1：说明子树高度增加，但整体仍平衡，需继续向上传播更新。
• bf 变为 ±2：说明失衡，必须进行旋转操作。

注意：当发现 parent 的 bf 变为 ±2 时，引起失衡的子节点 cur 的 bf 必定是 ±1，不可能是 0。这是因为如果 cur 的 bf 为 0，插入前该子树高度已确定，插入后不会导致父节点直接跳变到 ±2。

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;

    // 1. 二叉搜索树插入阶段
    while (cur) {
        if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        } else if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false; // 键已存在
        }
    }

    cur = new Node(kv);
    if (parent->_kv.first < kv.first) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    cur->_parent = parent;

    // 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 = parent->_parent; // 继续向上
        } else {
            // 失衡，需要旋转
            if (parent->_bf == 2 && cur->_bf == 1) {
                RotateL(parent); // LL 型
            } else if (parent->_bf == -2 && cur->_bf == -1) {
                RotateR(parent); // RR 型
            } else if (parent->_bf == -2 && cur->_bf == 1) {
                RotateLR(parent); // LR 型
            } else {
                RotateRL(parent); // RL 型
            }
            break; // 旋转后高度恢复，停止更新
        }
    }
    return true;
}

旋转操作详解

当平衡因子绝对值达到 2 时，需通过旋转恢复平衡。命名规则依据失衡方向：LL 表示父节点左高且子节点左高，RR 同理，LR 和 RL 则为双旋。

左单旋 (RR 型)

发生在右子树过高时（parent bf = -2）。将右子节点提上来作为新根，原根成为其左孩子。

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

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

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

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

    parent->_bf = 0;
    subR->_bf = 0;
}

右单旋 (LL 型)

发生在左子树过高时（parent bf = 2）。逻辑与左单旋对称。

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

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

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

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

    subL->_bf = 0;
    parent->_bf = 0;
}

左右双旋 (LR 型)

先对左子节点进行左旋，再对父节点进行右旋。适用于 parent bf=2 且 cur bf=-1 的情况。

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 {
        subLR->_bf = 0;
        subL->_bf = 0;
        parent->_bf = 0;
    }
}

右左双旋 (RL 型)

先对右子节点进行右旋，再对父节点进行左旋。适用于 parent bf=-2 且 cur bf=1 的情况。

void RotateRL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

    RotateR(subR);
    RotateL(parent);

    subRL->_bf = 0;
    if (bf == 1) {
        subR->_bf = 0;
        parent->_bf = -1;
    } else if (bf == -1) {
        subR->_bf = 1;
        parent->_bf = 0;
    } else {
        subR->_bf = 0;
        parent->_bf = 0;
    }
}

验证与性能

验证方法

1. 中序遍历：检查是否有序，确保满足 BST 性质。
2. 平衡性检查：递归计算高度并判断差值。高效做法是在一次后序遍历中同时获取高度和判断平衡。

bool _IsBalance(Node* root, int& height) {
    if (root == nullptr) {
        height = 0;
        return true;
    }
    int leftHeight = 0, rightHeight = 0;
    if (!_IsBalance(root->_left, leftHeight)) return false;
    if (!_IsBalance(root->_right, rightHeight)) return false;

    root->_bf = rightHeight - leftHeight;
    if (abs(root->_bf) >= 2) {
        cout << root->_kv.first << "不平衡" << endl;
        return false;
    }
    height = max(leftHeight, rightHeight) + 1;
    return true;
}

性能分析

• 查询：O(log n)，非常稳定。
• 插入/删除：O(log n)，但维护成本高于红黑树。因为 AVL 追求绝对平衡，旋转次数可能更多，尤其在频繁删除场景下。
• 适用场景：适合查询频繁、修改较少的静态或半静态数据集合。

完整代码实现

#pragma once
#include <assert.h>
#include <vector>
#include <iostream>
using namespace std;

template <class K, class V>
struct AVLTreeNode {
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf;
    pair<K, V> _kv;

    AVLTreeNode(const pair<K, V>& kv)
        : _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {}
};

template <class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;

        while (cur) {
            if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first < kv.first) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        cur->_parent = parent;

        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 = parent->_parent;
            } else {
                if (parent->_bf == 2 && cur->_bf == 1) {
                    RotateL(parent);
                } else if (parent->_bf == -2 && cur->_bf == -1) {
                    RotateR(parent);
                } else if (parent->_bf == -2 && cur->_bf == 1) {
                    RotateLR(parent);
                } else {
                    RotateRL(parent);
                }
                break;
            }
        }
        return true;
    }

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

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

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

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

        subL->_bf = 0;
        parent->_bf = 0;
    }

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

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

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

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

        parent->_bf = 0;
        subR->_bf = 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 {
            subLR->_bf = 0;
            subL->_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);

        subRL->_bf = 0;
        if (bf == 1) {
            subR->_bf = 0;
            parent->_bf = -1;
        } else if (bf == -1) {
            subR->_bf = 1;
            parent->_bf = 0;
        } else {
            subR->_bf = 0;
            parent->_bf = 0;
        }
    }

    void InOrder() {
        _InOrder(_root);
    }

    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_kv.first << "[" << root->_bf << "]" << endl;
        _InOrder(root->_right);
    }

    bool IsBalance() {
        int height = 0;
        return _IsBalance(_root, height);
    }

    bool _IsBalance(Node* root, int& height) {
        if (root == nullptr) {
            height = 0;
            return true;
        }
        int leftHeight = 0, rightHeight = 0;
        if (!_IsBalance(root->_left, leftHeight)) return false;
        if (!_IsBalance(root->_right, rightHeight)) return false;

        root->_bf = rightHeight - leftHeight;
        if (abs(root->_bf) >= 2) {
            cout << root->_kv.first << "不平衡" << endl;
            return false;
        }
        height = max(leftHeight, rightHeight) + 1;
        return true;
    }

private:
    Node* _root = nullptr;
};

补充说明

模板声明的位置

代码中出现了两次 template<class K, class V>。第一次用于定义节点结构体 AVLTreeNode，第二次用于定义树类 AVLTree。这是 C++ 模板语法的规范写法，分别告知编译器这两个类型都是模板类。

调试建议

在开发过程中，可以通过条件断点定位失衡问题。例如在插入特定元素时暂停，观察树的结构变化。中序遍历输出可以辅助验证 BST 性质，IsBalance 函数则能实时反馈当前状态。