从结构到操作：手撕 AVL 树的实现
一、AVL 树介绍
1.1 什么是 AVL 树
AVL 树是一种自平衡的二叉查找树（BST），由 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年提出。AVL 树的核心特点是它保证树的每个节点的左右子树的高度差（平衡因子）不超过 1，从而保证了 AVL 树在插入、删除和查找操作时的时间复杂度始终为 O(log N)。
1.2 平衡因子的定义
每个节点都有一个 平衡因子 (_bf)，它表示节点左子树的高度减去右子树的高度：
平衡因子 = 左子树的高度 - 右子树的高度
- 如果平衡因子为 0，表示左右子树的高度相等。
- 如果平衡因子为 1，表示左子树比右子树高 1。
- 如果平衡因子为 -1，表示右子树比左子树高 1。
1.3 平衡的意义
AVL 树的自平衡特性确保了其查询、插入和删除操作的最坏时间复杂度为 O(log N)，避免了普通二叉查找树的退化（比如变成链表）。因此，AVL 树非常适用于需要频繁插入和删除操作的场景。
1.4 AVL 树的操作
AVL 树的主要操作有：
- 插入操作：在树中插入节点，并在插入后调整平衡因子。如果平衡因子为 2 或 -2，执行旋转操作恢复平衡。
- 删除操作：删除节点，并且在删除节点后，可能需要调整树的结构以保持平衡。由于 AVL 树的删除操作涉及复杂的旋转和调整，因此在本文中我们不会详细讲解该操作。如果你希望深入了解，可以参考《算法导论》中的相关章节来获取详细内容。
- 查找操作：通过比较节点值来查找特定的元素。
- 旋转操作：当树失衡时，使用旋转来恢复平衡，常见的旋转有左旋、右旋、左右旋和右左旋。
二、AVL 树的节点结构
在实现 AVL 树之前，首先要定义节点结构。每个节点存储以下信息：
- 键值对 (
_kv)：存储数据 (pair<K, V>)。 - 左右子树指针 (
_left,_right)：指向左右子树。 - 父节点指针 (
_parent)：指向父节点。 - 平衡因子 (
_bf)：用于标识该节点的左右子树的高度差。
2.1 节点结构的定义：
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) {}
};
三、插入操作
3.1 插入操作概述
AVL 树的插入操作包括三步：
- 按二叉查找树规则插入节点；
- 更新每个节点的平衡因子；
- 如果需要，进行旋转操作 来恢复树的平衡。
bool Insert(const pair<K, V>& kv);
3.2 步骤 1：按二叉查找树规则插入节点
在插入节点时，我们根据值的大小，递归地找到插入位置，并在该位置插入新节点：
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;
3.3 步骤 2：更新平衡因子
插入节点后，我们从新插入的节点开始，逐步更新路径上每个节点的平衡因子。插入时会对父节点的平衡因子进行调整：
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;
3.4 步骤 3：旋转操作详解
如果某个节点的平衡因子为 2 或 -2，表示该节点不平衡。我们需要通过旋转操作来恢复平衡。旋转操作有四种：
- 右单旋 (RotateR)
- 左单旋 (RotateL)
- 左右双旋 (RotateLR)
- 右左双旋 (RotateRL)
3.4.1 右单旋
右单旋适用于当左子树较高时，执行旋转操作来恢复平衡。
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;
}
3.4.2 左单旋
左单旋适用于当右子树较高时，执行旋转操作来恢复平衡。
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;
}
3.4.3 左右双旋
当左子树的右子树较高时，首先进行左旋，再进行右旋，恢复平衡。
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);
}
}
总结：找失衡原因，决定如何旋转
- 左子树的左子树高：进行 R
- 右子树的右子树高：进行 L
- 左子树的右子树高：进行 LR
- 右子树的左子树高：进行 RL
四、其他操作
4.1 查找操作 (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 树是平衡的，树的高度是对数级别的。
4.2 计算树的高度 (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 树是平衡的，但在计算高度时需要遍历整个树。
4.3 计算节点数量 (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)，需要遍历整个树来计算节点总数。
4.4 树是否平衡 (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)，需要递归遍历整个树并计算每个节点的平衡因子。
五、性能分析与测试
5.1 性能分析
AVL 树通过保持平衡，保证了插入、查找和删除操作的时间复杂度都为 O(logN)，相比于普通的二叉查找树，AVL 树避免了退化成链表的情况，极大提高了性能。
5.2 测试代码
下面是两个测试代码，用于验证 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 ( e : v) {
t.((e, e));
}
end2 = ();
cout << t.() << endl;
cout << << end2 - begin2 << endl;
cout << << t.() << endl;
cout << << t.() << endl;
begin1 = ();
( i = ; i < N; i) {
t.((() + i));
}
end1 = ();
cout << << end1 - begin1 << endl;
}
六、全部代码
AVLTree.h
#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;
} {
parent->_left = cur;
}
cur->_parent = parent;
(parent) {
(cur == parent->_left) {
parent->_bf++;
} {
parent->_bf--;
}
(parent->_bf == ) {
;
} (parent->_bf == || parent->_bf == ) {
cur = parent;
parent = cur->_parent;
} (parent->_bf == || parent->_bf == ) {
(parent->_bf == && cur->_bf == ) {
(parent);
} (parent->_bf == && cur->_bf == ) {
(parent);
} (parent->_bf == && cur->_bf == ) {
(parent);
} (parent->_bf == && cur->_bf == ) {
(parent);
} ();
;
} {
();
}
}
;
}
{
_InOrder(_root);
}
{
_IsBalanceTree(_root);
}
{
Node* cur = _root;
(cur) {
(cur->_kv.first < key) cur = cur->_right;
(cur->_kv.first > key) cur = cur->_left;
cur;
}
;
}
{
_Height(_root);
}
{
_Size(_root);
}
:
_Size(Node* root) {
(root == ) ;
_Size(root->_left) + _Size(root->_right) + ;
}
_Height(Node* root) {
(root == ) ;
leftHeight = _Height(root->_left);
rightHeight = _Height(root->_right);
leftHeight > rightHeight ? leftHeight + : rightHeight + ;
}
_IsBalanceTree(Node* root) {
(root == ) ;
leftHeight = _Height(root->_left);
rightHeight = _Height(root->_right);
diff = leftHeight - rightHeight;
((diff) >= ) {
cout << root->_kv.first << << endl;
;
}
(root->_bf != diff) {
cout << root->_kv.first << << endl;
;
}
_IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
_InOrder(Node* root) {
(root == ) {
;
}
_InOrder(root->_left);
cout << root->_kv.first << << root->_kv.second << ;
_InOrder(root->_right);
}
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
parent->_left = subLR;
(subLR) {
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
(parent == _root) {
subL->_parent = ;
_root = subL;
} {
subL->_parent = ppNode;
(parent == ppNode->_right) ppNode->_right = subL;
ppNode->_left = subL;
}
parent->_bf = ;
subL->_bf = ;
}
{
Node* subR = parent->_right;
Node* ppNode = parent->_parent;
Node* subRL = subR->_left;
parent->_right = subRL;
parent->_parent = subR;
(subRL) {
subRL->_parent = parent;
}
subR->_left = parent;
(parent == _root) {
_root = subR;
subR->_parent = ;
} {
subR->_parent = ppNode;
(parent == ppNode->_right) ppNode->_right = subR;
ppNode->_left = subR;
}
parent->_bf = ;
subR->_bf = ;
}
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
bf = subLR->_bf;
(subL);
(parent);
(bf == ) {
subLR->_bf = ;
subL->_bf = ;
parent->_bf = ;
} (bf == ) {
subLR->_bf = ;
subL->_bf = ;
parent->_bf = ;
} (bf == ) {
subL->_bf = subLR->_bf = parent->_bf = ;
} {
();
}
}
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
bf = subRL->_bf;
(subR);
(parent);
(bf == ) {
parent->_bf = subR->_bf = subRL->_bf = ;
} (bf == ) {
subRL->_bf = ;
parent->_bf = ;
subR->_bf = ;
} (bf == ) {
subRL->_bf = ;
parent->_bf = ;
subR->_bf = ;
} {
();
}
}
Node* _root = ;
};
{
AVLTree<, > t;
a[] = { , , , , , , , , , };
( e : a) {
t.({ e, e });
cout << << e << ;
cout << t.() << endl;
}
t.();
cout << t.() << endl;
}
{
N = ;
vector<> v;
v.(N);
(( )());
( i = ; i < N; i) {
v.(() + i);
}
begin2 = ();
AVLTree<, > t;
( e : v) {
t.((e, e));
}
end2 = ();
cout << t.() << endl;
cout << << end2 - begin2 << endl;
cout << << t.() << endl;
cout << << t.() << endl;
begin1 = ();
( i = ; i < N; i) {
t.((() + i));
}
end1 = ();
cout << << end1 - begin1 << endl;
}
Test.cpp
#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 树的实现和优化将迎来更多挑战与机遇。
