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

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

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

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 树快速查找合适的资源。
• 网络路由表：快速查找目标网络地址对应的路由信息，提高路由效率。
• 地图导航软件：存储地图中的地点信息，以便快速查找特定位置或进行路径规划。
• 游戏开发：管理游戏中的对象，如角色、道具等，实现快速的查找和操作。