Data Structure - AVL Tree (C)

待我称王封你为后i 2023-01-20 09:42 8阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

/*
     * Fatal.h - by FreeMan
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define Error( Str )        FatalError( Str )
    #define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )

/*
     * AvlTree.h - by FreeMan
     */
    
    typedef int ElementType;
    
    #ifndef _AvlTree_H_
    #define _AvlTree_H_
    
    struct AvlNode;
    typedef struct AvlNode *Position;
    typedef struct AvlNode *AvlTree;
    
    AvlTree MakeAvlTreeEmpty(AvlTree T);
    Position FindInAvlTree(ElementType X, AvlTree T);
    Position FindMinInAvlTree(AvlTree T);
    Position FindMaxInAvlTree(AvlTree T);
    AvlTree InsertInAvlTree(ElementType X, AvlTree T);
    AvlTree DeleteInAvlTree(ElementType X, AvlTree T);
    ElementType RetrieveInAvlTree(Position P);
    
    #endif

/*
     * AvlTree.c - by FreeMan
     */
    
    #include "AvlTree.h"
    #include "..\Fatal.h"
    #include <stdlib.h>
    
    struct AvlNode
    {
        ElementType Element;
        AvlTree  Left;
        AvlTree  Right;
        int      Height;
    };
    
    AvlTree MakeAvlTreeEmpty(AvlTree T)
    {
        if (T != NULL)
        {
            MakeAvlTreeEmpty(T->Left);
            MakeAvlTreeEmpty(T->Right);
            free(T);
        }
        return NULL;
    }
    
    Position FindInAvlTree(ElementType X, AvlTree T)
    {
        if (T == NULL)
        {
            return NULL;
        }
    
        if (X < T->Element)
        {
            return FindInAvlTree(X, T->Left);
        }
        else if (X > T->Element)
        {
            return FindInAvlTree(X, T->Right);
        }
        else
        {
            return T;
        }
    }
    
    Position FindMinInAvlTree(AvlTree T)
    {
        if (T == NULL)
        {
            return NULL;
        }
        else if (T->Left == NULL)
        {
            return T;
        }
        else
        {
            return FindMinInAvlTree(T->Left);
        }
    }
    
    Position FindMaxInAvlTree(AvlTree T)
    {
        if (T != NULL)
        {
            while (T->Right != NULL)
            {
                T = T->Right;
            }
        }
        return T;
    }
    
    static int Height(Position P)
    {
        if (P == NULL)
        {
            return -1;
        }
        else
        {
            return P->Height;
        }
    }
    
    static int Max(int Lhs, int Rhs)
    {
        return Lhs > Rhs ? Lhs : Rhs;
    }
    
    /*
     * This function can be called only if K2 has a left child.
     * Perform a rotate between a node (K2) and its left child.
     * Update heights, then return new root.
     */
    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;  /* New root */
    }
    
    /*
     * This function can be called only if K1 has a right child.
     * Perform a rotate between a node (K1) and its right child.
     * Update heights, then return new root.
     */
    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 */
    }
    
    /*
     * This function can be called only if K3 has a left child
     * and K3's left child has a right child.
     * Do the left-right double rotation.
     * Update heights, then return new root.
     */
    static Position DoubleRotateWithLeft(Position K3)
    {
        /* Rotate between K1 and K2 */
        K3->Left = SingleRotateWithRight(K3->Left);
    
        /* Rotate between K3 and K2 */
        return SingleRotateWithLeft(K3);
    }
    
    /*
     * This function can be called only if K1 has a right child
     * and K1's right child has a left child.
     * Do the right-left double rotation.
     * Update heights, then return new root.
     */
    static Position DoubleRotateWithRight(Position K1)
    {
        /* Rotate between K3 and K2 */
        K1->Right = SingleRotateWithLeft(K1->Right);
    
        /* Rotate between K1 and K2 */
        return SingleRotateWithRight(K1);
    }
    
    AvlTree InsertInAvlTree(ElementType X, AvlTree T)
    {
        if (T == NULL)
        {
            /* Create and return a one-node tree */
            T = malloc(sizeof(struct AvlNode));
            if (T == NULL)
            {
                FatalError("Out of memory!!");
            }
            else
            {
                T->Element = X;
                T->Left = T->Right = NULL;
                T->Height = 0;
            }
        }
        else if (X < T->Element)
        {
            T->Left = InsertInAvlTree(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 = InsertInAvlTree(X, T->Right);
            if (Height(T->Right) - Height(T->Left) == 2)
            {
                if (X > T->Right->Element)
                {
                    T = SingleRotateWithRight(T);
                }
                else
                {
                    T = DoubleRotateWithRight(T);
                }
            }
        }
        /* Else X is in the tree already; we'll do nothing */
    
        T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    
        return T;
    }
    
    AvlTree DeleteInAvlTree(ElementType X, AvlTree T)
    {
        printf("Sorry; Delete is unimplemented; %d remains\n", X);
        return T;
    }
    
    ElementType RetrieveInAvlTree(Position P)
    {
        return P->Element;
    }

/*
     * AvlTreeTest.c - by FreeMan
     */
    
    #include "AvlTree.h"
    #include <stdio.h>
    
    main()
    {
        AvlTree T;
        Position P;
        int i;
        int j = 0;
    
        T = MakeAvlTreeEmpty(NULL);
        for (i = 0; i < 50; i++, j = (j + 7) % 50)
        {
            T = InsertInAvlTree(j, T);
        }
        for (i = 0; i < 50; i++)
        {
            if ((P = FindInAvlTree(i, T)) == NULL || RetrieveInAvlTree(P) != i)
            {
                printf("Error at %d\n", i);
            }
        }
    
        /*
        for (i = 0; i < 50; i += 2)
        {
            T = Delete(i, T);
        }
        for (i = 1; i < 50; i += 2)
        {
            if ((P = Find(i, T)) == NULL || Retrieve(P) != i)
            {
                printf("Error at %d\n", i);
            }
        }
        for (i = 0; i < 50; i += 2)
        {
            if ((P = Find(i, T)) != NULL)
            {
                printf("Error at %d\n", i);
            }
        }
        */
    
        printf("Min is %d, Max is %d\n",
            RetrieveInAvlTree(FindMinInAvlTree(T)),
            RetrieveInAvlTree(FindMaxInAvlTree(T)));
    
        return 0;
    }
    
    // Output:
    /*
    Min is 0, Max is 49
    
    */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter