跳到主要内容
极客日志极客日志
首页博客AI提示词GitHub精选代理工具
|注册
博客列表

目录

  1. 1. AVL 树的概念
  2. 2. AVL 树的实现
  3. 2.1 AVL 树节点结构实现
  4. 2.2 AVL 树的结构
  5. 2.3 AVL 树插入功能实现
  6. 1. 插入步骤
  7. 2. 平衡因子更新
  8. 3. 旋转
  9. 1. 右单旋
  10. 2. 左单旋
  11. 3. 左右双旋
  12. 4. 右左双旋
  13. 完整插入代码
  14. 2.4 AVL 树查找功能实现
  15. 2.5 AVL 树平衡检测
C++算法

C++ AVL 树详解与实现

本文介绍了 AVL 树（自平衡二叉查找树）的概念，其通过平衡因子控制左右子树高度差不超过 1。文章详细阐述了 AVL 树的节点结构、插入流程及平衡因子的更新规则。重点讲解了四种旋转操作（左单旋、右单旋、左右双旋、右左双旋）的原理与代码实现，并提供了查找功能和平衡检测的实现示例。最终验证了 AVL 树在增删查改操作中保持 O(logN) 效率的能力。

晚风告白发布于 2026/3/290 浏览
C++ AVL 树详解与实现

AVL 树是最先发明的自平衡二叉查找树，其左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 E. M. Landis，他们在 1962 年的论文中发表了它。

1. AVL 树的概念

在 AVL 树实现中引入一个平衡因子 (balance factor) 的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度。也就是说任何结点的平衡因子等于 0/1/-1。AVL 树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡。

虽然 AVL 树无法做到保证所有子树没有高度差，但每个子树高度差最大就为 2，这就使得 AVL 树整体结点数量和分布和完全二叉树类似，高度以控制在 logN，那么增删查改的效率也可以控制在 O(logN)，相比二叉搜索树有了本质的提升。

2. AVL 树的实现

在了解了 AVL 树的概念以及结构特点之后接下来我们就试着来实现 AVL 树。在此和二叉搜索类似在 AVL 树当中我们依旧会实现插入和查找的功能，但在此 AVL 树中的删除功能就没有实现，原因是在 AVL 树当中删除的功能也是在二叉搜索树的删除基础上进行改进的，但结合了旋转之后就较为复杂。

2.1 AVL 树节点结构实现

在 AVL 树当中每个节点内的信息是和二叉搜索树类似，只不过增加两个变量bf 和_parent 分别表示节点内的平衡因子和指向其父节点的指针，其他的和二叉搜索树类型。

template<class T,class K> struct AVLTreeNode { //使用键值对_val 来存储节点内的数据值 pair<T, K> _val; //left 表示指向该节点左孩子节点的指针 AVLTreeNode<T, K>* _left; //right 表示指向该节点右孩子节点的指针 AVLTreeNode<T, K>* _right; //parent 表示指向该节点父节点的指针 AVLTreeNode<T, K>* _parent; //_bf 内存储节点的平衡因子 int _bf; AVLTreeNode(const pair<T, K>& x) :_val(x) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) { } };

以上结构体 AVLTreeNode 就用于表示 AVL 树的节点，在此实现为类模板可以使得节点内存储任意类型的数据。并且在类当中显示实现构造函数，这样就可以在我们之后创建出节点之后自动的进行初始化的工作。

2.2 AVL 树的结构

在此 AVL 树的结构使用类AVLTree 来封装实现。

template<class T,class K> class AVLTree { //将表示节点的变量重命名，简化书写 typedef AVLTreeNode<T, K> Node; public: //…… private: //root 表示 AVL 树内的根结点指针 Node* root = nullptr; };

2.3 AVL 树插入功能实现

在 AVL 树当中节点插入的步骤其实在前半部分和二叉搜索树节点的插入是完全一样的，只不过是在完成插入之后进行平衡因子的更新；如果当前树的平衡因子绝对值已经超出要求还需要进行旋转的操作。

1. 插入步骤

因此要实现插入的步骤如下：

  1. 插入一个值按二叉搜索树规则进行插入。
  2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子。
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog

更多推荐文章

查看全部
  • 主流C语言开发工具对比：VS/CLion/VSCode/Dev C++选型指南

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online

  • Markdown 转 HTML

    将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online

  • HTML 转 Markdown

    将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online

  • JSON 压缩

    通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online

  • 更新平衡因子过程中没有出现问题，则插入结束。
  • 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。
    • bool Insert(const pair<T, K>& x) {
    if (root == nullptr) {
        root = new Node(x);
        return true;
    }
    Node* cur = root;
    Node* parent = nullptr;
    while (cur) {
        if (cur->_val.first < x.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_val.first > x.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    cur = new Node(x);
    if (parent->_val.first > x.first) {
        parent->_left = cur;
    } else {
        parent->_right = cur;
    }
    cur->_parent = parent;
    // 更新平衡因子操作
    // ……
}

    注：在此我们实现的 AVL 树是不支持冗余的，也就是树当中是不能出现重复元素的，因此在以上查找中如果出现相同值得节点就直接返回 false；表示插入失败。

    2. 平衡因子更新

    更新原则：确定节点的平衡因子 = 右子树高度 - 左子树高度，只有子树高度变化才会影响当前结点平衡因子。当插入结点时，会增加高度，所以新增结点在 parent 的右子树，parent 的平衡因子++，新增结点在 parent 的左子树，parent 平衡因子--，parent 所在子树的高度是否变化决定了是否会继续往上更新。

    更新停止条件总结如下：

    • 更新后 parent 的平衡因子等于 0，说明更新前 parent 子树一边高一边低，插入后 parent 所在的子树高度不变，不会影响 parent 的父亲结点的平衡因子，更新结束。
    • 更新后 parent 的平衡因子等于 1 或 -1，说明更新前 parent 子树两边一样高，插入后 parent 所在的子树一边高一边低，parent 所在的子树符合平衡要求，但是高度增加了 1，会影响 parent 的父亲结点的平衡因子，所以要继续向上更新。
    • 更新后 parent 的平衡因子等于 2 或 -2，说明更新前 parent 子树一边高一边低，新增的插入结点在高的那边，parent 所在的子树高的那边更高了，破坏了平衡，需要旋转处理，旋转后也不需要继续往上更新，插入结束。
    • 不断更新，更新到根，根的平衡因子是 1 或 -1 也停止了。
    3. 旋转

    旋转总共分为四种：左单旋/右单旋/左右双旋/右左双旋。

    1. 右单旋

    当 AVL 树出现以下情况的结构时就需要使用右单旋。在 a 子树中插入一个新结点，导致 a 子树的高度从 h 变成 h+1，不断向上更新平衡因子，导致根节点的平衡因子从 -1 变成 -2，根为根的树左右高度差超过 1，违反平衡规则。根为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。

    //右单旋
void RotateR(Node* Parent) {
    Node* SubL = Parent->_left;
    Node* SubLR = SubL->_right;
    if (SubLR != nullptr) {
        SubLR->_parent = Parent;
    }
    Node* ppNode = Parent->_parent;
    Parent->_left = SubLR;
    Parent->_parent = SubL;
    SubL->_right = Parent;
    if (ppNode != nullptr) {
        if (ppNode->_left == Parent) {
            ppNode->_left = SubL;
        } else {
            ppNode->_right = SubL;
        }
        SubL->_parent = ppNode;
    } else {
        root = SubL;
        SubL->_parent = nullptr;
    }
    Parent->_bf = 0;
    SubL->_bf = 0;
}
    2. 左单旋

    当 AVL 树出现以下情况的结构时就需要使用左单旋。在 a 子树中插入一个新结点，导致 a 子树的高度从 h 变成 h+1，不断向上更新平衡因子，导致根节点的平衡因子从 1 变成 2，根为根的树左右高度差超过 1，违反平衡规则。根为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。

    //左单旋
void RotateL(Node* Parent) {
    Node* SubR = Parent->_right;
    Node* SubRL = SubR->_left;
    if (SubRL != nullptr) {
        SubRL->_parent = Parent;
    }
    Node* ppNode = Parent->_parent;
    Parent->_right = SubRL;
    Parent->_parent = SubR;
    SubR->_left = Parent;
    if (ppNode != nullptr) {
        if (ppNode->_left == Parent) {
            ppNode->_left = SubR;
        } else {
            ppNode->_right = SubR;
        }
        SubR->_parent = ppNode;
    } else {
        root = SubR;
        SubR->_parent = nullptr;
    }
    SubR->_bf = 0;
    Parent->_bf = 0;
}
    3. 左右双旋

    通过下图所示可以看到，左边高时，如果插入位置不是在 a 子树，而是插入在 b 子树，b 子树高度从 h 变成 h+1，引发旋转，右单旋无法解决问题。需要用两次旋转才能解决，以 5 为旋转点进行一个左单旋，以 10 为旋转点进行一个右单旋，这棵树就平衡了。

    //左右双旋
void RotateLR(Node* Parent) {
    Node* SubL = Parent->_left;
    Node* SubLR = SubL->_right;
    int bf = SubLR->_bf;
    RotateL(SubL);
    RotateR(Parent);
    if (bf == 0) {
        SubL->_bf = 0;
        SubLR->_bf = 0;
        Parent->_bf = 0;
    } else if(bf==1) {
        SubL->_bf = -1;
        Parent->_bf = 0;
        SubLR->_bf = 0;
    } else if (bf == -1) {
        SubL->_bf = 0;
        SubLR->_bf = 0;
        Parent->_bf = 1;
    } else {
        assert(false);
    }
}
    4. 右左双旋

    跟左右双旋类似，下面我们将 a/b/c 子树抽象为高度 h 的 AVL 子树进行分析。需要对 b 的父亲 15 为旋转点进行右单旋，右单旋需要动 b 树中的右子树。

    //右左单旋
void RotateRL(Node* Parent) {
    Node* SubR = Parent->_right;
    Node* SubRL = SubR->_left;
    int bf = SubRL->_bf;
    RotateR(SubR);
    RotateL(Parent);
    if (bf == 0) {
        SubR->_bf = 0;
        SubRL->_bf = 0;
        Parent->_bf = 0;
    } else if (bf == 1) {
        SubR->_bf = 0;
        SubRL->_bf = 0;
        Parent->_bf = -1;
    } else if (bf == -1) {
        SubRL->_bf = 0;
        Parent->_bf = 0;
        SubR->_bf = 1;
    } else {
        assert(false);
    }
}
    完整插入代码
    bool Insert(const pair<T, K>& x) {
    if (root == nullptr) {
        root = new Node(x);
        return true;
    }
    Node* cur = root;
    Node* parent = nullptr;
    while (cur) {
        if (cur->_val.first < x.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_val.first > x.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    cur = new Node(x);
    if (parent->_val.first > x.first) {
        parent->_left = cur;
    } else {
        parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent) {
        if (parent->_left == cur) {
            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) {
                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);
            }
            break;
        } else {
            assert(false);
        }
    }
    return true;
}

    2.4 AVL 树查找功能实现

    在此 AVL 树当中的查找和二叉搜索树当中完全一致，在此就不再进行讲解，搜索效率为 O(logN)。

    Node* Find(const T&x) {
    if (root == nullptr) {
        return nullptr;
    }
    Node* cur=root;
    while (cur) {
        if (cur->_val.first < x) {
            cur = cur->_right;
        } else if (cur->_val.first > x) {
            cur = cur->_left;
        } else {
            return cur;
        }
    }
    return nullptr;
}

    2.5 AVL 树平衡检测

    我们实现的 AVL 树是否合格，我们通过检查左右子树高度差的程序进行反向验证，同时检查一下结点的平衡因子更新是否出现了问题。

    void InOrder() { _InOrder(root); cout << endl; }
bool IsBalanceTree() { return _IsBalanceTree(root); }
int Height() { return _Height(root); }
int Size() { return _Size(root); }
private:
void _InOrder(Node* cur) {
    if (cur == nullptr) {
        return;
    }
    _InOrder(cur->_left);
    cout << cur->_val.first <<":" << cur->_val.second << endl;
    _InOrder(cur->_right);
}
int _Height(Node* cur) {
    if (cur == nullptr) {
        return 0;
    }
    int Left = _Height(cur->_left);
    int Right = _Height(cur->_right);
    return Left > Right ? Left + 1 : Right + 1;
}
bool _IsBalanceTree(Node* root) {
    if (root == nullptr) {
        return true;
    }
    int HLeft = _Height(root->_left);
    int HRight = _Height(root->_right);
    int diff = HRight-HLeft;
    if (abs(diff) >= 2) {
        cout << root->_val.first << "高度差异常" << endl;
        return false;
    }
    if (root->_bf != diff) {
        cout << root->_val.first << "平衡因子异常" << endl;
        return false;
    }
    return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
int _Size(Node* cur) {
    if (cur == nullptr) {
        return 0;
    }
    return 1 + _Size(cur->_left) + _Size(cur->_right);
}

    测试用例验证了 AVL 树各个功能都是没问题的，并且通过输出的结果还可以看出在 AVL 树当中的查找效率是很高的。