C++ 实现 AVL 树：从原理到代码实战

C++ 实现 AVL 树：从原理到代码实战

前面我们已经学习了二叉搜索树。最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为 O(log N)。最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为 O(N/2)。如果是单链情况，大大降低了效率。

所以出现了改进的搜索树——AVL 树（平衡二叉搜索树）。

在 1962 年，俄罗斯数学家 G.M. Adelson-Velskii 和 E.M. Landis 提出了一种革命性的解决方案：他们发明了 AVL 树。通过在二叉搜索树插入新节点后，确保每个节点的左右子树高度差的绝对值不超过 1（即进行必要的树结构调整），这种方法能够有效控制树的高度，从而大幅度降低平均搜索长度。这个创新不仅解决了二叉搜索树在高频插入和删除操作中的性能瓶颈，也为平衡二叉树的发展奠定了基础，成为了数据结构领域的一个经典突破。

map 与 set 的底层实现也是 AVL 树或红黑树！

一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是 AVL 树
• 左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1 / 0 / 1）

如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log N)，搜索复杂度 O(log N)。

通过每次插入删除的调整（旋转）保证二叉树始终保持一个近乎完美的完全二叉树，规避了极端情况下二叉搜索树退化为单枝树的情况。

搭建 AVL 树：从零到自平衡的实现之路

树基打底：设计与框架构建

首先 AVL 树是在二叉搜索树的基础上进行改进，AVL 树节点中加入了：

• 平衡因子 _bf：左右子树的高度差 right 子树高度 - left 子树高度，即左子树插入节点时 _bf--，右子树插入节点时 _bf++
• 父指针 _parent：指向父节点的指针，为了可以回溯更新父节点的平衡因子

template<class K,class V> struct AVLTreeNode {
    //键值对 pair<K, V>
    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<class K, class V> class AVLTree {
    using Node = AVLTreeNode<K, V>;
private:
    Node* _root = nullptr;
};

插入有道：平衡与插入并存

实现插入操作，确保新节点的加入不会破坏树的平衡。

bool insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    Node* cur = _root;
    Node* prev = nullptr;
    //查找逻辑 cur 到对应的位置去
    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);
    // 连接 prev 与 cur
    if (prev->_kv.first > kv.first)
        prev->_left = cur;
    else
        prev->_right = cur;
    cur->_parent = prev;
    //更新平衡因子
}

接下来就是处理平衡因子：左子树插入节点时 _bf--，右子树插入节点时 _bf++。

这里思考一下，平衡因子的处理要到什么情况才停下来？？？ 当我们插入一个新节点时，有两种情况：

1. 插入 parent 的左子树，parent 的平衡因子减一！
2. 插入 parent 的右子树，parent 的平衡因子加一！

父节点的平衡因子经过更新后可以得到三种情况：

• parent 的平衡因子是 0：说明之前 parent 的左右两边不平衡，插入后平衡了，高度没有改变，不需要处理爷爷节点！！！
• parent 的平衡因子是 ±1：说明之前 parent 的平衡因子是 0，插入后以 parent 为根节点的子树的高度增加了！那么就要继续处理爷爷节点！
• parent 的平衡因子是 ±2：说明在本来就高的一边继续插入了一个新节点！以 parent 为根节点的子树已经不满足 AVL 树的结构，需要特殊处理！

首先可能要向上一直处理，所以干脆写一个 while 循环，在内部进行分类：如果需要继续处理爷爷节点，就继续循环，不需要处理就跳出循环！

// ... //更新平衡因子
while (prev != nullptr) {
    if (cur == prev->_left) {
        //左子树增加 父节点平衡因子--
        prev->_bf--;
    } else {
        //右子树增加 父节点平衡因子++
        prev->_bf++;
    }
    //为零直接退出
    if (prev->_bf == 0) {
        break;
    }
    //为 1 或 -1 继续向上进行
    else if (prev->_bf == 1 || prev->_bf == -1) {
        cur = prev;
        prev = cur->_parent;
    }
    //旋转来哩！！！
    else if (prev->_bf == 2 || prev->_bf == -2) {
        //分类旋转
        //旋转之后二叉树平衡！
        break;
    }
    //特殊情况处理 因为未来不知道会出什么 bug ,在这里截断一下
    else {
        assert(false);
    }
}

prev(cur 的父亲节点) 的平衡因子是 ±2 的情况的特殊处理就是旋转！！！下面我们来看如何进行旋！！！**

旋转为王：平衡的秘密武器

旋转是 AVL 树的精髓所在！

首先选择有四种：右单旋，左单旋，左右双旋，右左双旋。

右单旋

这是最简单的情况，简单的向右旋转，使其满足 AVL 树的性质！

再来看一般情况，并来具体分析一下：

1. 初始化情况：树的情况如图，parent 的平衡因子是 -1，subL 的平衡因子是 0！
2. 当我们在 subL 的左子树插入一个节点，并使 subL 的平衡因子变为 -1, parent 的平衡因子变为 -2（左边一边高，故右单旋）
3. 此时需要对 parent 进行右单旋

• parent 成为 subL 的右子树
• subLR 成为 parent 的左子树
• subL 代替原本 parent 的位置
• 注意处理平衡因子！！！处理 _parent 指针

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    //subLR->_parent = parent; //这里有个问题 subLR 为空呢？
    if (subLR)
        subLR->_parent = parent;
    Node* pparent = parent->_parent; //先记录再更改指向
    subL->_right = parent;
    parent->_parent = subL;
    //为根
    if (parent == _root) {
        _root = subL;
        subL->_parent = nullptr;
    }
    //这里个问题如何确定 subL 为 parnet->parent 的左右呢？
    else //不为根 还需要连接 parent->parent 和 subL
    {
        if (pparent->_left == parent)
            pparent->_left = subL;
        else
            pparent->_right = subL;
        subL->_parent = pparent;
    }
    //更新平衡因子
    subL->_bf = 0;
    parent->_bf = 0;
}

左单旋

左单旋与右单旋类似！！！

1. 初始化情况：树的情况如图，parent 的平衡因子是 1，subR 的平衡因子是 0！
2. 当我们在 subR 的右子树插入一个节点，并使 subR 的平衡因子变为 1, parent 的平衡因子变为 2
3. 此时需要对 parent 进行左单旋

• parent 成为 subR 的左子树
• subRL 成为 parent 的右子树
• subR 代替原本 parent 的位置
• 注意处理平衡因子！！！处理 _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;
}

左右双旋

这种情况既不能通过右单旋解决，也不能通过左单旋解决！！！这时候就需要进行左右双旋：先进行一次左单旋，再进行一次右单旋。

Tip：subL 的 bf 为 1，右边高了 所以第一次对 subL 左旋 parent 的 bf 为 2 左边高了 所以第二次对 parent 右旋。

具体怎么操作，我们来看图分析。

注意，根据图分析，插入的位置会影响 subL 和 parent 的平衡因子，需要根据 subLR 分类讨论。

如果插入到 subLR 的右子树，那么该右子树最终会变成 parent 的左子树，所以相当于 parent 的左子树插入节点，所以 parent 的平衡因子应为 -1 如果插入到 subLR 的左子树，那么该左子树最终会变成 subL 的左子树，所以相当于 subL 的右子树插入节点，所以 parent 的平衡因子应为 1 如果 subLR 自己是新插入的节点，那么平衡因子都为 0！

我们可以只观察结果：subLR 成为了新根，subL 左子树（左单旋 左子树），parent 右子树（右单旋 右子树），subLR 之前的左子树分给了 subL 的右子树，subLR 之前的右子树分给了 parent 的左子树。

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

右左双旋

情况与左右双旋类似，不再赘述。

// 右左双旋 parent 最后在 subRL 左
void RotateRL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    if (bf == -1) //左 0 右 1 bf=-1 右边低 低的充当 subRL 的右树（subR）的左树 所以 subR->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);
    }
}

我们完成了旋转，就可以补全插入操作的空缺，按情况分好类即可：

bool insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    Node* cur = _root;
    Node* prev = nullptr;
    //查找逻辑 cur 到对应的位置去
    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);
    // 连接 prev 与 cur
    if (prev->_kv.first > kv.first)
        prev->_left = cur;
    else
        prev->_right = cur;
    cur->_parent = prev;
    // 更新平衡因子 Tip 更新结束条件？
    while (prev) //可能一直更新到根 根的 prev 即 parent 为空 结束更新
    {
        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 = prev->_parent;
        }
        else if (prev->_bf == 2 || prev->_bf == -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;
        }
        else {
            assert(false);
        }
    }
    return true;
}

在这里可以测试一下！！！一定一定保证插入没有问题了在向下进行其他函数的书写，不然出错了就会让人崩溃的！！！**

查找制胜：高效查询之道

寻找与二叉搜索树一样：

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

性能透析：AVL 树的效率与边界

我们写了这么多的代码，现在来测试一下，来看看是否满足 AVL 树！！！

验证 AVL 树就要来检查每个节点的平衡因子是否满足条件！平衡因子的本质是左右子树的高度差，所以我们可以通过检查每颗子树的高度差来看看是否满足条件，然后还有个问题就是可能平衡因子更新错误了，这个也是需判断的。

int height() { return _height(_root); }
bool isBalanceTree() { return _isBalanceTree(_root); }
private:
int _height(Node* root) {
    if (root == nullptr) return 0;
    int leftHeight = _height(root->_left);
    int rightHeight = _height(root->_right);
    return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
}
bool _isBalanceTree(Node* root) {
    if (root == nullptr) return true;
    // 计算 Root 结点的平衡因⼦：即 Root 左右⼦树的⾼度差
    int leftHeight = _height(root->_left);
    int rightHeight = _height(root->_right);
    int diff = rightHeight - leftHeight;
    // Root 平衡因⼦的绝对值超过 1，则⼀定不是 AVL 树
    if (abs(diff) >= 2) {
        cout << root->_kv.first << "高度差异常" << endl;
        return false;
    }
    // 如果计算出的平衡因⼦与 Root 的平衡因⼦不相等 不是 AVL 树
    if (root->_bf != diff) {
        cout << root->_kv.first << "平衡因子异常" << endl;
        return false;
    }
    // Root 的左和右如果都是 AVL 树，则该树⼀定是 AVL 树
    return _isBalanceTree(root->_left) && _isBalanceTree(root->_right);
}

现在：我们写个测试代码测试一下：

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

可以看到我们插入了六百万多节点，仍保持平衡结构！

现在来分析一下性能。我们提供 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);
    }
    size_t begin2 = clock();
    AVLTree<int, int> t;
    for (auto e : v) {
        t.insert(make_pair(e, e));
    }
    cout << t.isBalanceTree() << endl;
    size_t end2 = clock();
    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 (size_t i = 0; i < N; i++)
    //{ 
    //    t.find((rand() + i));
    //}
    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 s，依次删除所有节点用时 18s，搜索只用了不到 1ms！！！

所以 AVL 树的优缺点很明显：

• 插入删除的效率比较低，毕竟每次插入删除时都有对应更新平衡因子，还要考虑旋转的情况。
• 搜索的效率是真的快！！！1 亿数据量的最多就搜索 29 次（因为最高才 29 层）。

下面是对 AVL 树性能的分析：

查找操作最坏情况时间复杂度：O(log n)，平均情况时间复杂度：O(log n)。由于 AVL 树总是保持平衡的，因此查找操作的时间复杂度与树的高度成正比，树的高度最小，查找效率就高。

插入操作最坏情况时间复杂度：O(log n)，平均情况时间复杂度：O(log n)。插入操作后，AVL 树可能会失去平衡。为了恢复平衡，可能需要进行一次或多次旋转（单旋转或双旋转）。尽管如此，这些操作的时间复杂度仍然是对数级别的。

删除操作最坏情况时间复杂度：O(log n)，平均情况时间复杂度：O(log n)。删除操作与插入操作类似，可能会使树失去平衡，需要进行旋转操作来恢复平衡。

空间复杂度：O(n)。AVL 树需要存储额外的信息（例如节点的平衡因子），以及可能需要的额外空间来执行旋转操作。

AVL 树在频繁进行插入和删除操作的场景中可能不是最佳选择。在这些情况下，红黑树等其他自平衡二叉搜索树可能是更好的选择，因为它们对平衡的要求不那么严格，从而在插入和删除操作时可能需要更少的旋转操作。

如果数据结构是静态的，即一旦创建就不会频繁修改，AVL 树是一个很好的选择，因为它可以提供高效的查询操作。但是，如果数据结构需要频繁地修改，那么可能需要考虑使用其他数据结构，如红黑树、B 树或跳表等，这些数据结构在动态操作方面可能更加高效。

AVL 树的应用场景：

• 数据库系统：用于高效地存储和检索数据，保证快速的查找、插入和删除操作。
• 文件系统：帮助管理文件目录结构，快速定位文件。
• 编译器设计：在符号表的实现中，可以快速查找变量、函数等的信息。
• 操作系统：管理内存分配、进程调度等任务时，可利用 AVL 树快速查找合适的资源。
• 网络路由表：快速查找目标网络地址对应的路由信息，提高路由效率。
• 地图导航软件：存储地图中的地点信息，以便快速查找特定位置或进行路径规划。
• 游戏开发：管理游戏中的对象，如角色、道具等，实现快速的查找和操作。