Data Structure - Red Black Tree (C)

ゝ一纸荒年。 2023-01-20 10:58 51阅读 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 )

/*
     * RedBlackTree.h - by FreeMan
     */
    
    typedef int ElementType;
    #define NegInfinity (-10000)
    
    #ifndef _RedBlackTree_H_
    #define _RedBlackTree_H_
    
    struct RedBlackNode;
    typedef struct RedBlackNode *Position;
    typedef struct RedBlackNode *RedBlackTree;
    
    RedBlackTree MakeRedBlackTreeEmpty(RedBlackTree T);
    Position FindInRedBlackTree(ElementType X, RedBlackTree T);
    Position FindMinInRedBlackTree(RedBlackTree T);
    Position FindMaxInRedBlackTree(RedBlackTree T);
    RedBlackTree InitializeRedBlackTree(void);
    RedBlackTree InsertInRedBlackTree(ElementType X, RedBlackTree T);
    RedBlackTree RemoveInRedBlackTree(ElementType X, RedBlackTree T);
    ElementType RetrieveInRedBlackTree(Position P);
    void PrintRedBlackTree(RedBlackTree T);
    
    #endif

/*
     * RedBlackTree.c - by FreeMan
     */
    
    #include "RedBlackTree.h"
    #include "Fatal.h"
    #include <stdlib.h>
    
    typedef enum ColorType { Red, Black } ColorType;
    
    struct RedBlackNode
    {
        ElementType  Element;
        RedBlackTree Left;
        RedBlackTree Right;
        ColorType    Color;
    };
    
    /* Needs initialization */
    static Position NullNode = NULL;
    
    RedBlackTree InitializeRedBlackTree(void)
    {
        RedBlackTree T;
    
        if (NullNode == NULL)
        {
            NullNode = malloc(sizeof(struct RedBlackNode));
            if (NullNode == NULL)
            {
                FatalError("Out of memory!!");
            }
            NullNode->Left = NullNode->Right = NullNode;
            NullNode->Color = Black;
            NullNode->Element = 12345;
        }
    
        /* Create the header node */
        T = malloc(sizeof(struct RedBlackNode));
        if (T == NULL)
        {
            FatalError("Out of memory!!");
        }
        T->Element = NegInfinity;
        T->Left = T->Right = NullNode;
        T->Color = Black;
    
        return T;
    }
    
    void Output(ElementType Element)
    {
        printf("%d\n", Element);
    }
    
    /* Print the tree, watch out for NullNode, and skip header */
    static void DoPrint(RedBlackTree T)
    {
        if (T != NullNode)
        {
            DoPrint(T->Left);
            Output(T->Element);
            DoPrint(T->Right);
        }
    }
    
    void PrintRedBlackTree(RedBlackTree T)
    {
        DoPrint(T->Right);
    }
    
    static RedBlackTree MakeEmptyRec(RedBlackTree T)
    {
        if (T != NullNode)
        {
            MakeEmptyRec(T->Left);
            MakeEmptyRec(T->Right);
            free(T);
        }
        return NullNode;
    }
    
    RedBlackTree MakeRedBlackTreeEmpty(RedBlackTree T)
    {
        T->Right = MakeEmptyRec(T->Right);
        return T;
    }
    
    Position FindInRedBlackTree(ElementType X, RedBlackTree T)
    {
        if (T == NullNode)
        {
            return NullNode;
        }
    
        if (X < T->Element)
        {
            return FindInRedBlackTree(X, T->Left);
        }
        else if (X > T->Element)
        {
            return FindInRedBlackTree(X, T->Right);
        }
        else
        {
            return T;
        }
    }
    
    Position FindMinInRedBlackTree(RedBlackTree T)
    {
        T = T->Right;
        while (T->Left != NullNode)
        {
            T = T->Left;
        }
        return T;
    }
    
    Position FindMaxInRedBlackTree(RedBlackTree T)
    {
        while (T->Right != NullNode)
        {
            T = T->Right;
        }
        return T;
    }
    
    /*
     * 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;
    
        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;
    
        return K2;  /* New root */
    }
    
    /*
     * Perform a rotation at node X (whose parent is passed as a parameter).
     * The child is deduced by examining Item.
     */
    static Position Rotate(ElementType Item, Position Parent)
    {
        if (Item < Parent->Element)
        {
            return Parent->Left = Item < Parent->Left->Element ?
                SingleRotateWithLeft(Parent->Left) :
                SingleRotateWithRight(Parent->Left);
        }
        else
        {
            return Parent->Right = Item < Parent->Right->Element ?
                SingleRotateWithLeft(Parent->Right) :
                SingleRotateWithRight(Parent->Right);
        }
    }
    
    static Position X, P, GP, GGP;
    
    static void HandleReorient(ElementType Item, RedBlackTree T)
    {
        X->Color = Red;  /* Do the color flip */
        X->Left->Color = Black;
        X->Right->Color = Black;
    
        if (P->Color == Red)  /* Have to rotate */
        {
            GP->Color = Red;
            if ((Item < GP->Element) != (Item < P->Element))
            {
                P = Rotate(Item, GP);  /* Start double rotate */
            }
            X = Rotate(Item, GGP);
            X->Color = Black;
        }
        T->Right->Color = Black;  /* Make root black */
    }
    
    RedBlackTree InsertInRedBlackTree(ElementType Item, RedBlackTree T)
    {
        X = P = GP = T;
        NullNode->Element = Item;
        while (X->Element != Item)  /* Descend down the tree */
        {
            GGP = GP; GP = P; P = X;
            if (Item < X->Element)
            {
                X = X->Left;
            }
            else
            {
                X = X->Right;
            }
            if (X->Left->Color == Red && X->Right->Color == Red)
            {
                HandleReorient(Item, T);
            }
        }
    
        if (X != NullNode)
        {
            return NullNode;  /* Duplicate */
        }
    
        X = malloc(sizeof(struct RedBlackNode));
        if (X == NULL)
        {
            FatalError("Out of memory!!");
        }
        X->Element = Item;
        X->Left = X->Right = NullNode;
    
        if (Item < P->Element)  /* Attach to its parent */
        {
            P->Left = X;
        }
        else
        {
            P->Right = X;
        }
        HandleReorient(Item, T); /* Color it red; maybe rotate */
    
        return T;
    }
    
    RedBlackTree RemoveInRedBlackTree(ElementType Item, RedBlackTree T)
    {
        printf("Remove is unimplemented\n");
        if (Item)
        {
            return T;
        }
        return T;
    }
    
    ElementType RetrieveInRedBlackTree(Position P)
    {
        return P->Element;
    }

/*
     * RedBlackTreeTest.c - by FreeMan
     */
    
    #include "RedBlackTree.h"
    #include <stdio.h>
    
    #define N 800
    
    main()
    {
        RedBlackTree T;
        Position P;
        int i;
        int j = 0;
    
        T = InitializeRedBlackTree();
        T = MakeRedBlackTreeEmpty(T);
    
        for (i = 0; i < N; i++, j = (j + 7) % N)
        {
            T = InsertInRedBlackTree(j, T);
        }
        printf("Inserts are complete\n");
    
        for (i = 0; i < N; i++)
        {
            if ((P = FindInRedBlackTree(i, T)) == NULL || RetrieveInRedBlackTree(P) != i)
            {
                printf("Error at %d\n", i);
            }
        }
    
        printf("Min is %d, Max is %d\n",
            RetrieveInRedBlackTree(FindMinInRedBlackTree(T)),
            RetrieveInRedBlackTree(FindMaxInRedBlackTree(T)));
    
        return 0;
    }
    
    // Output:
    /*
    Inserts are complete
    Min is 0, Max is 799
    
    */

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