Avl 平衡樹 實現(xiàn)記錄
Avl平衡二叉樹和搜索二叉樹基本實現(xiàn)原理相同苍柏，在搜索二叉樹的基礎(chǔ)上添加樹平衡的操作--單旋和雙旋（這也是AvlTree的重難點）洁奈。插入數(shù)據(jù)和刪除數(shù)據(jù)的時候?qū)溥M(jìn)行平衡調(diào)整。
需要注意：在刪除樹節(jié)點的操作中络断，要注意更新調(diào)整各節(jié)點中高度（Height）的值毡琉。Google搜索結(jié)果中看了前幾個實現(xiàn)AvlTree的文章蕾久，基本都沒考慮節(jié)點Height屬性的更新婉宰。
實現(xiàn)代碼
#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("根節(jié)點的高度：%d\n", T->Height);
printf("根節(jié)點的值：%d\n",T->Element);
}
int main()
{
test();
}
歡迎關(guān)注我的博客O(∩_∩)O哈哈~
