AVL Tree的C实现

avl_tree.c

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include "avl_tree.h"

static Position SingleRotateWithRight(Position K2);

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

static int Max(int i,int j)
{
        return (j>i) ? j : i;
}


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;

        printf("SingleRotateWithLeft\n");
        return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
        printf("DoubleRotateWithLeft\n");
        K3->Left=SingleRotateWithRight(K3->Left);

        return SingleRotateWithLeft(K3);
}

static Position SingleRotateWithRight(Position K2)
{
        Position K1;
        K1=K2->Right;
        K2->Right=K1->Left;
        K1->Left=K2;

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

        printf("SingleRotateWithRight\n");
        return K1;
}

static Position DoubleRotateWithRight(Position K3)
{
        printf("DoubleRotateWithRight\n");
        K3->Right=SingleRotateWithLeft(K3->Right);

        return SingleRotateWithRight(K3);
}

void MakeEmpty(AvlTree T)
{
        if(T->Left != NULL)
        {
                MakeEmpty(T->Left);
                T->Left=NULL;
        }
        if(T->Right != NULL)
        {
                MakeEmpty(T->Right);
                T->Right=NULL;
        }
        free(T);
}

void PrintAvlTree(AvlTree T)
{
        if(T != NULL)
        {
                PrintAvlTree(T->Left);
                printf("Elem:%d\tHeight:%d\n",T->Elem,T->Height);
                PrintAvlTree(T->Right);
        }
}


AvlTree Insert(int X,AvlTree T)
{
        if(T == NULL)
        {
                printf("new node\n");
                T=(struct AvlNode *)malloc(sizeof(struct AvlNode));
                if(T==NULL)
                {
                        perror("alloc new node memory error");
                        exit(1);
                }else
                {
                        T->Elem=X;
                        T->Height=0;
                        T->Left=T->Right=NULL;
                }
        }else
        {
                if(X < T->Elem)
                {
                        T->Left=Insert(X,T->Left);
                        if(Height(T->Left)-Height(T->Right) == 2)
                                if(X < (T->Left->Elem))
                                        T=SingleRotateWithLeft(T);
                                else
                                        T=DoubleRotateWithLeft(T);

                }
                else if(X > T->Elem)
                {
                        T->Right=Insert(X,T->Right);
                        if(Height(T->Right)-Height(T->Left) == 2)
                                if(X > (T->Right->Elem))
                                        T=SingleRotateWithRight(T);
                                else
                                        T=DoubleRotateWithRight(T);

                }
        }

        T->Height=Max(Height(T->Left),Height(T->Right))+1;
        printf("T->Height:%d\n",T->Height);
        return T;
}

avl_tree.h

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

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


void MakeEmpty(AvlTree T);
void PrintAvlTree(AvlTree T);
Position Find(int X,AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(int X,AvlTree T);

main.c

#include <stdio.h>
#include "avl_tree.h"

int main(void)
{
        AvlTree T=NULL;
        T=Insert(20,T);
        T=Insert(30,T);
        T=Insert(50,T);
        T=Insert(70,T);
        T=Insert(60,T);
        T=Insert(90,T);
        T=Insert(120,T);
        T=Insert(100,T);
        T=Insert(190,T);
        T=Insert(170,T);
        T=Insert(160,T);
        T=Insert(150,T);
        T=Insert(130,T);
        PrintAvlTree(T);
        MakeEmpty(T);
        return 0;
}