AVL
AVL-Tree
AVL树简介
一棵AVL树有如下必要条件：
- 它必须是二叉查找树。
- 每个节点的左子树和右子树的高度差至多为1
AVL树的优势
AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。如果我们需要查找的集合本身没有顺序，在频繁查找的同时也经常的插入和删除，AVL树是不错的选择。不平衡的二叉查找树在查找时的效率是很低的。AVL树的相关概念
平衡因子（BF）
将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)最小不平衡树
距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树。结点类型
1
2
3
4
5
6
7
8
9
10template<typename T>
struct AVL_Node {
T data;
int height;
AVL_Node<T>* lchild, * rchild;
//构造函数
AVL_Node():lchild(nullptr),rchild(nullptr),height(0){}
AVL_Node(T d, AVL_Node<T> *l = nullptr,AVL_Node<T> *r=nullptr,int h=0):
data(d),lchild(l),rchild(r),height(0){}
};AVL-Tree类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58template<typename T>
class AVL
{
public:
//=========构造函数和析构函数=========//
AVL():root(nullptr)
{
T item;
while(cin>>item)
{
Insert(root,item);
if(getchar()=='\n') //回车结束输入
break;
}
}
~AVL(){Destroy(root);}
//=========插入函数=========//
bool Insert(T key){return Insert(root,key);}
//=========删除函数=========//
bool Remove(T key){return Remove(root,key);}
//=========高度=========//
int Height(){return Height(root);}
//=========搜查函数(递归)=========//
AVL_Node<T>* SearchRecurse(T key){return SearchRecurse(root,key);}
//=========搜查函数(非递归)=========//
AVL_Node<T>* SearchIterator(T key){return SearchIterator(root,key);}
//=========中序遍历=========//
void InOrder(){InOrder(root);}
//=========广义表输出树=========//
void PrintBinTree(){PrintBinTree(root);}
protected:
AVL_Node<T>* LeftRotation(AVL_Node<T>*);
AVL_Node<T>* RightRotation(AVL_Node<T>*);
AVL_Node<T>* LeftRightRotation(AVL_Node<T>*);
AVL_Node<T>* RightLeftRotation(AVL_Node<T>*);
AVL_Node<T>* Insert(AVL_Node<T>*&,T);
AVL_Node<T>* Remove(AVL_Node<T>*&,T);
AVL_Node<T>* SearchRecurse(AVL_Node<T>*,T);
AVL_Node<T>* SearchIterator(AVL_Node<T>*,T);
int Height(AVL_Node<T>*);
AVL_Node<T>* maxmum(AVL_Node<T>*);
AVL_Node<T>* minmum(AVL_Node<T>*);
void InOrder(AVL_Node<T>*);
void Destroy(AVL_Node<T>*&);
void PrintBinTree(AVL_Node<T>*);
int max(int a,int b){return a>b?a:b;}
private:
AVL_Node<T> *root;
};
实现要点——失衡因子
我们的节点结构中并不存储结点的BF，取而代之的是节点的高度。一个节点的BF可由其左右子树的高度计算出来。我们提供返回一个节点高度的操作1
2
3
4
5
6
7
8int Height(AVL_Node<T>* cur)
{
if(!cur)
return 0;
int i=Height(cur->lchild);
int j=Height(cur->rchild);
return (i<j)?j+1:i+1;
}
实现要点——失衡调整
1.左旋
当我们在右子树插入右孩子导致AVL失衡时，我们需要进行单左旋调整。旋转围绕最小失衡子树的根节点进行。 在删除新节点时也有可能会出现需要单左旋的情况。1
2
3
4
5
6
7
8
9
10AVL_Node<T>* LeftRotation(AVL_Node<T> *cur)
{
auto prchild=cur->rchild;
cur->rchild=prchild->lchild;
prchild->lchild=cur;
//改变了指向，更新结点的高度
cur->height=max(Height(cur->lchild),Height(cur->rchild))+1;
prchild->height=max(Height(prchild->lchild),Height(prchild->rchild))+1;
return prchild;
}
思路：
- 参数cur为最小失衡子树的根节点，在图四中为节点4
- 若节点5有左子树，则该左子树成为节点4的右子树
- 节点4成为节点5的左子树
- 最后更新节点的高度值
PS:新根结点的左子树由当前结点的右子树接受
（根据中序遍历，新根结点原本就是失衡根结点的右子树上的结点，因此新根结点的左子树全部大于失衡根结点，所以可以成为失衡根结点的新右子树）
2.右旋
插入3、2后出现了不平衡的情况。此时的插入情况是“在左子树上插入左孩子导致AVL树失衡”，我们需要进行单右旋调整。1
2
3
4
5
6
7
8
9AVL_Node<T>* RightRotation(AVL_Node<T> *cur)
{
auto plchild=cur->lchild;
cur->lchild=plchild->rchild;
plchild->rchild=cur;
cur->height=max(Height(cur->lchild),Height(cur->rchild))+1;
plchild->height=max(Height(cur->lchild),Height(cur->rchild))+1;
return plchild;
}
3.先右旋后左旋
这种情况，总结起来就是“在右子树上插入左孩子导致AVL树失衡”,此时我们需要进行先右旋后左旋的调整。1
2
3
4
5AVL_Node<T>* RightLeftRotation(AVL_Node<T> *cur)
{
cur->rchild=RightRotation(cur->rchild);
return LeftRotation(cur);
}
思路：
- 首先对最小不平衡子树的根节点（也就是节点6）的右孩子（也就是8）进行右旋操作
- 再对节点6进行一次左旋操作
PS:对右孩子进行右旋操作就是单纯的该结点转移，因为右孩子并未失衡4.先左旋后右旋
当我们“在左子树上插入右孩子导致AVL树失衡”,此时我们需要进行先左旋后右旋的调整.1
2
3
4
5AVL_Node<T>* LeftRightRotation(AVL_Node<T> *cur)
{
cur->lchild=LeftRotation(cur->lchild);
return RightRotation(cur);
}实现要点——插入和删除结点
插入将旋转的情况串联起来即可1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31AVL_Node<T>* Insert(AVL_Node<T>* &cur,T key)
{
if(!cur) //动态分配新结点
{
cur=new AVL_Node<T>(key);
}
else if(key>cur->data) //处理右树
{
cur->rchild=Insert(cur->rchild,key);
if(Height(cur->rchild)-Height(cur->lchild)==2) //失衡
{
if(key>cur->rchild->data) //右右失衡，左旋
cur=LeftRotation(cur);
else if(key<cur->rchild->data) //右左失衡，先右旋后左旋
cur=RightLeftRotation(cur);
}
}
else if(key<cur->data) //处理左树
{
cur->lchild=Insert(cur->lchild,key);
if(Height(cur->lchild)-Height(cur->rchild)==2) //失衡
{
if(key<cur->lchild->data) //左左失衡，右旋
cur=RightRotation(cur);
else if(key>cur->lchild->data) //左右失衡，先左旋后右旋
cur=LeftRightRotation(cur);
}
}
cur->height=max(Height(cur->lchild),Height(cur->rchild))+1; //更新该结点高度
return cur;
}
删除节点也可能导致AVL树的失衡，实际上删除节点和插入节点是一种互逆的操作：
- 删除右子树的节点导致AVL树失衡时，相当于在左子树插入节点导致AVL树失衡，即左左失衡或左右失衡。
- 删除左子树的节点导致AVL树失衡时，相当于在右子树插入节点导致AVL树失衡，即右右失衡或右左失衡。
举个例子：如删除右树结点后失衡，左树需要调整，取处理结点的左结点为参考，它的右子树比左子树高，那么相当于左子树插右孩子导致失衡，左右旋转可以解决，而左子树比右子树高，就相当于左子树插左孩子导致失衡，右旋转可以解决。
另外，AVL树也是一棵二叉排序树，因此在删除节点时也要维护二叉排序树的性质。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62AVL_Node<T>* Remove(AVL_Node<T>* &cur,T key)
{
if(cur)
{
if(key==cur->data) //同二叉搜索树的处理方式
{
if(cur->lchild&&cur->rchild) //左右子树都有
{
if(Height(cur->lchild)>Height(cur->rchild))
//左子树比右子树高
{
auto pmax=maxmum(cur->lchild); //左子树的最大结点
cur->data=pmax->data; //最大结点替代当前节点，维持性质
cur->lchild=Remove(cur->lchild,pmax->data); //删除原来的最大结点
}
else
//右子树比左子树高
//高度相等删哪边都一样
{
auto pmin=minmum(cur->rchild); //右子树的最小结点
cur->data=pmin->data; //最小结点替代当前结点，维持性质
cur->rchild=Remove(cur->rchild,pmin->data); //删除原来的最小结点
}
}
else //只有一个孩子，用孩子替代根结点，没有孩子直接删除
{
auto ptmp=cur; //cur指向的内存由temp接管
if(!cur->lchild)
cur=cur->lchild;
else if(!cur->rchild)
cur=cur->rchild;
delete ptmp; //cur已指向其他内存，删除原本指向的内存
return nullptr;
}
}
else if(key>cur->data) //进入右树
{
cur->rchild=Remove(cur->rchild,key); //在右子树中删除
if(Height(cur->lchild)-Height(cur->rchild)==2) //左子树失衡
{
if(Height(cur->lchild->rchild)>Height(cur->lchild->lchild))
//右子树比左子树高，左右旋转可以调整BF
cur=LeftRightRotation(cur);
else
//左子树比右子树高，右旋可以调整BF
cur=RightRotation(cur);
}
}
else if(key<cur->data) //进入左树
{
cur->lchild=Remove(cur->lchild,key);
if(Height(cur->rchild->lchild)>Height(cur->rchild->rchild))
//左子树比右子树高，右左旋可以调整BF
cur=RightLeftRotation(cur);
else
//右子树比左子树高，左旋可以调整BF
cur=LeftRotation(cur);
}
return cur;
}
return nullptr;
}
查找结点
查找结点就没什么好说的了，直接看代码自然懂。
递归版本
1 | AVL_Node<T>* SearchRecurse(AVL_Node<T> *cur,T key) |
迭代版本
1 | AVL_Node<T>* SearchIterator(AVL_Node<T> *cur,T key) |
销毁AVL树
后续遍历删除AVL树（当然其他遍历也可以删除）1
2
3
4
5
6
7
8
9
10void Destroy(AVL_Node<T>* &cur)
{
if(cur)
{
Destroy(cur->rchild);
Destroy(cur->lchild);
delete cur;
cur=nullptr;
}
}
求最大结点和最小结点
二叉搜索树的最小结点在左子树的最左，最大结点在右子树的最右。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23AVL_Node<T>* maxmum(AVL_Node<T>* cur)
{
if(!cur)
return nullptr;
else
{
while(cur->rchild)
cur=cur->rchild;
return cur;
}
}
AVL_Node<T>* minmum(AVL_Node<T>* cur)
{
if(!cur)
return nullptr;
else
{
while(cur->lchild)
cur=cur->lchild;
return cur;
}
}
完整代码
AVL.h
1 |
|
测试代码main.cpp
1 |
|
