[数据结构与算法]AvlTree 数据结构与算法分析C语言实现

AvlTree

Avl的节点以及相关函数声明

#ifndef _AvlTree_H

struct AvlNode;
typedef struct AvlNode *Position;
typedef Position AvlTree;

// AvlTree MakeEmpty(AvlTree T);
Position Find(int X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(int X, AvlTree T);
AvlTree Delete(int X, AvlTree T);
// int Retrieve(Position P);
AvlTree SingleRotateWithLeft(Position K);
AvlTree DoubleRotateWithLeft(Position K);
AvlTree SingleRotateWithRight(Position K);
AvlTree DoubleRotateWithRight(Position K);
int Max(int X, int Y);
static int Height(Position P);

#endif

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

Height()

static int Height(Position P)
{
    if (P == NULL)
        return -1;
    else
        return P->Height;
}

Find()

Position Find(int 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;
}

FindMin()

Position FindMin(AvlTree T)
{
    if (T == NULL)
        return NULL;
    else if(T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);
}

Insert()

AvlTree Insert(int X, AvlTree T)
{
    if (T == NULL)
    {
        T = (AvlTree)malloc(sizeof(struct AvlNode));
        if (T == NULL)
        {
            printf("Out of space");
            exit(EXIT_FAILURE);
        }
        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;
}

Delete()

AvlTree Delete(int X, AvlTree T)
{
    if (T == NULL)
    {
        fprintf(stderr, "%d not exist\n", X);
    }
    else
    {
        if (X < T->Element)
        {
            T->Left = Delete(X, T->Left);
            T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
            if (Height(T->Right) - Height(T->Left) == 2)
                if (Height(T->Right->Right) >= Height(T->Right->Left))
                    T = SingleRotateWithRight(T);
                else
                    T = DoubleRotateWithRight(T);
        }
        else if (X > T->Element)
        {
            T->Right = Delete(X, T->Right);
			T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
			if((Height(T->Left) - Height(T->Right)) == 2)
			{
				if(Height(T->Left->Left) >= Height(T->Left->Right))
					T = SingleRotateWithLeft(T);
				else
					T = DoubleRotateWithLeft(T);
			}
        }
        else
        {
            if(T ->Left && T->Right)
			{
				T->Element = FindMin(T->Right)->Element;
				T->Right = Delete(T->Element, T->Right);
                 T->Height = Max(Height(T->Left), Height(T->Right)) + 1;

				if((Height(T->Left) - Height(T->Right)) == 2)
				{
					if(Height(T->Left->Left) >= Height(T->Left->Right))
						T = SingleRotateWithLeft(T);
					else
						T = DoubleRotateWithLeft(T);
				}
			}
			else
			{
			    AvlTree Tmp = T;
				if(T->Left == NULL)
					T= T->Right;
				else
					T= T->Left;
				free(Tmp);
			}
        }
    }
    return T;
}

SingleRotateWithLeft()

AvlTree SingleRotateWithLeft(Position K2)
{
    Position 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;
}

DoubleRotateWithLeft()

AvlTree DoubleRotateWithLeft(Position K3)
{
    /* Rotate between K1 and K2 */
    K3->Left = SingleRotateWithRight(K3->Left);
    /* Rotate between K3 and K2 */
    return SingleRotateWithLeft(K3);
}