C++ AVL 树概念讲解与模拟实现

2. 平衡因子

平衡因子本质是一个 int 类型的变量，用于判断是否需要进行旋转控制树的高度。它的计算方式是当前节点的右子树高度减去左子树高度。

正常情况下，平衡因子的取值为 -1、0、1。一旦平衡因子的绝对值超出这个区间（即为 2 或 -2），说明当前节点的左右子树高度差的绝对值大于 1，不符合 AVL 树的性质，此时就需要进行旋转降低树的高度。

为了控制树的高度进行的旋转有四种：左单旋、右单旋、右左双旋、左右双旋。这些情况都是通过平衡因子判断出来的。

常规插入情况下的平衡因子更新规律如下：

• 如果新插入的节点处于其父亲节点的右边，那么其父亲节点的平衡因子应该 ++。
• 如果新插入的节点处于其父亲节点的左边，那么其父亲节点的平衡因子应该 --。

3. 插入逻辑

关于插入找节点的逻辑与二叉搜索树的非递归插入类似。由于是三叉链结构，还需要将标记的 cur 的父亲节点 parent 链接到 cur 中的父指针 _parent 上。

完成节点插入后，需要更新控制当前插入节点父亲的平衡因子，并根据父亲平衡因子判断是否需要向上更新，以及是否当前树处于不平衡状态，是否需要旋转。

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    } else {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (kv.first > cur->_kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (kv.first < cur->_kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false; // 已存在
            }
        }
        cur = new Node(kv);
        cur->_parent = parent;
        
        if (cur->_kv.first > parent->_kv.first) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }

        while (parent) {
            if (cur->_kv.first > parent->_kv.first) {
                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 || parent->_bf == -2) {
                // 需要旋转
                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) {
                    RotateRL(parent);
                } else if (parent->_bf == -2 && cur->_bf == 1) {
                    RotateLR(parent);
                } else {
                    assert(false); // 插入前树已不平衡
                }
                break;
            } else {
                assert(false); // 平衡因子异常
            }
        }
        return true;
    }
}

4. 四种旋转

旋转的目的是在保证它是搜索树的前提下变成平衡树，并降低这颗子树的高度。这四种旋转我们设置为私有成员函数。

左单旋 (LL)

当 parent 节点的右边高于左边，且是一条直线（parent == 2 && cur == 1）时，进行左单旋。

void RotateL(Node* parent) {
    Node* ppnode = parent->_parent;
    Node* cur = parent->_right;
    Node* curleft = cur->_left;

    parent->_right = curleft;
    if (curleft) curleft->_parent = parent;
    
    cur->_left = parent;
    parent->_parent = cur;

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

右单旋 (RR)

当 parent 节点的左边高于右边，且是一条直线（parent == -2 && cur == -1）时，进行右单旋。

void RotateR(Node* parent) {
    Node* ppnode = parent->_parent;
    Node* cur = parent->_left;
    Node* curright = cur->_right;

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

    cur->_right = parent;
    parent->_parent = cur;

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

右左双旋 (RL)

先以 cur 为旋转点进行右旋转，再以 parent 为旋转点进行左旋转。适用于 parent == 2 && cur == -1 的情况。

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

    RotateR(cur);
    RotateL(parent);

    if (bf == 0) {
        parent->_bf = 0;
        cur->_bf = 0;
        curleft->_bf = 0;
    } else if (bf == -1) {
        parent->_bf = 0;
        cur->_bf = 1;
        curleft->_bf = 0;
    } else if (bf == 1) {
        parent->_bf = -1;
        cur->_bf = 0;
        curleft->_bf = 0;
    } else {
        assert(false);
    }
}

左右双旋 (LR)

先以 cur 为旋转点进行左单旋，再以 parent 为旋转点进行右单旋。适用于 parent == -2 && cur == 1 的情况。

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

    RotateL(cur);
    RotateR(parent);

    if (bf == 0) {
        parent->_bf = 0;
        cur->_bf = 0;
        curright->_bf = 0;
    } else if (bf == -1) {
        parent->_bf = 1;
        cur->_bf = 0;
        curright->_bf = 0;
    } else if (bf == 1) {
        parent->_bf = 0;
        cur->_bf = -1;
        curright->_bf = 0;
    } else {
        assert(false);
    }
}

5. 验证函数

我们需要验证每一层的节点左右子树的高度差的绝对值是否都不超过 1。同时可以顺便验证计算出的高度差是否等于节点存储的平衡因子 _bf。

int Height() {
    return Height(_root);
}

int Height(Node* root) {
    if (root == nullptr) return 0;
    int heightL = Height(root->_left);
    int heightR = Height(root->_right);
    return heightL > heightR ? heightL + 1 : heightR + 1;
}

bool IsBalance() {
    return IsBalance(_root);
}

bool IsBalance(Node* root) {
    if (root == nullptr) return true;
    Node* left = root->_left;
    Node* right = root->_right;
    int heightL = Height(left);
    int heightR = Height(right);
    int bf = heightR - heightL;

    if (bf != root->_bf) {
        cout << "平衡因子异常" << root->_kv.first << ":" << root->_bf << endl;
        return false;
    }
    return abs(bf) <= 1 && IsBalance(left) && IsBalance(right);
}

三、验证测试

简单验证

使用两组典型数据验证代码是否能构建出正确的 AVL 树。

#include <iostream>
#include "AVLTree.h"
using namespace std;

int main() {
    int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    AVLTree<int, int> alv;
    for (auto e : arr) {
        alv.Insert(make_pair(e, e));
        cout << e << ":" << alv.IsBalance() << endl;
    }
    return 0;
}

大规模随机验证

仅靠少量数据不足以验证正确性，使用随机生成的一千万个数据进行严格测试。

#include <iostream>
#include "AVLTree.h"
#include <time.h>
#include <vector>
using namespace std;

int main() {
    srand((unsigned int)time(NULL));
    const int N = 10000000;
    vector<int> v;
    v.reserve(N);
    for (int i = 0; i < N; i++) {
        v.push_back(rand());
    }
    AVLTree<int, int> avl;
    for (auto e : v) {
        avl.Insert(make_pair(e, e));
    }
    cout << avl.IsBalance() << endl;
    cout << avl.Height() << endl;
    return 0;
}

四、源代码

AVLTree.h

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

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

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

template<typename K, typename V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    AVLTree() : _root(nullptr) {}

    bool Insert(const pair<K, V>& kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        } else {
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur) {
                if (kv.first > cur->_kv.first) {
                    parent = cur;
                    cur = cur->_right;
                } else if (kv.first < cur->_kv.first) {
                    parent = cur;
                    cur = cur->_left;
                } else {
                    return false;
                }
            }
            cur = new Node(kv);
            cur->_parent = parent;
            if (cur->_kv.first > parent->_kv.first) {
                parent->_right = cur;
            } else {
                parent->_left = cur;
            }
            while (parent) {
                if (cur->_kv.first > parent->_kv.first) {
                    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 || parent->_bf == -2) {
                    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) {
                        RotateRL(parent);
                    } else if (parent->_bf == -2 && cur->_bf == 1) {
                        RotateLR(parent);
                    } else {
                        assert(false);
                    }
                    break;
                } else {
                    assert(false);
                }
            }
            return true;
        }
    }

    int Height() {
        return Height(_root);
    }

    int Height(Node* root) {
        if (root == nullptr) return 0;
        int heightL = Height(root->_left);
        int heightR = Height(root->_right);
        return heightL > heightR ? heightL + 1 : heightR + 1;
    }

    bool IsBalance() {
        return IsBalance(_root);
    }

    bool IsBalance(Node* root) {
        if (root == nullptr) return true;
        Node* left = root->_left;
        Node* right = root->_right;
        int heightL = Height(left);
        int heightR = Height(right);
        int bf = heightR - heightL;
        if (bf != root->_bf) {
            cout << "平衡因子异常" << root->_kv.first << ":" << root->_bf << endl;
            return false;
        }
        return abs(bf) <= 1 && IsBalance(left) && IsBalance(right);
    }

private:
    void RotateL(Node* parent) {
        Node* ppnode = parent->_parent;
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        parent->_right = curleft;
        if (curleft) curleft->_parent = parent;
        cur->_left = parent;
        parent->_parent = cur;
        if (ppnode == nullptr) {
            _root = cur;
            cur->_parent = nullptr;
        } else {
            cur->_parent = ppnode;
            if (ppnode->_left == parent) {
                ppnode->_left = cur;
            } else {
                ppnode->_right = cur;
            }
        }
        parent->_bf = cur->_bf = 0;
    }

    void RotateR(Node* parent) {
        Node* ppnode = parent->_parent;
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        parent->_left = curright;
        if (curright) curright->_parent = parent;
        cur->_right = parent;
        parent->_parent = cur;
        if (ppnode == nullptr) {
            _root = cur;
            cur->_parent = nullptr;
        } else {
            if (ppnode->_left == parent) {
                ppnode->_left = cur;
                cur->_parent = ppnode;
            } else {
                ppnode->_right = cur;
                cur->_parent = ppnode;
            }
        }
        parent->_bf = cur->_bf = 0;
    }

    void RotateRL(Node* parent) {
        Node* cur = parent->_right;
        Node* curleft = cur->_left;
        int bf = curleft->_bf;
        RotateR(cur);
        RotateL(parent);
        if (bf == 0) {
            parent->_bf = 0;
            cur->_bf = 0;
            curleft->_bf = 0;
        } else if (bf == -1) {
            parent->_bf = 0;
            cur->_bf = 1;
            curleft->_bf = 0;
        } else if (bf == 1) {
            parent->_bf = -1;
            cur->_bf = 0;
            curleft->_bf = 0;
        } else {
            assert(false);
        }
    }

    void RotateLR(Node* parent) {
        Node* cur = parent->_left;
        Node* curright = cur->_right;
        int bf = curright->_bf;
        RotateL(cur);
        RotateR(parent);
        if (bf == 0) {
            parent->_bf = 0;
            cur->_bf = 0;
            curright->_bf = 0;
        } else if (bf == -1) {
            parent->_bf = 1;
            cur->_bf = 0;
            curright->_bf = 0;
        } else if (bf == 1) {
            parent->_bf = 0;
            cur->_bf = -1;
            curright->_bf = 0;
        } else {
            assert(false);
        }
    }

private:
    Node* _root;
};

五、总结

AVL 树通过维护平衡因子解决了二叉搜索树在最坏情况下退化为链表的问题。实现的关键在于正确理解四种旋转场景及平衡因子的更新规则。本文详细解析了 AVL 树的定义、节点设计、插入逻辑、旋转策略及代码实现，并通过简单与大规模数据验证了代码的正确性。