Data Structure - Red Black Tree (C)-蒲公英云

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击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
*/