本文主要介绍AVL树数据结构的详细说明。本文讲解了AVL树的基础知识，AVL树的旋转操作，AVL数的插入和删除操作等。非常详细。有需要的可以参考一下。
1. 概述
AVL树是最早的自平衡二叉树。AVL树中任意一个节点的两个子树的高度差为1，所以也叫高度平衡树。AVL tree以其发明者G.M. Adelson-Velsky和E.M. Landis的名字命名。AVL树种搜索、插入和删除平均为O(log n)，在最坏的情况下。添加和删除可能需要一个或多个树循环来重新平衡此树。介绍了AVL树的设计思想和基本操作。
2. 基本术语
有四种情况可能导致二叉查找树的不平衡，即：
(1)LL:在根节点的左子树的左子树中插入一个新节点，导致根节点的平衡因子从1变为2。
(2)RR:在根节点的右子树的右子树中插入一个新节点，导致根节点的平衡因子从-1变为-2。
(3)LR:在根节点的左子树的右子树中插入一个新节点，导致根节点的平衡因子从1变为2。
(4)RL:在根节点的右子树的左子树中插入一个新节点，导致根节点的平衡因子从-1变为-2。
针对四种情况可能造成的不平衡，可以通过旋转来平衡。旋转有两种基本类型：
(1)向左旋转：将根节点旋转到(根节点的)右子节点的左子节点位置
(2)右旋转：将根节点旋转到(根节点的)左子节点的右子节点位置。
3. AVL树的旋转操作
AVL树的基本操作是旋转，旋转方式有四种，分别是：左旋转、右旋转、左右旋转(先左后右)和左右旋转(先右后左)。其实这四种旋转运算是两两对称的，所以也可以描述为两种旋转运算。
基本数据结构：
复制代码如下：
typedef结构节点*树；
typedef结构节点* Node _ t；
typedef类型int
结构节点{
Node _ t left
Node _ t right
int高度；
类型数据；
};
int Height(Node_t node) {
返回节点高度；
}
3.1 LL
LL情况需要用右手解决，如下图所示：
代码是：
复制代码如下：
Node_t RightRotate(Node_t a) {
b=a-左；
a-左=b-右；
b-右=a；
a-height=Max(高度(a-左)，高度(a-右))；
b-height=Max(高度(b-左)，高度(b-右))；
返回b；
}
3.2 RR
RR需要左手求解，如下图所示：
代码是：
复制代码如下：
Node_t LeftRotate(Node_t a) {
b=a-右；
a-右=b-左；
b-左=a；
a-height=Max(高度(a-左)，高度(a-右))；
b-height=Max(高度(b-左)，高度(b-右))；
返回b；
}
3.3 LR
LR情况需要通过左转右转(先B左转，再A右转)来解决，如下图所示：
代码是：
复制代码如下：
Node _ t left right rotate(Node _ t a){
a-left=left rotate(a-left)；
返回right rotate(a)；
}
3.4 RL
RL需要从右向左求解(先B向右旋转，再A向左旋转)，如下图所示：
代码是：
复制代码如下：
Node _ t right left rotate(Node _ t a){
a-right=right rotate(a-right)；
返回left rotate(a)；
}
4. AVL数的插入和删除操作
(1)插入操作：实际上是在不同的条件下，通过不同的旋转方式对整棵树进行调整。具体代码如下：
复制代码如下：
Node_t插入(类型x，树t) {
if(t==NULL) {
t=new node(x)；
} else if(x t-data) {
t-left=插入(t-left)；
if(Height(t-left)-Height(t-right)==2){
if(x t-left-data) {
t=right rotate(t)；
}否则{
t=LeftRightRotate(t)；
}
}
}否则{
t右=Insert(t右)；
if(Height(t-right)-Height(t-left)==2){
if(x t-right-data) {
t=left rotate(t)；
}否则{
t=RightLeftRotate(t)；
}
}
}
t-height=Max(Height(t-left)，Height(t-right))1；
return t；
}
(2)删除操作：首先定位要删除的节点，然后用该节点的右子节点的最左边的子节点替换该节点，并将该节点中的根子树重新调整为AVL树。具体调整方法类似于插入数据，代码如下：
复制代码代码如下：
节点删除(类型x，树t) {
if(t==NULL)返回NULL
if(t-data==x) {
if(t-right==NULL) {
Node _ t温度=t
t=t-左；
免费（临时);
}否则{
Node_t头=t右；
而(左上){
头=头-左；
}
t-data=head-data；//只复制数据
t-right=Delete(t-data，t-right)；
t-height=Max(Height(t-left)，Height(t-right))1；
}
return t；
} else if(t-data x) {
删除(x，t-right)；
如果(t右)旋转(x，t右);
}否则{
删除(x，t-左)；
如果(t-左)旋转(x，t-左);
}
如果(t)旋转(x，t)；
}
5. 总结
AVL树是最早的自平衡二叉树，相比于后来出现的平衡二叉树（红黑树、处理、张开树)而言，它现在应用较少，但研究AVL树对于了解后面出现的常用平衡二叉树具有重要意义。
6. 参考资料
(1) 数据结构（三)语言版)严蔚敏，吴伟民著
(2)http://zh . Wikipedia . org/wiki/AVL树
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。