数据结构学习之树---AVL树的实现

AVL 树是带有平衡条件的儿茶查找树。这个平衡条件必须要容易保持，而且必须保证书的深度是O(log N),最简单的想法是
要求左右子树具有相同的高度
另一种平衡条件是要求每个节点都唏嘘要具有相同的高度的做子树和右子树

定义：AVL树是其每一个节点的左子树和右子树的高度最多差1的二叉树(空树的高度定义为-1)

AVL树节点的声明：
#ifndef _AvlTree_h
struct AvlNode;
typedef struct AvlNode *Position ;
typedef struct AvlNode *AvlTree ;
AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X,AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X,AvlTree T);
AvlTree Delete(ElementType X,AvlTree T);
ElementType Retrieve(Position P);
#endif

struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};


Position
Find( ElementType X, AvlTree T )
{
if( T == NULL )
return NULL;
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;
}
计算AVL节点的高度的函数
static int Height(Position P)
{
if(P==NULL)
return -1;
else
return P->Height;
}

向AVL插入节点的函数

AvlTree Insert(ElementType X,AvlTree T)
{
if(T==NULL)
{
T=malloc(sizeof(struct AvlNode));
if(T==NULL)
FatalError("out of space");
else
{
T->Element=X;
T->Height=0;
T->Left=T->Right=NULL:
}
}
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 if(X>T->Element)
{
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 K2)
{
Position K1;
K1=K2->Left;
K2->Left=K1->Right;
K1->Right=K2;

K2->Height=Max(Height(K2->Left),Height(K2->Right))+1;

K1->Height=Max(Height(K1->Left),K2->Height)+1;

return K1;

}


static Position
SingleRotateWithRight( Position K1 )
{
Position K2;


K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;


K1->Height = Max( Height( K1->Left ), Height( K1->Right ) ) + 1;
K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;


return K2; /* New root */
}




执行双旋转过程


static Position DoubleRotateWithLeft(Position K3)
{
K3->Left=SingleRotateWithRight(K3->Left);

return SingleRotateWithLeft(K3);
}
static Position
DoubleRotateWithRight( Position K1 )
{
/* Rotate between K3 and K2 */
K1->Right = SingleRotateWithLeft( K1->Right );


/* Rotate between K1 and K2 */
return SingleRotateWithRight( K1 );
}