C++ 实现 AVL 树：结构、插入与旋转操作详解

三、插入操作

3.1 插入操作概述

AVL 树的插入操作包括三步：

1. 按二叉查找树规则插入节点；
2. 更新每个节点的平衡因子；
3. 如果需要，进行旋转操作 来恢复树的平衡。

bool Insert(const pair<K, V>& kv);

3.2 步骤 1：按二叉查找树规则插入节点

在插入节点时，我们根据值的大小，递归地找到插入位置，并在该位置插入新节点：

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->_right; // 在右子树中查找插入位置
    } else if (cur->_kv.first > kv.first) {
        parent = cur;
        cur = cur->_left; // 在左子树中查找插入位置
    } else {
        return false; // 如果节点已存在，不插入
    }
}
cur = new Node(kv);
if (parent->_kv.first < kv.first) {
    parent->_right = cur;
} else {
    parent->_left = cur;
}
// 更新插入节点的_parent
cur->_parent = parent;

3.3 步骤 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 || parent->_bf == -2) {
        // 旋转
        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;
    } else {
        assert(false);
    }
}
return true;

3.4 步骤 3：旋转操作详解

如果某个节点的平衡因子为 2 或 -2，表示该节点不平衡。我们需要通过旋转操作来恢复平衡。旋转操作有四种：

1. 右单旋 (RotateR)
2. 左单旋 (RotateL)
3. 左右双旋 (RotateLR)
4. 右左双旋 (RotateRL)

3.4.1 右单旋

右单旋适用于当左子树较高时，执行旋转操作来恢复平衡。

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

3.4.2 左单旋

左单旋适用于当右子树较高时，执行旋转操作来恢复平衡。

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* ppNode = parent->_parent;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    parent->_parent = subR;
    if (subRL) {
        subRL->_parent = parent;
    }
    subR->_left = parent;
    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;
}

3.4.3 左右双旋

当左子树的右子树较高时，首先进行左旋，再进行右旋，恢复平衡。

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 if (bf == 0) {
        subL->_bf = subLR->_bf = parent->_bf = 0;
    } else {
        assert(false);
    }
}

总结：找失衡原因，决定如何旋转

• 左子树的左子树高：进行 R
• 右子树的右子树高：进行 L
• 左子树的右子树高：进行 LR
• 右子树的左子树高：进行 RL

四、其他操作

4.1 查找操作 (Find)

查找操作与普通的二叉查找树类似。通过不断比较当前节点的键值和目标值，沿树的路径查找目标节点。

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; // 如果没有找到，返回空
}

该方法的时间复杂度为 O(log N)，因为 AVL 树是平衡的，树的高度是对数级别的。

4.2 计算树的高度 (Height)

树的高度指的是从根节点到最远叶子节点的最长路径上的边数。AVL 树的高度是平衡的，计算时我们需要递归地计算左右子树的高度并返回较大的一个。

int Height() {
    return _Height(_root); // 从根节点开始计算树的高度
}
int _Height(Node* root) {
    if (root == nullptr) return 0; // 空树的高度为 0
    int leftHeight = _Height(root->_left); // 递归计算左子树的高度
    int rightHeight = _Height(root->_right); // 递归计算右子树的高度
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; // 返回较大值，并加 1
}

该方法的时间复杂度为 O(N)，其中 N 为节点总数。虽然 AVL 树是平衡的，但在计算高度时需要遍历整个树。

4.3 计算节点数量 (Size)

节点数量是树中所有节点的总数。通过递归遍历树，计算左右子树的节点数量，并加上当前节点。

int Size() {
    return _Size(_root); // 从根节点开始计算树的大小
}
int _Size(Node* root) {
    if (root == nullptr) return 0; // 空树节点数量为 0
    return _Size(root->_left) + _Size(root->_right) + 1; // 左右子树的节点数量加 1
}

该方法的时间复杂度为 O(N)，需要遍历整个树来计算节点总数。

4.4 树是否平衡 (IsBalanceTree)

为了验证 AVL 树的平衡性，我们需要检查每个节点的平衡因子，并确保它们的绝对值不超过 1。如果树的任意节点的平衡因子大于 1 或小于 -1，那么树就不平衡。

bool _IsBalanceTree(Node* root) {
    if (root == nullptr) 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; // 如果高度差大于等于 2，树不平衡
    }
    if (root->_bf != diff) {
        cout << root->_kv.first << "平衡因子异常" << endl;
        return false; // 如果平衡因子与实际高度差不符，树不平衡
    }
    // 递归检查左右子树是否平衡
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

该方法的时间复杂度为 O(N)，需要递归遍历整个树并计算每个节点的平衡因子。

五、性能分析与测试

5.1 性能分析

AVL 树通过保持平衡，保证了插入、查找和删除操作的时间复杂度都为 O(logN)，相比于普通的二叉查找树，AVL 树避免了退化成链表的情况，极大提高了性能。

5.2 测试代码

下面是两个测试代码，用于验证 AVL 树的插入和查找操作。

// 测试代码
void TestAVLTree1() {
    AVLTree<int, int> t;
    // 常规的测试用例
    // int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    // 特殊的带有双旋场景的测试用例
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        t.Insert({ e, e });
        cout << "Insert:" << e << "->";
        cout << t.IsBalanceTree() << endl;
    }
    t.InOrder();
    cout << 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 begin2 = clock();
    AVLTree<int, int> t;
    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); }*/
    // 随机值
    for (int i = 0; i < N; i) {
        t.Find((rand() + i));
    }
    size_t end1 = clock();
    cout << "Find:" << end1 - begin1 << endl;
}

六、全部代码

AVLTree.h

#pragma once
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 == 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->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } 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 = cur->_parent;
            } else if (parent->_bf == 2 || parent->_bf == -2) {
                // 旋转
                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;
            } else {
                assert(false);
            }
        }
        return true;
    }

    void InOrder() {
        _InOrder(_root);
    }

    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 == nullptr) return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    int _Height(Node* root) {
        if (root == nullptr) return 0;
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    bool _IsBalanceTree(Node* root) {
        if (root == nullptr) 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);
    }

    void _InOrder(Node* root) {
        if (root == nullptr) {
            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* ppNode = parent->_parent;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        parent->_parent = subR;
        if (subRL) {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        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 if (bf == 0) {
            subL->_bf = subLR->_bf = parent->_bf = 0;
        } 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) {
            parent->_bf = subR->_bf = 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;
        } else {
            assert(false);
        }
    }

    Node* _root = nullptr;
};

// 测试代码
void TestAVLTree1() {
    AVLTree<int, int> t;
    // 常规的测试用例
    // int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    // 特殊的带有双旋场景的测试用例
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        /*if (e == 14) { int x = 0; }*/
        t.Insert({ e, e });
        cout << "Insert:" << e << "->";
        cout << t.IsBalanceTree() << endl;
    }
    t.InOrder();
    cout << 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 begin2 = clock();
    AVLTree<int, int> t;
    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); }*/
    // 随机值
    for (int i = 0; i < N; i) {
        t.Find((rand() + i));
    }
    size_t end1 = clock();
    cout << "Find:" << end1 - begin1 << endl;
}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;
#include "AVLTree.h"

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

七、总结与展望

随着数据量的不断增长，如何保持高效的查找与插入操作成为了现代计算机科学的核心问题之一。AVL 树作为一种自平衡二叉查找树，凭借其稳定的时间复杂度和高效的性能，已广泛应用于各类需要动态数据结构支持的场景。未来，随着算法和硬件的进一步发展，AVL 树的实现和优化将迎来更多挑战与机遇。