目录
一、什么是AVL树
1.1 AVL树介绍
- AVL树是一种自平衡的二叉搜索树,由G. M. Adelson-Velsky和E. M. Landis在1962年提出。
- AVL树是最先发明的⾃平衡⼆叉查找树,AVL树是⼀颗⾼度平衡搜索⼆叉树,通过控制⾼度差去控制平衡。
- AVL树整体结点数量和分布和完全⼆叉树类似,⾼度可以控制在 logN,那么增删查改的效率也可以控制在O(logN),相⽐⼆叉搜索树有了本质的提升。
AVL树支持常见的二叉搜索树操作,如插入、删除和搜索
- 插入:在AVL树中插入节点时,可能会破坏树的平衡性。为了恢复平衡,需要进行一次或多次旋转操作。根据节点平衡因子的不同,可能需要进行单旋(左旋或右旋)或双旋(先左后右或先右后左)。
- 删除:删除节点时同样可能破坏树的平衡性。通过旋转操作(可能包括单旋和双旋)来恢复平衡。
- 搜索:在AVL树中搜索节点的过程与在普通二叉搜索树中相同,但由于AVL树的高度始终保持在O(log n),因此搜索操作的时间复杂度也是O(log n)。
本文重点讲解插入旋转操作,与搜索二叉树重合的部分详见:数据结构之搜索二叉树-CSDN博客
1.2 AVL树的结构
- 二叉搜索树特性:左子树中所有节点的值小于根节点的值,右子树中所有节点的值大于根节点的值,且左右子树也分别是AVL树。
- 高度平衡:对于任意节点,其左右子树的高度差的绝对值不超过1。
- 平衡因子:每个节点都有一个平衡因子,定义为该节点的左子树高度减去右子树高度的差值。在AVL树中,平衡因子的值只能是0、1或-1(不平衡就要进行旋转操作)。
- 三叉链:三叉链结构在AVL树中指的是每个节点不仅包含指向左右子节点的指针,还包含一个指向其父节点的指针(即_parent)。这种结构使得节点能够直接访问其父节点,从而在进行插入、删除等操作时能够更高效地向上回溯和更新平衡因子。
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
// 需要parent 指针,使得更新平衡因⼦可以向上更新
AVLTreeNode<K, V>* _parent;
int _bf; //平衡因子-balance factor
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0) //新增的节点平衡因子一定为0
{}
};
二、AVL树的插入
2.1 插入过程
- 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。
- 更新平衡因子没有问题则结束
- 更新平衡因子出现不平衡,则旋转
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;
// 更新平衡因⼦
......
}
2.2 更新平衡因子
什么时候更新:
- 只有⼦树⾼度变化才会影响当前结点平衡因⼦。
- 插入在parent节点的右子树,平衡因子++;插入在parent节点的左子树,平衡因子--。
- parent的子树高度变化需要向上更新。
什么时候停止更新:
- 更新后parent的平衡因⼦等于0:说明平衡因子是由-1/1->0变化的,也就说明插入前一边高一边低,插入后左右一样高。整体子树的高度不变,无需向上更新。
- 更新后parent的平衡因⼦等于1 或 -1:说明平衡因子是由0->1/-1变化的,也就说明插入前一样高,插入后一边高一边低。整体子树高度++,需要向上更新。
- 更新后parent的平衡因⼦等于2 或 -2:说明平衡因子是由1->2/-1->-2变化的,也就说明插入前一边高一边低,新节点插入在高的一边,插入后不符合AVL树的规则,需要进行旋转处理
// 更新平衡因⼦
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)
{
// 不平衡了,旋转处理
......
}
else
{
assert(false);
}
}
三、AVL树的旋转
3.1 单旋思路
以左单旋为例讲解,右单旋类比左单旋即可。
- 图中表示的树是广义上的抽象的树:既可以代表整棵树也可以代表其中一颗子树。模糊掉了子树的节点组成,仅关注的是不平衡的节点
- 旋转核心:b树的根节点值介于6和9之间,旋转是将b作为6的右子树,6作为9的左子树。从而实现整体高度的降低
3.2 单旋代码
根据上述图示,生成基本的代码
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
subR->_left = parent;
parent->_parent = subR;
}
但是,旋转实际上会破坏原来的三叉链的结构,旋转后的平衡因子也需要更新。所以进一步完善代码。
三叉链更新:
- 如果subRL也就是图中的b树为空,subRL没有父亲指针,不需要更新。只有在subRL不为空时,才需要将subRL的_parent->parent。
- 如果parent是整棵树的根节点:那么旋转后新的节点为subR,subR的_parent->nullptr
- 如果parent不是整棵树的根节点:那么subR的_parent就要指向原来parent的parent。
平衡因子更新:
由图示可知,旋转后只有parent和subR的平衡因子发生变化,且都变为0
//左旋源代码
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* Pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
/*调整旋转后树的结构符合树的基本原则*/
//1.整棵树的根
if (parent==_root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (Pparent->_left == parent)
{
Pparent->_left = subR;
}
else
{
Pparent->_right = subR;
}
subR->_parent = Pparent;
}
//更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}
//右旋源代码
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;
/*调整旋转后树的结构符合树的基本原则*/
//1.整棵树的根
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
//2.局部子树的根
else
{
if (Pparent->_left == parent)
{
Pparent->_left = subL;
}
else
{
Pparent->_right = subL;
}
subL->_parent = Pparent;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}
3.3 为什么要双旋
单旋的情况我们只考虑了左边高插在子树的左边/右边高插在子树的右边。那么左边高插在子树的右边还能否用单旋的思路解决?
很明显,采用单旋的思路是错误的。
双旋才能解决此类问题
3.4 双旋思路
以先右旋再左旋为例进行分析,先左旋后右旋类比即可。
上述图已经展示了双旋的基本思路,但是双旋的难点还在于平衡因子的更新。需要分为三种情况进行分析:
- 插在x子树,parent的平衡因子=0,subR的平衡因子=1,subRL的平衡因子=0。
- 插在y子树,parent的平衡因子=-1.subR的平衡因子=0,subRL的平衡因子=0。
- h == 0时,a/x/y/c都是空树,旋转后平衡因子都为0。
3.5 双旋代码
由上述思路可知:需要保存subRL的平衡因子作为判断情况1,2,3的依据
//先右后左
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//更新平衡因子
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
//先左后右
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);
}
}
四、C++源代码
源代码:AVL.h
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
// 需要parent 指针,使得更新平衡因⼦可以向上更新
AVLTreeNode<K, V>* _parent;
int _bf; //平衡因子-balance factor
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0) //新增的节点平衡因子一定为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);
}
break;
}
else
{
assert(false);
}
}
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;
/*调整旋转后树的结构符合树的基本原则*/
//1.整棵树的根
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
//2.局部子树的根
else
{
if (Pparent->_left == parent)
{
Pparent->_left = subL;
}
else
{
Pparent->_right = subL;
}
subL->_parent = Pparent;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* Pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
/*调整旋转后树的结构符合树的基本原则*/
//1.整棵树的根
if (parent==_root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (Pparent->_left == parent)
{
Pparent->_left = subR;
}
else
{
Pparent->_right = subR;
}
subR->_parent = Pparent;
}
//更新平衡因子
subR->_bf = 0;
parent->_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->_right);
RotateL(parent);
//更新平衡因子
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
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;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " : " << root->_kv.second << endl;
_InOrder(root->_right);
}
Node* _root = nullptr;
};
测试:test.cpp
#include"AVL.h"
void test1()
{
AVLTree<int, int> av;
// 常规的测试⽤例
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)
{
av.Insert({ e, e });
}
av.InOrder();
}
void test2()
{
AVLTree<int, int> av;
// 特殊的带有双旋场景的测试⽤例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
av.Insert({ e, e });
}
av.InOrder();
}
int main()
{
cout << "单旋测试" << endl;
test1();
cout << "双旋测试" << endl;
test2();
return 0;
}