Avl 平衡树 实现记录
Avl平衡二叉树和搜索二叉树基本实现原理相同，在搜索二叉树的基础上添加树平衡的操作--单旋和双旋（这也是AvlTree的重难点）。插入数据和删除数据的时候对树进行平衡调整。
需要注意：在删除树节点的操作中，要注意更新调整各节点中高度（Height）的值。Google搜索结果中看了前几个实现AvlTree的文章，基本都没考虑节点Height属性的更新。
实现代码
#include <stdio.h>
#include <stdlib.h>
#define FatalError(str) fprintf(stderr, "%s\n", str), exit(1);
#define Error(str) FatalError(str);
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
typedef int ElementType;
struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
AvlTree
MakeEmpty(AvlTree T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
ElementType Retrieve(Position P);
static int Height(Position P);
static int Max(int, int);
static Position SingleRotateWithLeft(Position P);
static Position SingleRotateWithRight(Position P);
static Position DoubleRotateWithLeft(Position P);
static Position DoubleRotateWithRight(Position P);
AvlTree Delete(Position P, AvlTree T);
void printTree(AvlTree T);
void test();
AvlTree MakeEmpty(AvlTree T)
{
if (T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return T;
}
ElementType Retrieve(Position P)
{
return P->Element;
}
Position Find(ElementType X, AvlTree T)
{
if (T == NULL)
{
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 FindMin(AvlTree T)
{
if (T == NULL)
{
return NULL;
}
else if (T->Left == NULL)
{
return T;
}
else
{
return FindMin(T->Left);
}
}
Position FindMax(AvlTree T)
{
if (T != NULL)
{
while (T->Right != NULL)
{
T = T->Right;
}
}
return T;
}
static int Height(Position P)
{
if (P == NULL)
{
return -1;
}
return P->Height;
}
static int Max(int height1, int height2)
{
if (height1 > height2)
{
return height1;
}
return height2;
}
AvlTree Insert(ElementType X, AvlTree T)
{
if (T == NULL)
{
T = malloc(sizeof(struct AvlNode));
if (T == NULL)
{
Error("Error: out of space!!!");
}
else
{
T->Element = X;
T->Left = T->Right = NULL;
T->Height = 0;
}
}
else if (X < T->Element)
{
T->Left = Insert(X, T->Left);
if (Height(T->Left) - Height(T->Right) == 2)
{
if (X < T->Left->Element)
{
T = SingleRotateWithLeft(T);
}
else
{
T = DoubleRotateWithLeft(T);
}
}
}
else
{
T->Right = Insert(X, T->Right);
if (Height(T->Right) - Height(T->Left) == 2)
{
if (X > T->Right->Element)
{
T = SingleRotateWithRight(T);
}
else
{
T = DoubleRotateWithRight(T);
}
}
}
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
// 左单旋
static Position SingleRotateWithLeft(Position P)
{
Position K1;
K1 = P->Left;
P->Left = K1->Right;
K1->Right = P;
P->Height = Max(Height(P->Left), Height(P->Right)) + 1;
K1->Height = Max(Height(K1->Left), P->Height) + 1;
return K1;
}
// 右单旋
static Position SingleRotateWithRight(Position P)
{
Position K1;
K1 = P->Right;
P->Right = K1->Left;
K1->Left = P;
P->Height = Max(Height(P->Left), Height(P->Right)) + 1;
K1->Height = Max(Height(K1->Left), P->Height) + 1;
return K1;
}
// 左双旋
static Position DoubleRotateWithLeft(Position P)
{
P->Left = SingleRotateWithRight(P->Left);
return SingleRotateWithLeft(P);
}
// 右双旋
static Position DoubleRotateWithRight(Position P)
{
P->Right = SingleRotateWithLeft(P->Right);
return SingleRotateWithRight(P);
}
// 删除
AvlTree Delete(Position P, AvlTree T)
{
Position PMix;
Position Tmp;
if (T != NULL)
{
if (T->Element > P->Element)
{
// printf("34\n");
T->Left = Delete(P, T->Left);
T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
if (Height(T->Right) - Height(T->Left) == 2)
{
if (T->Right->Element < P->Element)
{
return SingleRotateWithRight(T);
}
else
{
return DoubleRotateWithRight(T);
}
}
}
else if (T->Element < P->Element)
{
T->Right = Delete(P, T->Right);
T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
if (Height(T->Left) - Height(T->Right) == 2)
{
if (T->Left->Element > P->Element)
{
return SingleRotateWithLeft(T);
}
else
{
return DoubleRotateWithLeft(T);
}
}
}
else
{
if (T->Right != NULL && T->Left != NULL)
{
if (Height(T->Right) > Height(T->Left))
{
PMix = FindMin(T->Right);
T->Element = PMix->Element;
T->Right = Delete(PMix, T->Right);
}
else
{
PMix = FindMax(T->Left);
T->Element = PMix->Element;
T->Left = Delete(PMix, T->Left);
}
T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
}
else
{
Tmp = P;
T = P->Right ? P->Right : P->Left;
free(Tmp);
}
}
}
return T;
}
void printTree(AvlTree T)
{
if (T != NULL)
{
printTree(T->Left);
printf("%d", T->Element);
printTree(T->Right);
}
}
void test()
{
int i,n;
AvlTree T;
Position P;
n = 20;
for(i = 0; i < n; i++)
{
T = Insert(i, T);
}
printTree(T);
P = Find(4, T);
T = Delete(P, T);
P = Find(5, T);
T = Delete(P, T);
P = Find(17, T);
T = Delete(P, T);
T = Insert(5, T);
printf("\n");
printTree(T);
printf("\n");
printf("根节点的高度：%d\n", T->Height);
printf("根节点的值：%d\n",T->Element);
}
int main()
{
test();
}
欢迎关注我的博客O(∩_∩)O哈哈~
网友评论