C++ AVL 树底层原理与实现

C++ 中 AVL 树的底层原理与实现。AVL 树是一种自平衡二叉搜索树，通过平衡因子控制左右子树高度差不超过 1。文章涵盖了 AVL 树的概念、三大性质、节点结构定义、插入逻辑及四种旋转操作（左单旋、右单旋、左右双旋、右左双旋）以维持平衡。此外还展示了查找、遍历、高度和大小计算等功能的代码实现，并分析了其查找效率高但插入删除涉及旋转操作较复杂的优缺点。

RustyLab发布于 2026/3/27更新于 2026/4/163 浏览

C++ AVL 树底层原理与实现

AVL 树示意图

一、AVL 树的概念

AVL 树是一种高度平衡的平衡二叉树，相比于搜索二叉树，它的特点在于左右子树都为 AVL 树且树的高度差的绝对值不超过 1。

这里我们会引入一个新的概念叫做平衡因子。平衡因子也就是左右子树的高度差，我们可以通过平衡因子方便我们后续去观察和控制树是否平衡。

平衡因子示例

二、AVL 树的性质

AVL 树主要有三大性质：

每棵树的左右子树都是 AVL 树。
左子树和右子树的高度之差的绝对值不超过 1。
每个节点都会有一个平衡因子，且任何一个节点的平衡因子都为 1、0、-1。

三、AVL 树的实现

1. 树的基本结构

AVL 树的结点包含了左右节点的指针以及父亲节点的指针，同时还有 key、value 以及代表树平衡的平衡因子。

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

2. 树的插入

树的插入按照搜索二叉树的规则进行插入。插入节点后更新平衡因子，如果没有违反规则 (即没有导致节点的平衡因子变成 2/-2)，则插入结束；如果违反规则，则树会不平衡，需要进行旋转操作。

平衡因子的更新规则：

平衡因子 = 右子树高度 - 左子树高度。
只有子树高度的变化才会影响当前节点的平衡因子。
插入节点后会增加数的高度，若新增节点在 parent 的右子树，则 parent 的平衡因子 ++，相反在 parent 的左子树时，则平衡因子 --。

每更新完一个节点的平衡因子都需要进行以下判断：

如果 parent 的平衡因子等于 1/-1 时，说明 parent 原先的平衡因子为 0，插入节点后左子树或右子树的高度增加了，说明还需要向上更新平衡因子。

相关免费在线工具

加密/解密文本

使用加密算法（如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

#include <iostream> #include <assert.h> using namespace std; template <class K, class V> struct AVLTreeNode { // 需要 parent 指针，后续更新平衡因子可以看到 pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; // 平衡因子 int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} }; template <class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; // 更新平衡因子 while (parent) { if (cur == parent->_left) { 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); } else { assert(false); } } else { assert(false); } break; } return true; } // 右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (pparent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (pparent == parent->_left) { parent->_left = subL; } else { parent->_right = subL; } subL->_parent = pparent; } parent->_bf = subL->_bf = 0; } // 左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subR; if (subRL) subRL->_parent = parent; Node* pparent = parent->_parent; if (pparent == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (pparent == parent->_right) { parent->_right = subR; } else { parent->_left = subR; } subR->_parent = pparent; } parent->_bf = subR->_bf = 0; } // 左右双旋 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); } } // 右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent); 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) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } } void Inorder() { _Inorder(_root); cout << endl; } void Hight() { return _Hight(_root); } void Size() { return _Size(_root); } private: 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; } int _Size(Node* root) { if (root == nullptr) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1; } 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; } private: Node* _root = nullptr; };

C++ AVL 树底层原理与实现

C++ AVL 树底层原理与实现

一、AVL 树的概念

二、AVL 树的性质

三、AVL 树的实现

1. 树的基本结构

2. 树的插入

更多推荐文章

相关免费在线工具

3. 树的旋转

• 左单旋

• 右单旋

• 左右双旋

• 右左双旋

四、AVL 树的其它功能

1. 树的查找

2. 树的遍历

3. 树的高度

4. 树的大小

五、总结

1. AVL 树的优缺点

2. 完整代码

C++ AVL 树底层原理与实现

C++ AVL 树底层原理与实现

一、AVL 树的概念

二、AVL 树的性质

三、AVL 树的实现

1. 树的基本结构

2. 树的插入

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

更多推荐文章

相关免费在线工具

3. 树的旋转

• 左单旋

• 右单旋

• 左右双旋

• 右左双旋

四、AVL 树的其它功能

1. 树的查找

2. 树的遍历

3. 树的高度

4. 树的大小

五、总结

1. AVL 树的优缺点

2. 完整代码