1.AVL树是带有平衡条件的二叉查找树.
2.AVL树的每个节点高度最多相差1.
3.AVL树实现的难点在于插入或删除操作.由于插入和删除都有可能破坏AVL树高度最多相差1的特性,所以当特性被破坏时需要通过旋转方式调整树结构.具体旋转方式有以下4种,举例说明如下:
LL型:
6 5
/ 右转 / \
5 ----> 4 6
/
4
-------------------------------------------------------------------------------------------------------
RR型:
6 7
\ 左转 / \
7 ----> 6 8
\
8
-------------------------------------------------------------------------------------------------------
LR型:
7 7 6
/ 先左转 / 再右转 / \
4 ----> 6 ----> 4 7
\ /
6 4
-------------------------------------------------------------------------------------------------------
RL型:
7 7 8
\ 先右转 \ 再左转 / \
9 ----> 8 ----> 7 9
/ \
8 9
图形说明可参考如下链接:
http://blog.csdn.net/gabriel1026/article/details/6311339
#include <stdio.h>
#include <stdlib.h> #define ElementType int
#define Max(N1, N2) ((N1 > N2) ? (N1) : (N2)) //typedef struct TreeNode *Position;
//typedef struct TreeNode *SearchTree; struct TreeNode
{
ElementType Element;
struct TreeNode *Left;
struct TreeNode *Right;
int Height;
}; typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree; SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
SearchTree MakeEmpty(SearchTree T);
SearchTree PrintTree(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMax(SearchTree T);
Position FindMin(SearchTree T); static int Height(Position P);
static Position SingleRotateWithRight(Position P); //RR型
static Position SingleRotateWithLeft(Position P);
static Position DoubleRotateWithRight(Position P);
static Position DoubleRotateWithLeft(Position P);
static Position Rotate(Position P); static int Height(Position P)
{
if (NULL == P)
{
return -;
}
else
{
return P->Height;
}
} static Position SingleRotateWithRight(Position P) //RR左转
{
Position M = NULL;
if (NULL == P)
{
return NULL;
}
M = P->Right;
P->Right = M->Left;
M->Left = P;
P->Height = Max(Height(P->Left), Height(P->Right)) + ;
M->Height = Max(Height(M->Left), Height(M->Right)) + ;
return M;
} static Position SingleRotateWithLeft(Position P) //LL右转
{ Position M = NULL;
if (NULL == P)
{
return NULL;
}
M = P->Left;
P->Left = M->Right;
M->Right = P;
P->Height = Max(Height(P->Left), Height(P->Right)) + ;
M->Height = Max(Height(M->Left), Height(M->Right)) + ;
return M;
} static Position DoubleRotateWithRight(Position P) //RL先右后左
{
if (NULL == P)
{
return NULL;
}
P->Right = SingleRotateWithLeft(P->Right); //LL右转
return SingleRotateWithRight(P); //RR左转
} static Position DoubleRotateWithLeft(Position P) //LR先左后右双旋
{
if (NULL == P)
{
return NULL;
}
P->Left = SingleRotateWithRight(P->Left); //RR左转
return SingleRotateWithLeft(P); //LL右转
} static Position Rotate(Position P)
{
if (NULL == P)
{
return NULL;
}
if (Height(P->Right) - Height(P->Left) == )
{
if (P->Right)
{
if (Height(P->Right->Right) > Height(P->Right->Left))
{
P = SingleRotateWithRight(P); //RR左单旋
}
else
{
P = DoubleRotateWithRight(P); //RL先右后左双旋
}
}
}
else if (Height(P->Left) - Height(P->Right) == )
{
if (P->Left)
{
if (Height(P->Left->Left) > Height(P->Left->Right))
{
P = SingleRotateWithLeft(P); //RR右单旋
}
else
{
P = DoubleRotateWithLeft(P); //RL先左后右双旋
}
}
}
else
{}
return P;
} SearchTree Insert(ElementType X, SearchTree T)
{
if (NULL == T)
{
T = (SearchTree)malloc(sizeof(struct TreeNode));
if (NULL == T)
{
printf("Malloc Error!\n");
return NULL;
}
else
{
printf("Insert %d!\n", X);
T->Element = X;
T->Left = T->Right = NULL;
}
}
else if (X > T->Element)
{
T->Right = Insert(X, T->Right);
if (Height(T->Right) - Height(T->Left) == )
{
if (X > T->Right->Element)//
{
T = SingleRotateWithRight(T); //RR左单旋
}
else
{
T = DoubleRotateWithRight(T); //RL先右后左双旋
}
}
}
else
{
T->Left = Insert(X, T->Left);
if (Height(T->Left) - Height(T->Right) == )
{
if (X < T->Left->Element)
{
T = SingleRotateWithLeft(T); //RR 右单旋
}
else
{
T = DoubleRotateWithLeft(T); //RL先右后左双旋
}
}
}
T->Height = Max(Height(T->Left), Height(T->Right)) + ;
return T;
} SearchTree Delete(ElementType X, SearchTree T)
{
Position Temp = NULL;
if (NULL == T)
{
printf("Delete Element Not Found!\n");
return NULL;
}
else if (X > T->Element)
{
T->Right = Delete(X, T->Right);
}
else if (X < T->Element)
{
T->Left = Delete(X, T->Left);
}
else if (T->Right && T->Left)
{
Temp = FindMin(T->Right);
T->Element = Temp->Element;
T->Right = Delete(T->Element, T->Right);
}
else
{
Temp = T;
if (NULL == T->Right)
{
T = T->Left;
}
else if (NULL == T->Left)
{
T = T->Right;
}
else
{}
free(Temp);
Temp = NULL;
if (NULL == T)
{
return NULL;
}
}
//回溯重新计算父节点高度
T->Height = Max(Height(T->Left), Height(T->Right)) + ;
//删除节点后判断是否失去平衡,如果失去平衡,将树进行相应调整
T = Rotate(T);
return T;
} SearchTree MakeEmpty(SearchTree T)
{
if (NULL != T)
{
MakeEmpty(T->Right);
MakeEmpty(T->Left);
free(T);
}
return NULL;
} SearchTree PrintTree(SearchTree T)
{
if (NULL != T)
{
printf("%d,%d ", T->Element, T->Height);
if (NULL != T->Left)
{
PrintTree(T->Left);
}
if (NULL != T->Right)
{
PrintTree(T->Right);
}
}
return NULL;
} Position Find(ElementType X, SearchTree T)
{
if (NULL == T)
{
printf("Find Element Not Found!\n");
return NULL;
}
else if (X < T->Element)
{
return Find(X, T->Left);
}
else if (X > T->Element)
{
return Find(X, T->Right);
}
else
{
return T;
}
} Position FindMax(SearchTree T)
{
if (NULL != T)
{
while (NULL != T->Right)
{
T = T->Right;
}
}
return T;
} Position FindMin(SearchTree T)
{
if (NULL == T)
{
return NULL;
}
else if (NULL == T->Left)
{
return T;
}
else
{
return FindMin(T->Left);
}
} int main()
{
SearchTree T = NULL;
SearchTree ptmp = NULL;
//验证各函数是否正确
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T);
T = Insert(, T); ptmp = FindMin(T);
if (NULL != ptmp)
{
printf("min:%d\n", ptmp->Element);
}
ptmp = FindMax(T);
if (NULL != ptmp)
{
printf("max:%d\n", ptmp->Element);
}
ptmp = Find(, T);
if (NULL != ptmp)
{
printf("find:%d\n", ptmp->Element);
}
PrintTree(T);
printf("\n"); T = Delete(, T);
T = Delete(, T);
T = Delete(, T);
T = Delete(, T);
T = Delete(, T);
PrintTree(T);
printf("\n");
ptmp = Find(, T);
if (NULL != ptmp)
{
printf("find:%d\n", ptmp->Element);
} T = MakeEmpty(T);
return ;
}
部分编码来自如下链接
http://blog.csdn.net/xiaofan086/article/details/8294382