C++ 进阶：AVL 树原理、旋转操作与代码实现

AVL 树概述

1. 什么是 AVL 树？

AVL 树（Adelson-Velsky and Landis Tree）是一种自平衡二叉搜索树。它由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出。AVL 树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态。 AVL 树要么是空树，要么是满足以下性质的二叉搜索树：其左、右子树也都是 AVL 树，并且左、右子树的高度差的绝对值不超过 1。

2. AVL 树的基本性质

• 高度近似平衡：AVL 树通过不断调整树的结构，保证树的左右子树高度差始终在允许范围内，使得树的高度相对较低。例如：在插入或删除节点后，会通过旋转操作（左旋、右旋、左右双旋、右左双旋）来重新平衡树。
• 查找效率稳定：由于 AVL 树高度平衡，其高度近似于 O(log n)，其中 n 是节点数量。这意味着在 AVL 树中进行查找操作时，时间复杂度稳定在 O(log n)。相比于普通二叉搜索树在最坏情况下可能退化为链表，查找时间复杂度为 O(n)，其查找效率更高且稳定。
• 基本操作：
  • 插入：新节点插入后，从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1，就需要进行旋转操作来恢复平衡。
  • 删除：删除节点后，同样从删除节点的位置向上检查祖先节点的平衡因子。如果出现不平衡，通过一系列的旋转操作和节点调整来重新平衡树。删除操作相对插入更复杂，因为可能需要多次旋转来恢复平衡。
  • 查找：和普通二叉搜索树查找方式相同，从根节点开始，根据比较节点值的大小，决定向左子树或右子树继续查找，直到找到目标节点或者确定目标节点不存在，时间复杂度为 O(log n)。

3. 为什么 AVL 树不要求左右子树的高度为 0 呢？

从平衡的理想状态看，高度差为 0 确实更平衡，但实际情况中，部分树的结构无法满足这一要求。当树的节点数为 2、4……等特定数量时，最优的高度差只能是 1，无法强制达到 0。这说明 AVL 树的平衡条件是在'绝对平衡'和'实现可行性'之间的权衡设计。

4. 什么是平衡因子？

每个节点都有一个平衡因子，其值等于该节点右子树的高度减去左子树的高度。因此，任何节点的平衡因子只能是 0、1 或 -1。平衡因子如同一个'风向标'，能帮助我们直观观察树的平衡状态并高效控制树的平衡维护过程——通过判断平衡因子是否超出 [-1, 1] 范围可快速定位需要调整的节点，进而通过旋转操作恢复树的平衡。

基本操作

一、查找操作

1. 步骤

定义进行遍历节点的指针，使用 while 循环查找对应节点：

• 情况 1：当前遍历到的节点的键 < 要查找的键 —> '继续向当前节点的右子树中查找'
• 情况 2：当前遍历到的节点的键 > 要查找的键 —> '继续向当前节点的左子树中查找'
• 情况 3：当前遍历到的节点的键 = 要查找的键 —> '找到了要查找的键'，跳出循环；若循环结束未找到，说明没有找到的键为 key 的节点。

2. 简述

• 初始化：从根节点开始查找，定义一个指针 curr 指向根节点 _root。
• 比较与移动：在 while 循环中，不断将当前节点的键 curr->_kv.first 与要查找的键 key 进行比较：
  • 如果 curr->_kv.first < key，这意味着要查找的节点在当前节点的右子树中，所以将 curr 更新为 curr->_right，继续在右子树中查找。
  • 如果 curr->_kv.first > key，说明要查找的节点在当前节点的左子树中，将 curr 更新为 curr->_left，继续在左子树中查找。
  • 如果 curr->_kv.first == key，表示找到了要查找的节点，直接返回当前节点的指针 curr。
• 查找失败：当 while 循环结束，curr 变为 nullptr，这表明在整个 AVL 树中没有找到键为 key 的节点，此时返回 nullptr。

二、插入操作

1. 本质

AVL 树的插入操作是在二叉搜索树插入逻辑基础上，增加了平衡维护的关键步骤，核心要解决'插入新节点可能破坏树的平衡，导致查询效率下降'的问题。

2. 简述

AVL 树插入 = 二叉搜索树插入（找位置、挂节点） + 平衡修复（更新平衡因子 + 旋转调整）。 流程分 5 步：

1. 空树处理：树为空时，新节点直接作为根。
2. 查找插入位置：从根出发，按二叉搜索树规则（小往左、大往右）找到新节点的父节点 parent，确定挂左还是挂右。
3. 挂载新节点：创建新节点，连接到 parent 的左 / 右子树，并维护 parent 指针。
4. 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（_bf），反映子树高度变化。
5. 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子。

3. 步骤

while (parent)
{
    // 第一步：更新新插入节点的父节点的平衡因子
    // 位置 1：新插入节点是左子节点 —> 父节点的平衡因子 -1
    if(current == parent->_left){ parent->_bf--; }
    // 位置 2：新插入节点是右子节点 —> 父节点的平衡因子 +1
    else{ parent->_bf++; }

    // 第二步：根据父节点的平衡因子做进一步的更新
    // 情况 1：父节点的平衡因子为 0 —> 高度变化未影响上层，结束更新
    if(parent->_bf == 0){ break; }
    // 情况 2：父节点的平衡因子为±1 —> 高度变化需向上传递，继续更新上层节点
    else if(parent->_bf == -1 || parent->_bf == 1){ current = current->_parent; parent = parent->_parent; }
    // 情况 3：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
    else if(parent->_bf == -2 || parent->_bf == 2)
    {
        // 失衡 1：左左失衡（父子平衡因子都为'负'） —> 右单旋
        if(parent->_bf == -2 && current->_bf == -1){ RotateR(parent); }
        // 失衡 2：右右失衡（父子平衡因子都为'正'） —> 左单旋
        else if(parent->_bf == 2 && current->_bf == 1){ RotateL(parent); }
        // 失衡 3：左右失衡（父为'负'，子为'正'） —> 左右双旋
        else if(parent->_bf == -2 && current->_bf == 1){ RotateLR(parent); }
        // 失衡 4：右左失衡（父为'正'，子为'负'） —> 右左双旋
        else if(parent->_bf == 2 && current->_bf == -1){ RotateRL(parent); }
        // 特殊情况：非法平衡因子 —> 断言失败
        else{ assert(false); }
        break;
    }
}
return true;

4. 图示

[图片]

三、删除操作

AVL 树的删除操作较为复杂，涉及多次旋转调整以恢复平衡，此处暂不展开详细代码实现，重点在于理解插入过程中的平衡维护机制。

旋转平衡

AVL 树通过下面的四种旋转操作维护平衡，这些操作在插入或删除节点导致树失衡时自动触发。

• 右单旋（RR 旋转）：处理 LL 型失衡
• 左单旋（LL 旋转）：处理 RR 型失衡
• 左右双旋（RL 旋转）：处理 RL 型失衡
• 右左双旋（LR 旋转）：处理 LR 型失衡

单旋

一、右单旋

1. 条件

当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的左子树插入节点导致的（即左子树的左子树深度增加，称为'LL 型失衡'），此时需要通过右单旋来恢复平衡。

2. 核心

旋转过程分为三步（以节点 parent 为旋转中心）：

• 提升左子节点：将 parent 的左子节点 subL 提升为新的根节点。
• 处理'悬挂'子树：subL 的右子树 subLR 需要重新挂接到 parent 的左子树。
• 更新父子关系：调整各节点的 _parent 指针，维护三叉链结构。

3. 步骤

// 第一阶段：准备阶段
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
Node* pParent = parent->_parent;

// 第二阶段：调整阶段
parent->_left = subLR;
if(subLR){ subLR->_parent = parent; }
parent->_parent = subL;
subL->_right = parent;

// 第三阶段：调整根节点或祖父节点的子树指向
if(parent == _root){ _root = subL; subL->_parent = nullptr; }
else
{
    if(parent == pParent->_left){ pParent->_left = subL; }
    else{ pParent->_right = subL; }
    subL->_parent = pParent;
}

// 第四阶段：更新平衡因子
subL->_bf = 0;
parent->_bf = 0;

4. 图示

[图片]

二、左单旋

1. 条件

当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的右子树插入节点导致（即右子树的右子树深度增加，称为'RR 型失衡'）时，需要通过左单旋恢复平衡。

2. 核心

旋转过程分为三步（以节点 parent 为旋转中心）：

• 提升右子节点：将 parent 的右子节点 subR 提升为新的根节点。
• 处理'悬挂'子树：subR 的左子树 subRL 需要重新挂接到 parent 的右子树。
• 更新父子关系：调整各节点的 _parent 指针，维护三叉链结构。

3. 步骤

// 第一阶段：准备阶段
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
Node* pParent = parent->_parent;

// 第二阶段：调整阶段
parent->_right = subRL;
if(subRL){ subRL->_parent = parent; }
parent->_parent = subR;
subR->_left = parent;

// 第三阶段：调整根节点或祖父节点的子树指向
if(pParent == nullptr)
{
    _root = subR;
    subR->_parent = nullptr;
}
else
{
    if(parent == pParent->_left){ pParent->_left = subR; }
    else{ pParent->_right = subR; }
    subR->_parent = pParent;
}

// 第四阶段：更新平衡因子
subR->_bf = 0;
parent->_bf = 0;

4. 图示

[图片]

双旋

一、左右双旋

1. 条件

当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的右子树插入节点导致（即左子树的右子树深度增加，称为'LR 型失衡'）时，需要通过左右双旋恢复平衡。左右双旋是左单旋 + 右单旋的复合操作，专门处理 LR 型失衡。

2. 核心

• 对 subL 执行左单旋：将 subL 的右子节点 subLR 提升为新根，subLR 的左子树 subLRL 挂接到 subL 的右子树。
• 对 parent 执行右单旋：将 subLR 提升为整棵子树的根，subLR 的原右子树 subLRR 挂接到 parent 的左子树。
• 更新父子关系：调整各节点的 _parent 指针，确保三叉链结构正确。
• 更新平衡因子：根据插入位置（subLR 的左 / 右子树），分情况修正 subLR、subL、parent 的平衡因子为 0 或 ±1。

3. 步骤

void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = parent->_left->_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); }
}

4. 图示

[图片]

二、右左双旋

1. 条件

当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的左子树插入节点导致（即右子树的左子树深度增加，称为'RL 型失衡'）时，需要通过右左双旋恢复平衡。右左双旋是右单旋 + 左单旋的复合操作，专门处理 RL 型失衡。

2. 核心

• 对 subR 执行右单旋：将 subR 的左子节点 subRL 提升为新根，subRL 的左子树 subRLR 挂接到 subR 的左子树。
• 对 parent 执行左单旋：将 subRL 提升为整棵子树的根，subRL 的原左子树 subRLL 挂接到 parent 的右子树。
• 更新父子关系：调整各节点的 _parent 指针，确保三叉链结构正确。
• 更新平衡因子：根据插入位置（subRL 的左 / 右子树），分情况修正 subRL、subR、parent 的平衡因子为 0 或 ±1。

3. 步骤

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

    // 首先对当前的节点的右子树进行'右单旋'
    RotateR(parent->_right);
    // 然后对当前的节点进行'左单旋'
    RotateL(parent);

    // 更新平衡因子
    if(bf == -1){ subRL->_bf = 0; subR->_bf = 1; parent->_bf = 0; }
    else if(bf == 1){ subRL->_bf = 0; subR->_bf = 0; parent->_bf = -1; }
    else if(bf == 0){ subRL->_bf = 0; subR->_bf = 0; parent->_bf = 0; }
    else{ assert(false); }
}

4. 图示

[图片]

代码实现

1. AVL 树的存储结构是什么样的？

一、节点的存储结构

AVL 树在二叉链基础上，额外增加了父节点指针、平衡因子来实现'自平衡'。严格来说，它属于三叉链存储结构（节点包含左子、右子、父节点三类指针），再配合平衡因子记录子树高度差。

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
{
private:
    AVLTreeNode<K, V>* _root = nullptr;
    typedef AVLTreeNode<K, V> Node;
public:
    // ... 成员函数 ...
};

2. 怎么使用代码实现 AVL 树？

头文件：AVLTree.h

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

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
{
private:
    AVLTreeNode<K, V>* _root = nullptr;
    typedef AVLTreeNode<K, V> Node;

    void _InOrder(Node* root)
    {
        if(root == nullptr){ return; }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }

    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 _IsAVLTree(Node* root)
    {
        if(root == nullptr){ return true; }
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        int bf = rightHeight - leftHeight;
        if(abs(bf) >= 2){ return false; }
        if(root->_bf != bf){ return false; }
        return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
    }

public:
    Node* Find(const K& key)
    {
        Node* curr = _root;
        while(curr)
        {
            if(curr->_kv.first < key){ curr = curr->_right; }
            else if(curr->_kv.first > key){ curr = curr->_left; }
            else{ return curr; }
        }
        return nullptr;
    }

    bool Insert(const pair<K, V>& kv)
    {
        if(_root == nullptr)
        {
            _root = new Node(kv);
            return true;
        }

        Node* current = _root;
        Node* parent = nullptr;

        while(current)
        {
            if(current->_kv.first < kv.first)
            {
                parent = current;
                current = current->_right;
            }
            else if(current->_kv.first > kv.first)
            {
                parent = current;
                current = current->_left;
            }
            else{ return false; }
        }

        current = new Node(kv);
        if(kv.first < parent->_kv.first){ parent->_left = current; }
        else{ parent->_right = current; }

        current->_parent = parent;

        while(parent)
        {
            if(current == parent->_left){ parent->_bf--; }
            else{ parent->_bf++; }

            if(parent->_bf == 0){ break; }
            else if(parent->_bf == -1 || parent->_bf == 1)
            {
                current = current->_parent;
                parent = parent->_parent;
            }
            else if(parent->_bf == -2 || parent->_bf == 2)
            {
                if(parent->_bf == -2 && current->_bf == -1){ RotateR(parent); }
                else if(parent->_bf == 2 && current->_bf == 1){ RotateL(parent); }
                else if(parent->_bf == -2 && current->_bf == 1){ RotateLR(parent); }
                else if(parent->_bf == 2 && current->_bf == -1){ RotateRL(parent); }
                else{ assert(false); }
                break;
            }
            else{ assert(false); }
        }
        return true;
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right;
        Node* pParent = parent->_parent;

        parent->_left = subLR;
        if(subLR){ subLR->_parent = parent; }
        parent->_parent = subL;
        subL->_right = parent;

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

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left;
        Node* pParent = parent->_parent;

        parent->_right = subRL;
        if(subRL){ subRL->_parent = parent; }
        parent->_parent = subR;
        subR->_left = parent;

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

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_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); }
    }

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

        RotateR(parent->_right);
        RotateL(parent);

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

    void InOrder(){ _InOrder(_root); cout << endl; }
    int Height(){ return _Height(_root); }
    int Size(){ return _Size(_root); }
    bool IsAVLTree(){ return _IsAVLTree(_root); }
};

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include"AVLTree.h"

void TestAVLTree1()
{
    cout << "------------------测试基本插入和平衡性------------------" << endl;
    AVLTree<int,int> t;
    int a2[] = {4,2,6,1,3,5,15,7,16,14};
    for(auto e : a2){ t.Insert({ e, e }); }
    t.InOrder();
    cout << "如果构建的那棵树是 AVL 树的话请扣 1：" << t.IsAVLTree() << endl;
}

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

运行结果

[图片]