C++ AVL 树（平衡搜索树）概念讲解与模拟实现

AVL 树（平衡搜索树）概念讲解与模拟实现

一、AVL 树的概念讲解

理想状态下，当数据乱序并且二叉搜索树的形态趋近于满二叉树的时候，二叉搜索树查找的时间复杂度为 O(logN)，效率很高。但是，当数据有序或接近有序的时候，二叉搜索树会退化成单支树，此时进行数据查找的时间复杂度为 O(N)，相当于在顺序表中遍历数据进行查找，效率十分低。

1. 基于上述情况，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年提出 AVL 树（以人名命名），即使用 AVL 树（平衡搜索树）解决上述问题。
2. AVL 树是基于二叉搜索树实现的。向二叉搜索树中插入节点后，如果能保证二叉搜索树的左右子树的高度差的绝对值不超过 1（通过对树中的节点进行旋转实现），即高度差取值 -1, 0, 1，那么就可以降低树的高度。
3. 从而使树的形态退而求其次的达到一种趋近于满二叉树的形态，达到一种平衡，从而减少平均搜索长度。这样被优化的二叉搜索树进行查找的时间复杂度也就会降为 O(logN)，我们把这种被优化的二叉搜索树叫做 AVL 树。

一颗 AVL 树要么是空树，要么是具有以下性质的二叉搜索树：

• 它的左右子树都是 AVL 树
• 左右子树的高度差（平衡因子）的绝对值不超过 1，即高度差取值 -1, 0, 1
• AVL 树的节点如果有 N 个，那么树的高度是 logN，那么搜索的时间复杂度为 O(logN)

二、AVL 树的模拟实现

1. 节点结构

AVL 树采用类模板的形式，使用 key_value 结构实现，同时使用 pair 键值对。定义 AVL 树的节点，成员变量包括 pair 键值对、左右指针、父亲节点以及平衡因子。这里的父亲节点用于后续旋转中找到父亲节点进行链接，即节点的结构是三叉链的结构。

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

template<typename K, typename 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<typename K, typename V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    AVLTree() :_root(nullptr) {}
private:
    Node* _root;
};

2. 平衡因子

平衡因子本质是一个 int 类型的变量，它是用于判断是否需要进行旋转控制树的高度的。它的计算是采用当前节点的右子树的高度减去左子树的高度就为当前节点的平衡因子，在插入和删除过程中平衡因子需要频繁更新控制。

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

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

常规插入的情况下的平衡因子更新规律：如果新插入的节点处于其父亲节点的右边，那么其父亲节点的平衡因子应该 ++；如果新插入的节点处于其父亲节点的左边，那么其父亲节点的平衡因子应该 --。

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; // 三叉链需要额外链接 cur 的父亲节点
        if (cur->_kv.first > parent->_kv.first) {
            parent->_right = cur;
        }
        else {
            parent->_left = cur;
        }
        while (parent) { // 当 parent == nullptr 的时候，无法继续向上更新，退出即可
            if (cur->_kv.first > parent->_kv.first) {
                parent->_bf++;
            }
            else {
                parent->_bf--;
            }
            if (parent->_bf == 0) { // 此时父亲节点的平衡因子为 0，退出即可
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1) { // 迭代 cur 和 parent，继续向上更新
                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 { // 如果 cur 的平衡因子不符合为 1 或 -1 的情况，说明在插入前树已经不是 AVL 树了
                    assert(false);
                }
                break;
            }
            else { // 如果 parent 的平衡因子不符合为 0, 1 或 -1, 2 或 -2 的情况
                assert(false);
            }
        }
        return true;
    }
}

4. 四种旋转

进行旋转需要注意的问题需要保证它是搜索树变成平衡树并且降低这颗子树的高度。旋转分为左单旋、右单旋、右左双旋、左右双旋，这四种旋转我们不希望暴露给用户，所以我们将这四种旋转使用 private 访问限定符设置为私有成员。

左单旋

左单旋是 parent 节点的右边（右子树）高于左边（左子树），右边是一条直线，符合此时平衡因子 parent == 2 && cur == 1 的情况。此时 AVL 树不平衡，parent 的右边高，为了降低整棵子树的高度维持平衡，此时就应该进行左单旋。

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

右单旋

右单旋是 parent 节点的左边（左子树）高于右边（右子树），左边是一条直线，符合此时平衡因子 parent == -2 && cur == -1 的情况。此时 AVL 树不平衡，parent 的左边高度高，为了降低整棵子树的高度维持平衡，此时就应该进行右单旋。

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

右左双旋

右左双旋，顾名思义需要进行两次旋转，先以 cur 为旋转点进行右旋转，再以 parent 为旋转点进行左旋转。当平衡因子满足 parent == 2 && cur == -1，parent 和 cur 和 curleft 所在的节点构成曲线的时候，此时不能使用单纯的左单旋或右单旋，而是要使用两次旋转去完成降低高度控制平衡。

void RotateRL(Node* parent) {
    Node* cur = parent->_right;
    Node* curleft = cur->_left;
    int bf = curleft->_bf;
    RotateR(cur);
    RotateL(parent);
    if (bf == 0) { // 对应 h == 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 { // 如果 bf 出现其它情况，那么插入前该树已经不是 AVL 树
        assert(false);
    }
}

左右双旋

左右双旋是进行两次旋转，先以 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. 验证函数

我们知道 AVLTree 的最重要的特点就是左右子树的高度差的绝对值不超过 1。这里我们递归 AVL 树验证每一层的节点使用高度计算函数 Height 计算出的右子树的高度减去左子树的高度，即计算出并验证每一层的左右子树的高度差的绝对值是否都不超过 1。

同时还可以顺便验证计算出来当前节点的左右子树的高度差是否等于当前节点存储的平衡因子 _bf。如果不相等则打印出对应节点的 key 值及异常的平衡因子。

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

三、代码验证

1. 简单验证

使用第一组数据验证一下：

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

运行结果正确。

2. 大量随机数据验证

使用更严格更随机更大量的数据进行验证，设置好随机数种子，然后使用 rand 函数随机生成一千万的随机数数据构成 AVLTree 进行验证正确性。

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

test.cpp

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

#include <time.h>
#include <vector>

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