也许二杈树是很好用的，在插入和查找的时候时间复杂度一般为O（logN），但如果左右子树失去平衡，也可能达到O（N）。为了防止这种现象发生，一种解决办法是是左右子树尽量保持平衡，即建立一种平衡有序树AVL树。
一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二杈有序树。空树的高度定义为-1。
AVL树的结点声明；
typedef struct avlnode
{
int height;//比普通二杈有序树多了一个高度信息
ElemType data;
struct bnode *lchild, *rchild;
} *AvlTree, *Position;
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);
//----------AVL树基本操作的算法实现--------------------
递归算法：
Position FindMin(AvlTree T)
{
if(T==NULL)
return NULL;
else if(T->lchild == NULL)
return T;
else
return FindMin(T->lchild);
}
Position FindMax(AvlTree T)
{
if(T==NULL)
return NULL;
else if(T->rchild == NULL)
return T;
else
return FindMax(T->rchild);
}
非递归算法：
Position FindMin(AvlTree T)
{
if(T!=NULL)
{
while(T->lchild != NULL)
T = T->lchild;
}
return T;
}
Position FindMax(AvlTree T)
{
if(T!=NULL)
{
while(T->rchild != NULL)
T = T->rchild;
}
return T;
}
//返回P点的高度
static int Height(Position P)
{
if(P==NULL)
return -1;
else
return P->height;
}
//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，
这里用到了“单旋转”或“双旋转”的算法，分别适用于：
单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入
单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入
双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入
双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入
static Position SingleRotateWithLeft(Position K2)
{
Position K1;
K1 = K2->lchild; //在K2和K1之间进行一次单左旋转
K2->lchild = K1->rchild;
K1->rchild = K2;
K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
return K1;
}
static Position SingleRotateWithRight(Position K2)
{
Position K1;
K1 = K2->rchild; //在K2和K1之间进行一次单右旋转
K2->rchild = K1->lchild;
K1->lchild = K2;
K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
return K1;
}
static Position DoubleRotateWithLeft(Position K3)
{
K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转
return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}
static Position DoubleRotateWithRight(Position K3)
{
K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转
return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}
//向AVL树插入结点的操作
AvlTree Insert(float x, AvlTree T)
{
if(T == NULL)
{
T = (Position)malloc(sizeof(struct avlnode));
if(T == NULL)
{
puts("wrong");
exit(1);
}
T->data = x;
T->height = 0;
T->lchild = T->rchild = NULL;
}
else if(T->data == x)//不做任何插入操作
;
else if(T->data > x)//把s所指结点插入到左子树中
{
T->lchild = Insert(x, T->lchild);
if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏
{
if(x < T->lchild->data) //若x比T的左孩子小，对T单左旋转
T = SingleRotateWithLeft(T);
else //否则，对T双左旋转
T = DoubleRotateWithLeft(T);
}
}
else //把s所指结点插入到右子树中
{
T->rchild = Insert(x, T->rchild);
if(Height(T->rchild) - Height(T->lchild) == 2)
{
if(x > T->rchild->data) //若x比T的右孩子大，对T单右旋转
T = SingleRotateWithRight(T);
else //否则，对T双右旋转
T = DoubleRotateWithRight(T);
}
}
T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;
return T;
}
int Max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
还有一种AVL树，它的结构中不包含高度特征，但包含一个平衡因子bf，用来判断结点的平衡性，若左孩子比右孩子高，则bf==1；否则，bf==-1；若左右相等则bf==0。
AVL树的结点声明；
enum BALANCE{LH = 1, EH = 0, RH = -1};
typedef struct avlnode
{
BALANCE bf;//比普通二杈有序树多了一个平衡因子信息
ElemType data;
struct avlnode *lchild, *rchild;
} *AvlTree, *Position;
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);
//----------AVL树基本操作的算法实现--------------------
//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，
这里用到了“单旋转”或“双旋转”的算法，分别适用于：
单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入
单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入
双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入
双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入
Position SingleRotateWithLeft(Position K2)
{
Position K1;
K1 = K2->lchild; //在K2和K1之间进行一次单左旋转
K2->lchild = K1->rchild;
K1->rchild = K2;
return K1;
}
Position SingleRotateWithRight(Position K2)
{
Position K1;
K1 = K2->rchild; //在K2和K1之间进行一次单右旋转
K2->rchild = K1->lchild;
K1->lchild = K2;
return K1;
}
Position DoubleRotateWithLeft(Position K3)
{
K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转
return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}
Position DoubleRotateWithRight(Position K3)
{
K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转
return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}
AvlTree LeftBalance(AvlTree T) //左平衡处理
{
AvlTree lT = T->lchild;
switch (lT->bf) //检查左树的平衡度，并做相应处理
{
case LH : T = SingleRotateWithLeft(T); //若新结点插入在T的左孩子的左子树上，对T单左旋转
T->bf = lT->bf = EH; //重新设置平衡度
break;
case RH : AvlTree rT = lT->rchild;//若新结点插入在T的左孩子的右子树上，对T双左旋转，并重新设置平衡度
switch (rT->bf)
{
case LH : T->bf = RH;
lT->bf = EH;
break;
case EH : T->bf = lT->bf = EH;
break;
case RH : T->bf = EH;
lT->bf = LH;
break
}
rT->bf = EH;
T = DoubleRotateWithLeft(T);
break;
}
return T;
}
AvlTree RightBalance(AvlTree T) //右平衡处理
{
AvlTree rT = T->rchild;
switch (rT->bf) //检查右树的平衡度，并做相应处理
{
case LH : T = SingleRotateWithRight(T); //若新结点插入在T的右孩子的右子树上，对T单右旋转
T->bf = rT->bf = EH; //重新设置平衡度
break;
case RH : AvlTree lT = rT->lchild;//若新结点插入在T的右孩子的左子树上，对T双右旋转，并重新设置平衡度
switch (lT->bf)
{
case LH : T->bf = EH;
rT->bf = RH;
break;
case EH : T->bf = rT->bf = EH;
break;
case RH : T->bf = LH;
rT->bf = EH;
break
}
lT->bf = EH;
T = DoubleRotateWithRight(T);
break;
}
return T;
}
//向AVL树插入结点的操作
AvlTree Insert(ElemType x, AvlTree T, bool & taller)
{
if(T == NULL)
{
T = (Position)malloc(sizeof(struct avlnode));
if(T == NULL)
{
puts("wrong");
exit(1);
}
T->data = x;
T->lchild = T->rchild = NULL;
T->bf = EH;
taller = true; //插入新结点，树“长高”，置taller为真值
}
else if(T->data == x)//不做任何插入操作
taller = false; //树未长高，置taller为假值
else if(T->data > x)//把x插入到左子树中
{
T->lchild = Insert(x, T->lchild, taller);
if (taller)//已经插入左子树，且树“长高”，需要检查平衡度，并做相应处理
{
switch(T->bf)
{
case LH : T = LeftBalance(T);//原本左树高于右树，需做左平衡处理，树高不变
taller = false;
break;
case EH : T->bf = LH;//原本左右等高，现在左高于右，且树“长高”
taller = true;
break;
case RH : T->bf = EH; //原本右树高于左树，现在左右等高，树高不变
taller = false;
break;
}
}
}
else //把x插入到右子树中，仿照处理左树的方法处理
{
T->rchild = Insert(x, T->rchild, taller);
if (taller)
{
switch(T->bf)
{
case LH : T->bf = EH;
taller = false;
break;
case EH : T->bf = RH;
taller = true;
break;
case RH : T = RightBalance(T);
taller = false;
break;
}
}
}
return T;
}
AVL树应用示例:
/*输入一组数,存储到AVL树中,并进行输出*/
#include <iostream>
using namespace std;
#define MAX 100
enum BALANCE{LH = 1, EH = 0, RH = -1};
typedef struct avlnode
{
BALANCE bf;//比普通二杈有序树多了一个平衡因子信息
int data;
struct avlnode *lchild, *rchild;
} *AvlTree, *Position;
int Input(int a[]);//输入数据到数组,未排序
void Print(const int a[], int len); //输入未排序的原始数据
AvlTree Sort(AvlTree A, const int a[], int len); //对数据进行排序
AvlTree Insert(int x, AvlTree T, bool & taller); //把数据存储到AVL树中
Position SingleRotateWithLeft(Position K2); //单左旋转
Position SingleRotateWithRight(Position K2); //单右旋转
Position DoubleRotateWithLeft(Position K3);//双左旋转
Position DoubleRotateWithRight(Position K3);//双右旋转
AvlTree LeftBalance(AvlTree T);// 左平衡处理
AvlTree RightBalance(AvlTree T); //右平衡处理
void inorder(const AvlTree bt); //中序遍历AVL树
void PrintBT(AvlTree bt); //输出二杈树
int main(void)
{
int a[MAX]={0};
int len;
AvlTree A=NULL;
len = Input(a);
Print(a, len);
printf("\n");
A = Sort(A, a, len);
PrintBT(A);
printf("\n");
inorder(A);
system("pause");
return 0;
}
int Input(int a[])
{
int i=0;
do{
a[i++] = rand()%1000;//输入随机数
} while(i<MAX);
return i;
}
void Print(const int a[], int len)
{
int i;
for(i=0; i<len; i++)
printf("%d\t", a[i]);
}
AvlTree Sort(AvlTree A, const int a[], int len)
{
int i;
bool taller = false;
for(i=0; i<len; i++)
A = Insert(a[i], A, taller);
return A;
}
void inorder(const AvlTree bt)
{
AvlTree p=bt, stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=-1;
do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
p = stack[top--];//栈顶元素出栈
printf("%d\t", p->data); //输出该结点
p = p->rchild; //处理其右孩子结点
}
} while((p != NULL)||(top >= 0));
}
//向AVL树插入结点的操作
AvlTree Insert(int x, AvlTree T, bool & taller)
{
if(T == NULL)
{
T = (Position)malloc(sizeof(struct avlnode));
if(T == NULL)
{
puts("wrong");
exit(1);
}
T->data = x;
T->lchild = T->rchild = NULL;
T->bf = EH;
taller = true; //插入新结点，树“长高”，置taller为真值
}
else if(T->data == x)//不做任何插入操作
taller = false; //树未长高，置taller为假值
else if(T->data > x)//把x插入到左子树中
{
T->lchild = Insert(x, T->lchild, taller);
if (taller)//已经插入左子树，且树“长高”，需要检查平衡度，并做相应处理
{
switch(T->bf)
{
case LH : T = LeftBalance(T);//原本左树高于右树，需做左平衡处理，树高不变
taller = false;
break;
case EH : T->bf = LH;//原本左右等高，现在左高于右，且树“长高”
taller = true;
break;
case RH : T->bf = EH; //原本右树高于左树，现在左右等高，树高不变
taller = false;
break;
}
}
}
else //把x插入到右子树中，仿照处理左树的方法处理
{
T->rchild = Insert(x, T->rchild, taller);
if (taller)
{
switch(T->bf)
{
case LH : T->bf = EH;
taller = false;
break;
case EH : T->bf = RH;
taller = true;
break;
case RH : T = RightBalance(T);
taller = false;
break;
}
}
}
return T;
}
Position SingleRotateWithLeft(Position K2)
{
Position K1;
K1 = K2->lchild; //在K2和K1之间进行一次单左旋转
K2->lchild = K1->rchild;
K1->rchild = K2;
return K1;
}
Position SingleRotateWithRight(Position K2)
{
Position K1;
K1 = K2->rchild; //在K2和K1之间进行一次单右旋转
K2->rchild = K1->lchild;
K1->lchild = K2;
return K1;
}
Position DoubleRotateWithLeft(Position K3)
{
K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转
return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}
Position DoubleRotateWithRight(Position K3)
{
K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转
return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}
AvlTree LeftBalance(AvlTree T) //左平衡处理
{
AvlTree lT = T->lchild;
switch (lT->bf) //检查左树的平衡度，并做相应处理
{
case LH : T = SingleRotateWithLeft(T); //若新结点插入在T的左孩子的左子树上，对T单左旋转
T->bf = lT->bf = EH; //重新设置平衡度
break;
case RH : AvlTree rT = lT->rchild;//若新结点插入在T的左孩子的右子树上，对T双左旋转，并重新设置平衡度
switch (rT->bf)
{
case LH : T->bf = RH;
lT->bf = EH;
break;
case EH : T->bf = lT->bf = EH;
break;
case RH : T->bf = EH;
lT->bf = LH;
break;
}
rT->bf = EH;
T = DoubleRotateWithLeft(T);
break;
}
return T;
}
AvlTree RightBalance(AvlTree T) //右平衡处理
{
AvlTree rT = T->rchild;
switch (rT->bf) //检查右树的平衡度，并做相应处理
{
case RH : T = SingleRotateWithRight(T); //若新结点插入在T的右孩子的右子树上，对T单右旋转
T->bf = rT->bf = EH; //重新设置平衡度
break;
case LH : AvlTree lT = rT->lchild;//若新结点插入在T的右孩子的左子树上，对T双右旋转，并重新设置平衡度
switch (lT->bf)
{
case LH : T->bf = EH;
rT->bf = RH;
break;
case EH : T->bf = rT->bf = EH;
break;
case RH : T->bf = LH;
rT->bf = EH;
break;
}
lT->bf = EH;
T = DoubleRotateWithRight(T);
break;
}
return T;
}
void PrintBT(AvlTree bt)
{
if(bt != NULL)
{
printf("%d", bt->data);
if(bt->lchild!=NULL || bt->rchild!=NULL)
{
printf("(");
PrintBT(bt->lchild);
if(bt->rchild!=NULL)
printf(",");
PrintBT(bt->rchild);
printf(")");
}
}
}
评论