Avl平衡树--C语言实现

Avl 平衡树 实现记录

Avl平衡二叉树和搜索二叉树基本实现原理相同，在搜索二叉树的基础上添加树平衡的操作--单旋和双旋（这也是AvlTree的重难点）。插入数据和删除数据的时候对树进行平衡调整。

需要注意：在删除树节点的操作中，要注意更新调整各节点中高度（Height）的值。Google搜索结果中看了前几个实现AvlTree的文章，基本都没考虑节点Height属性的更新。

实现代码

#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("根节点的高度：%d\n", T->Height);
    printf("根节点的值：%d\n",T->Element);
}

int main()
{
    test();
}

欢迎关注我的博客O(∩_∩)O哈哈~