C++算法
C++ 实现 AVL 树：结构、插入与旋转操作详解
本文介绍 C++ 中 AVL 树的实现。AVL 树是一种自平衡二叉查找树，通过平衡因子控制左右子树高度差不超过 1。内容包括节点结构定义、插入操作（含更新平衡因子）、四种旋转操作（左旋、右旋、左右双旋、右左双旋）以恢复平衡，以及查找、高度计算等辅助功能。代码展示了完整实现及测试用例，时间复杂度为 O(log N)。
本文介绍 C++ 中 AVL 树的实现。AVL 树是一种自平衡二叉查找树，通过平衡因子控制左右子树高度差不超过 1。内容包括节点结构定义、插入操作（含更新平衡因子）、四种旋转操作（左旋、右旋、左右双旋、右左双旋）以恢复平衡，以及查找、高度计算等辅助功能。代码展示了完整实现及测试用例，时间复杂度为 O(log N)。
AVL 树是一种自平衡的二叉查找树（BST），由 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年提出。AVL 树的核心特点是它保证树的每个节点的左右子树的高度差（平衡因子）不超过 1，从而保证了 AVL 树在插入、删除和查找操作时的时间复杂度始终为 O(log N)。
每个节点都有一个 平衡因子 (_bf)，它表示节点左子树的高度减去右子树的高度：
平衡因子 = 左子树的高度 - 右子树的高度
AVL 树的自平衡特性确保了其查询、插入和删除操作的最坏时间复杂度为 O(log N)，避免了普通二叉查找树的退化（比如变成链表）。因此，AVL 树非常适用于需要频繁插入和删除操作的场景。
AVL 树的主要操作有：
在实现 AVL 树之前，首先要定义节点结构。每个节点存储以下信息：
_kv)：存储数据 (pair<K, V>)。_left, _right)：指向左右子树。_parent)：指向父节点。_bf)：用于标识该节点的左右子树的高度差。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) {}
};
AVL 树的插入操作包括三步：
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;
}
// 更新插入节点的_parent
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 = cur->_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);
break;
} else {
assert(false);
}
}
return true;
如果某个节点的平衡因子为 2 或 -2，表示该节点不平衡。我们需要通过旋转操作来恢复平衡。旋转操作有四种：
右单旋适用于当左子树较高时，执行旋转操作来恢复平衡。
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
parent->_left = subLR;
if (subLR) {
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root) {
subL->_parent = nullptr;
_root = subL;
} else {
subL->_parent = ppNode;
if (parent == ppNode->_right) ppNode->_right = subL;
else ppNode->_left = subL;
}
parent->_bf = 0;
subL->_bf = 0;
}
左单旋适用于当右子树较高时，执行旋转操作来恢复平衡。
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* ppNode = parent->_parent;
Node* subRL = subR->_left;
parent->_right = subRL;
parent->_parent = subR;
if (subRL) {
subRL->_parent = parent;
}
subR->_left = parent;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
subR->_parent = ppNode;
if (parent == ppNode->_right) ppNode->_right = subR;
else ppNode->_left = subR;
}
parent->_bf = 0;
subR->_bf = 0;
}
当左子树的右子树较高时，首先进行左旋，再进行右旋，恢复平衡。
void RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL); // 左旋
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) {
subL->_bf = subLR->_bf = parent->_bf = 0;
} else {
assert(false);
}
}
总结：找失衡原因，决定如何旋转
Find)查找操作与普通的二叉查找树类似。通过不断比较当前节点的键值和目标值，沿树的路径查找目标节点。
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; // 如果没有找到，返回空
}
该方法的时间复杂度为 O(log N)，因为 AVL 树是平衡的，树的高度是对数级别的。
Height)树的高度指的是从根节点到最远叶子节点的最长路径上的边数。AVL 树的高度是平衡的，计算时我们需要递归地计算左右子树的高度并返回较大的一个。
int Height() {
return _Height(_root); // 从根节点开始计算树的高度
}
int _Height(Node* root) {
if (root == nullptr) return 0; // 空树的高度为 0
int leftHeight = _Height(root->_left); // 递归计算左子树的高度
int rightHeight = _Height(root->_right); // 递归计算右子树的高度
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; // 返回较大值，并加 1
}
该方法的时间复杂度为 O(N)，其中 N 为节点总数。虽然 AVL 树是平衡的，但在计算高度时需要遍历整个树。
Size)节点数量是树中所有节点的总数。通过递归遍历树，计算左右子树的节点数量，并加上当前节点。
int Size() {
return _Size(_root); // 从根节点开始计算树的大小
}
int _Size(Node* root) {
if (root == nullptr) return 0; // 空树节点数量为 0
return _Size(root->_left) + _Size(root->_right) + 1; // 左右子树的节点数量加 1
}
该方法的时间复杂度为 O(N)，需要遍历整个树来计算节点总数。
IsBalanceTree)为了验证 AVL 树的平衡性，我们需要检查每个节点的平衡因子，并确保它们的绝对值不超过 1。如果树的任意节点的平衡因子大于 1 或小于 -1，那么树就不平衡。
bool _IsBalanceTree(Node* root) {
if (root == nullptr) return true; // 空树是平衡的
int leftHeight = _Height(root->_left); // 左子树高度
int rightHeight = _Height(root->_right); // 右子树高度
int diff = leftHeight - rightHeight; // 计算平衡因子
if (abs(diff) >= 2) {
cout << root->_kv.first << "高度差异常" << endl;
return false; // 如果高度差大于等于 2，树不平衡
}
if (root->_bf != diff) {
cout << root->_kv.first << "平衡因子异常" << endl;
return false; // 如果平衡因子与实际高度差不符，树不平衡
}
// 递归检查左右子树是否平衡
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
该方法的时间复杂度为 O(N)，需要递归遍历整个树并计算每个节点的平衡因子。
AVL 树通过保持平衡，保证了插入、查找和删除操作的时间复杂度都为 O(logN)，相比于普通的二叉查找树，AVL 树避免了退化成链表的情况，极大提高了性能。
下面是两个测试代码，用于验证 AVL 树的插入和查找操作。
// 测试代码
void TestAVLTree1() {
AVLTree<int, int> t;
// 常规的测试用例
// int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试用例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a) {
t.Insert({ e, e });
cout << "Insert:" << e << "->";
cout << t.IsBalanceTree() << endl;
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2() {
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(0));
for (int 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 << t.IsBalanceTree() << endl;
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 (int i = 0; i < N; i) {
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
#pragma once
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 {
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 = cur->_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);
break;
} else {
assert(false);
}
}
return true;
}
void InOrder() {
_InOrder(_root);
}
bool IsBalanceTree() {
return _IsBalanceTree(_root);
}
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;
}
int Height() {
return _Height(_root);
}
int Size() {
return _Size(_root);
}
private:
int _Size(Node* root) {
if (root == nullptr) return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
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 _IsBalanceTree(Node* root) {
if (root == nullptr) return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = leftHeight - rightHeight;
if (abs(diff) >= 2) {
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != diff) {
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << " ";
_InOrder(root->_right);
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
parent->_left = subLR;
if (subLR) {
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root) {
subL->_parent = nullptr;
_root = subL;
} else {
subL->_parent = ppNode;
if (parent == ppNode->_right) ppNode->_right = subL;
else ppNode->_left = subL;
}
parent->_bf = 0;
subL->_bf = 0;
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* ppNode = parent->_parent;
Node* subRL = subR->_left;
parent->_right = subRL;
parent->_parent = subR;
if (subRL) {
subRL->_parent = parent;
}
subR->_left = parent;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
subR->_parent = ppNode;
if (parent == ppNode->_right) ppNode->_right = subR;
else ppNode->_left = subR;
}
parent->_bf = 0;
subR->_bf = 0;
}
void RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
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) {
subL->_bf = subLR->_bf = parent->_bf = 0;
} else {
assert(false);
}
}
void RotateRL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 0) {
parent->_bf = subR->_bf = subRL->_bf = 0;
} else if (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 {
assert(false);
}
}
Node* _root = nullptr;
};
// 测试代码
void TestAVLTree1() {
AVLTree<int, int> t;
// 常规的测试用例
// int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试用例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a) {
/*if (e == 14) { int x = 0; }*/
t.Insert({ e, e });
cout << "Insert:" << e << "->";
cout << t.IsBalanceTree() << endl;
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2() {
const int N = 1000000;
vector<int> v;
v.reserve(N);
srand((unsigned int)time(0));
for (int 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 << t.IsBalanceTree() << endl;
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 (int i = 0; i < N; i) {
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;
#include "AVLTree.h"
int main() {
TestAVLTree1();
TestAVLTree2();
return 0;
}
随着数据量的不断增长，如何保持高效的查找与插入操作成为了现代计算机科学的核心问题之一。AVL 树作为一种自平衡二叉查找树，凭借其稳定的时间复杂度和高效的性能，已广泛应用于各类需要动态数据结构支持的场景。未来，随着算法和硬件的进一步发展，AVL 树的实现和优化将迎来更多挑战与机遇。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online