C++进阶——AVL树的实现
1、AVL的概念
1.1 AVL 树的发明
AVL 树由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年的论文《An algorithm for the organization of information》中提出。他们的设计目标是解决二叉搜索树在动态操作（插入、删除）中可能退化为链表的问题。
1.2 AVL 树的定义
AVL 树是一种自平衡二叉搜索树，满足以下性质：
-
它是一棵空树，或者：
-
它的左右子树都是 AVL 树。
-
左右子树的高度差(平衡因子)的绝对值 <= 1。
-
1.3 平衡因子
平衡因子（Balance Factor）是 AVL 树的核心概念：
-
定义：某个节点的平衡因子 = 右子树的高度 - 左子树的高度。
-
平衡因子的取值范围：-1、0、1。
-
如果某个节点的平衡因子的绝对值超过 1，则该节点不平衡，需要通过旋转操作进行调整。
1.4 为什么高度差 <= 1 ？
高度差为 0 表示左右子树的高度相等，这种理想状态在某些情况下是无法实现的。
-
例如：
-
当树的节点数为 2 时，高度差只能为 1。
-
当树的节点数为 4 时，高度差也只能为 1。
-
-
如果强制要求高度差为 0，会导致树的结构过于严格，难以在动态操作中保持平衡。
1. 5 AVL 树的性能
AVL 树的性能优势主要体现在其高度平衡性：
-
高度控制：AVL 树的高度 始终保持在 O(logN)。
-
操作效率：插入、删除、查找等操作的时间复杂度均为 O(logN)。
2、AVL树的实现
2.1 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; // 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:
// ……
private:
Node* _root = nullptr;
}2.2 AVL树的插入
2.2.1 AVL树插入一个值的大概过程
1. 按二叉搜索树规则进行插入一个值。
2. 新增结点，只会影响祖先(或部分祖先)结点的高度，也就是会影响祖先(或部分祖先)结点的平衡因子，所以更新 从新增结点->根结点路径上的平衡因子。实际中最坏情况下要更新到根，有些情况更新到中间就可以结束了。
3. 更新平衡因子过程中出现不平衡(平衡因子的绝对值超过 1)，对不平衡子树 旋转，旋转后本质调平衡的同时，降低了子树的高度，不会再影响上一层，所以插入结束。
2.2.2 平衡因子的更新
更新原则：
1. 平衡因子的定义
平衡因子 = 右子树高度 - 左子树高度。
2. 影响平衡因子的条件
只有子树高度变化 才会影响当前节点的平衡因子。
3. 插入节点对平衡因子的影响
-
如果新增节点在parent的右子树，parent的平衡因子++。
-
如果新增节点在parent的左子树，parent的平衡因子--。
更新情况：
1. 更新后parent的平衡因子 等于 0
因为插入前，就是平衡搜索树，平衡因子只能是-1，0，1，所以一定是从-1或1变成0，子树整体的
高度不变，结束更新。
2. 更新后parent的平衡因子 等于 1 或 -1
一定是从0变成-1或1，子树整体的高度变化，继续更新。
3. 更新后parent的平衡因子等于 2 或 -2
一定是从-1变成-2或1变成2，parent高的子树更高了，不平衡了。
通过旋转，平衡(即降低树的高度)，并使子树的根的平衡因子为0。
即-1->-2(旋转)->0，或1->2(旋转)->0，相当于子树的高度没变，结束更新。
4. 更新到根节点
如果更新到根节点，且根节点的平衡因子为 1 或 -1，结束更新。因为根的parent为nullptr，不用更
新了。
2.2.3 插入的代码实现
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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 更新平衡因子
while (parent) // parent = nullptr,为根节点的父亲,结束更新
{
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)
{
// 旋转
break;
}
else
{
assert(false);
}
}
return true;
}2.3 旋转
2.3.1 旋转的原则
1. 保持搜索树的规则。
2. 让旋转的树从不平衡变平衡，其次降低旋转树的高度。
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
2.3.2 右单旋
即左侧高，右侧的parent旋下来。平衡因子同号。
a,b,c子树为抽象表示，实际上有非常多种情况。
a子树自己不旋转，高度+1，将subLR给parent的左，再将parent给subL的右。
注意：
当h = 0时，subLR为nullptr。
parent如果是局部子树的根，就改变连接关系，如果是根，就改变根。
2.3.3 右单旋的代码实现
void RotateR(Node* parent)
{
Node* pParent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
subL->_parent = pParent;
if (pParent == nullptr) // 当pParent == nullptr时,_root == parent
{
_root = subL;
}
else
{
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
}
subL->_bf = 0;
parent->_bf = 0;
}2.3.4 左单旋
即右侧高，左侧的parent旋下来。平衡因子同号。
a子树自己不旋转，高度+1，将subRL给parent的右，再将parent给subR的左。
注意：
当h = 0时，subRL为nullptr。
parent如果是局部子树的根，就改变连接关系，如果是根，就改变根。
2.3.5 左单旋的代码实现
void RotateL(Node* parent)
{
Node* pParent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
subR->_parent = pParent;
if (pParent == nullptr)
_root = subR;
else
{
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
}
subR->_bf = 0;
parent->_bf = 0;
}2.3.6 左右双旋
即中间高，右侧的parent旋下来。平衡因子异号。
从过程上，是对subL进行左旋，parent进行右旋。
从结果上，subLR的左给subL的右，subLR的右给parent的左，subLR自己做根。
subLR的左为subL，右为parent。
平衡后分三种情况，即有三种情况的平衡因子。
2.3.7 左右双旋的代码实现
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int _bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (_bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (_bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (_bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}2.3.8 右左双旋
即中间高，左侧的parent旋下来。平衡因子异号。
从过程上，是对subR进行右旋，parent进行左旋。
从结果上，subRL的左给parent的右，subRL的右给subR的左，subRL自己做根。
subRL的左为parent，右为subR。
平衡后分三种情况，即有三种情况的平衡因子。
2.3.9 右左双旋的代码实现
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 = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (_bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (_bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
assert(false);
}
}2.4 AVL树的查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}2.5 AVL树的平衡检测
bool _IsBalanceTree(Node* root, int& height) { // 后序
// 空树是 AVL 树
if (nullptr == root) {
height = 0;
return true;
}
// 递归检查左子树
int leftHeight = 0;
bool isLeftBalanced = _IsBalanceTree(root->_left, leftHeight);
// 递归检查右子树
int rightHeight = 0;
bool isRightBalanced = _IsBalanceTree(root->_right, rightHeight);
// 当前节点的高度
height = max(leftHeight, rightHeight) + 1;
// 计算平衡因子
int diff = rightHeight - leftHeight;
// 检查平衡因子是否异常
if (abs(diff) >= 2) {
cout << root->_kv.first << " 高度差异常" << endl;
return false;
}
// 检查当前节点的平衡因子是否正确
if (root->_bf != diff) {
cout << root->_kv.first << " 平衡因子异常" << endl;
return false;
}
// 如果左右子树都是 AVL 树，且当前节点也平衡，则整棵树是 AVL 树
return isLeftBalanced && isRightBalanced;
}2.6 AVL树的删除
2.7 AVL的代码实现
2.7.1 AVLTree.h
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace Lzc
{
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; // 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 (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (kv.first > parent->_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 RotateR(Node* parent)
{
Node* pParent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
subL->_parent = pParent;
if (pParent == nullptr) // 当pParent == nullptr时,_root == parent
{
_root = subL;
}
else
{
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
}
subL->_bf = 0;
parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* pParent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
subR->_parent = pParent;
if (pParent == nullptr)
_root = subR;
else
{
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
}
subR->_bf = 0;
parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int _bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (_bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (_bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (_bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_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 = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (_bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (_bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
void InOrder()
{
_InOrder(_root);
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
bool IsBalanceTree()
{
int height = 0;
return _IsBalanceTree(_root, height);
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
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;
}
bool _IsBalanceTree(Node* root, int& height) { // 后序
// 空树是 AVL 树
if (nullptr == root) {
height = 0;
return true;
}
// 递归检查左子树
int leftHeight = 0;
bool isLeftBalanced = _IsBalanceTree(root->_left, leftHeight);
// 递归检查右子树
int rightHeight = 0;
bool isRightBalanced = _IsBalanceTree(root->_right, rightHeight);
// 当前节点的高度
height = max(leftHeight, rightHeight) + 1;
// 计算平衡因子
int diff = rightHeight - leftHeight;
// 检查平衡因子是否异常
if (abs(diff) >= 2) {
cout << root->_kv.first << " 高度差异常" << endl;
return false;
}
// 检查当前节点的平衡因子是否正确
if (root->_bf != diff) {
cout << root->_kv.first << " 平衡因子异常" << endl;
return false;
}
// 如果左右子树都是 AVL 树，且当前节点也平衡，则整棵树是 AVL 树
return isLeftBalanced && isRightBalanced;
}
Node* _root = nullptr;
};
}2.7.2 Test.cpp
#include "AVLTree.h"
#include <vector >
namespace Lzc
{
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 });
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2() {
const int N = 100000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t 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 << "Insert:" << end2 - begin2 << endl;
// 测试平衡性、高度和大小
cout << "IsBalanceTree:" << t.IsBalanceTree() << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
// 测试查找性能
size_t begin1 = clock();
// 查找已存在的值
/*for (auto e : v) {
t.Find(e);
}*/
// 查找随机值
for (size_t i = 0; i < N; i++) {
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
}
int main()
{
Lzc::TestAVLTree1();
// Lzc::TestAVLTree2();
return 0;
}