数据结构与算法分析-AVL树

1.AVL树是带有平衡条件的二叉查找树.

2.AVL树的每个节点高度最多相差1.

3.AVL树实现的难点在于插入或删除操作.由于插入和删除都有可能破坏AVL树高度最多相差1的特性,所以当特性被破坏时需要通过旋转方式调整树结构.具体旋转方式有以下4种,举例说明如下:

LL型:

　　　　6 5

　　　/　　　右转 /

　　5　　　　 ----> 4 6

-------------------------------------------------------------------------------------------------------

RR型:

6 7

左转 /

7 ----> 6 8

-------------------------------------------------------------------------------------------------------

LR型:

7 7 6

/ 先左转 / 再右转 /

4 ----> 6 ----> 4 7

6 4

-------------------------------------------------------------------------------------------------------

RL型:

7 7 8

先右转再左转 /

9 ----> 8 ----> 7 9

8 9

图形说明可参考如下链接:

http://blog.csdn.net/gabriel1026/article/details/6311339

#include <stdio.h>
#include <stdlib.h>

#define ElementType int
#define Max(N1, N2) ((N1 > N2) ? (N1) : (N2))

//typedef struct TreeNode *Position;
//typedef struct TreeNode *SearchTree;

struct TreeNode
{
    ElementType Element;
    struct TreeNode *Left;
    struct TreeNode *Right;
    int Height;
};

typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree Insert(ElementType X,  SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
SearchTree MakeEmpty(SearchTree T);
SearchTree PrintTree(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMax(SearchTree T);
Position FindMin(SearchTree T);

static int Height(Position P);
static Position SingleRotateWithRight(Position P); //RR型
static Position SingleRotateWithLeft(Position P);
static Position DoubleRotateWithRight(Position P);
static Position DoubleRotateWithLeft(Position P);
static Position Rotate(Position P);

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

static Position SingleRotateWithRight(Position P)  //RR左转
{
    Position M = NULL;    
    if (NULL == P)
    {
        return NULL;
    }    
    M = P->Right;
    P->Right = M->Left;
    M->Left = P;
    P->Height = Max(Height(P->Left), Height(P->Right)) + 1; 
    M->Height = Max(Height(M->Left), Height(M->Right)) + 1; 
    return M;
}


static Position SingleRotateWithLeft(Position P)  //LL右转
{
    
    Position M = NULL;    
    if (NULL == P)
    {
        return NULL;
    }    
    M = P->Left;
    P->Left = M->Right;
    M->Right = P;
    P->Height = Max(Height(P->Left), Height(P->Right)) + 1; 
    M->Height = Max(Height(M->Left), Height(M->Right)) + 1; 
    return M;
}


static Position DoubleRotateWithRight(Position P)    //RL先右后左
{
    if (NULL == P)
    {
        return NULL;
    }
    P->Right = SingleRotateWithLeft(P->Right);  //LL右转
    return SingleRotateWithRight(P);  //RR左转
}


static Position DoubleRotateWithLeft(Position P)    //LR先左后右双旋
{
    if (NULL == P)
    {
        return NULL;
    }
    P->Left = SingleRotateWithRight(P->Left);  //RR左转
    return SingleRotateWithLeft(P);  //LL右转
}


static Position Rotate(Position P)
{
    if (NULL == P)
    {
        return NULL;
    }
    if (Height(P->Right) - Height(P->Left) == 2)
    {
        if (P->Right)
        {
            if (Height(P->Right->Right) > Height(P->Right->Left))
            {
                P = SingleRotateWithRight(P);   //RR左单旋
            }
            else
            {
                P = DoubleRotateWithRight(P);   //RL先右后左双旋
            }
        }
    }
    else if (Height(P->Left) - Height(P->Right) == 2)
    {
        if (P->Left)
        {
            if (Height(P->Left->Left) > Height(P->Left->Right))
            {
                P = SingleRotateWithLeft(P);   //RR右单旋
            }
            else
            {
                P = DoubleRotateWithLeft(P);   //RL先左后右双旋
            }
        }
    }
    else
    {}
    return P;
}    


SearchTree Insert(ElementType X,  SearchTree T)
{
    if (NULL == T)
    {
        T = (SearchTree)malloc(sizeof(struct TreeNode));    
        if (NULL == T)
        {
            printf("Malloc Error!
");
            return NULL;
        }
        else
        {
            printf("Insert %d!
", X);
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }
    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);    //RR左单旋
            }
            else
            {
                T = DoubleRotateWithRight(T);    //RL先右后左双旋
            }
        }
    }
    else
    {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
        {
            if (X < T->Left->Element)
            {
                T = SingleRotateWithLeft(T);    //RR 右单旋
            }
            else
            {
                T = DoubleRotateWithLeft(T);    //RL先右后左双旋
            }
        }
    }
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}


SearchTree Delete(ElementType X, SearchTree T)
{
    Position Temp = NULL;
    if (NULL == T)
    {
        printf("Delete Element Not Found!
");
        return NULL;
    }
    else if (X > T->Element)
    {
        T->Right = Delete(X, T->Right);
    }
    else if (X < T->Element)
    {
        T->Left = Delete(X, T->Left);
    }
    else if (T->Right && T->Left)
    {
        Temp = FindMin(T->Right);
        T->Element = Temp->Element;
        T->Right = Delete(T->Element, T->Right);
    }
    else
    {
        Temp = T;
        if (NULL == T->Right)
        {
            T = T->Left;    
        }
        else if (NULL == T->Left)
        {
            T = T->Right;    
        }
        else
        {}
        free(Temp);
        Temp = NULL;
        if (NULL == T)
        {
            return NULL;
        }
    }
    //回溯重新计算父节点高度    
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    //删除节点后判断是否失去平衡,如果失去平衡,将树进行相应调整    
    T = Rotate(T);
    return T;
}


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


SearchTree PrintTree(SearchTree T)
{
    if (NULL != T)
    {
        printf("%d,%d ", T->Element, T->Height);
        if (NULL != T->Left)
        {
            PrintTree(T->Left);
        }
        if (NULL != T->Right)
        {
            PrintTree(T->Right);
        }
    }
    return NULL;
}


Position Find(ElementType X, SearchTree T)
{
    if (NULL == T)
    {
        printf("Find Element Not Found!
");
        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 FindMax(SearchTree T)
{
    if (NULL != T)
    {
        while (NULL != T->Right)
        {
            T = T->Right;
        }
    }
    return T;
}

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

int main()
{
    SearchTree T = NULL;    
    SearchTree ptmp = NULL;    
   //验证各函数是否正确
    T = Insert(12, T);    
    T = Insert(4, T);    
    T = Insert(1, T);    
    T = Insert(7, T);    
    T = Insert(8, T);    
    T = Insert(10, T);    
    T = Insert(9, T);    
    T = Insert(2, T);    
    T = Insert(11, T);    
    T = Insert(6, T);    
    T = Insert(5, T);    

    ptmp = FindMin(T);
    if (NULL != ptmp)
    {
        printf("min:%d
", ptmp->Element);
    }
    ptmp = FindMax(T);
    if (NULL != ptmp)
    {
        printf("max:%d
", ptmp->Element);
    }
    ptmp = Find(8, T);
    if (NULL != ptmp)
    {
        printf("find:%d
", ptmp->Element); 
    }
    PrintTree(T);
    printf("
");    

    T = Delete(5, T);
    T = Delete(6, T);
    T = Delete(7, T);
    T = Delete(1, T);
    T = Delete(4, T);
    PrintTree(T);
    printf("
");    
    ptmp = Find(8, T);
    if (NULL != ptmp)
    {
        printf("find:%d
", ptmp->Element); 
    }
    
    T = MakeEmpty(T);
    return 0;    
}

部分编码来自如下链接

http://blog.csdn.net/xiaofan086/article/details/8294382