Data Structure - Splay 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 )
/*
 * SplayTree.h - by FreeMan
 */
typedef int ElementType;
#define Infinity 30000
#define NegInfinity (-30000)
#ifndef _SplayTree_H_
#define _SplayTree_H_
struct SplayNode;
typedef struct SplayNode *SplayTree;
SplayTree MakeSplayTreeEmpty(SplayTree T);
SplayTree FindInSplayTree(ElementType X, SplayTree T);
SplayTree FindMinInSplayTree(SplayTree T);
SplayTree FindMaxInSplayTree(SplayTree T);
SplayTree InitializeSplayTree(void);
SplayTree InsertInSplayTree(ElementType X, SplayTree T);
SplayTree RemoveInSplayTree(ElementType X, SplayTree T);
ElementType RetrieveInSplayTree(SplayTree T);  /* Gets root item */
#endif
/*
 * SplayTree.c - by FreeMan
 */
#include "SplayTree.h"
#include "Fatal.h"
#include <stdlib.h>
struct SplayNode
{
    ElementType Element;
    SplayTree   Left;
    SplayTree   Right;
};
typedef struct SplayNode *Position;
static Position NullNode = NULL;  /* Needs initialization */
SplayTree InitializeSplayTree(void)
{
    if (NullNode == NULL)
    {
        NullNode = malloc(sizeof(struct SplayNode));
        if (NullNode == NULL)
        {
            FatalError("Out of memory!!");
        }
        NullNode->Left = NullNode->Right = NullNode;
    }
    return NullNode;
}
static SplayTree Splay(ElementType Item, Position X);
SplayTree MakeSplayTreeEmpty(SplayTree T)
{
    if (T != NullNode)
    {
        MakeSplayTreeEmpty(T->Left);
        MakeSplayTreeEmpty(T->Right);
        free(T);
    }
    return NullNode;
}
void PrintTree(SplayTree T)
{
    if (T != NullNode)
    {
        PrintTree(T->Left);
        printf("%d ", T->Element);
        PrintTree(T->Right);
    }
}
SplayTree FindInSplayTree(ElementType X, SplayTree T)
{
    return Splay(X, T);
}
SplayTree FindMinInSplayTree(SplayTree T)
{
    return Splay(NegInfinity, T);
}
SplayTree FindMaxInSplayTree(SplayTree T)
{
    return Splay(Infinity, 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 */
}
/* Top-down splay procedure, not requiring item to be in tree. */
SplayTree Splay(ElementType Item, Position X)
{
    static struct SplayNode Header;
    Position LeftTreeMax, RightTreeMin;
    Header.Left = Header.Right = NullNode;
    LeftTreeMax = RightTreeMin = &Header;
    NullNode->Element = Item;
    while (Item != X->Element)
    {
        if (Item < X->Element)
        {
            if (Item < X->Left->Element)
            {
                X = SingleRotateWithLeft(X);
            }
            if (X->Left == NullNode)
            {
                break;
            }
            /* Link right */
            RightTreeMin->Left = X;
            RightTreeMin = X;
            X = X->Left;
        }
        else
        {
            if (Item > X->Right->Element)
            {
                X = SingleRotateWithRight(X);
            }
            if (X->Right == NullNode)
            {
                break;
            }
            /* Link left */
            LeftTreeMax->Right = X;
            LeftTreeMax = X;
            X = X->Right;
        }
    }
    /* Reassemble */
    LeftTreeMax->Right = X->Left;
    RightTreeMin->Left = X->Right;
    X->Left = Header.Right;
    X->Right = Header.Left;
    return X;
}
SplayTree InsertInSplayTree(ElementType Item, SplayTree T)
{
    static Position NewNode = NULL;
    if (NewNode == NULL)
    {
        NewNode = malloc(sizeof(struct SplayNode));
        if (NewNode == NULL)
        {
            FatalError("Out of memory!!");
        }
    }
    NewNode->Element = Item;
    if (T == NullNode)
    {
        NewNode->Left = NewNode->Right = NullNode;
        T = NewNode;
    }
    else
    {
        T = Splay(Item, T);
        if (Item < T->Element)
        {
            NewNode->Left = T->Left;
            NewNode->Right = T;
            T->Left = NullNode;
            T = NewNode;
        }
        else if (T->Element < Item)
        {
            NewNode->Right = T->Right;
            NewNode->Left = T;
            T->Right = NullNode;
            T = NewNode;
        }
        else
        {
            return T;  /* Already in the tree */
        }
    }
    NewNode = NULL;  /* So next insert will call malloc */
    return T;
}
SplayTree RemoveInSplayTree(ElementType Item, SplayTree T)
{
    Position NewTree;
    if (T != NullNode)
    {
        T = Splay(Item, T);
        if (Item == T->Element)
        {
            /* Found it! */
            if (T->Left == NullNode)
            {
                NewTree = T->Right;
            }
            else
            {
                NewTree = T->Left;
                NewTree = Splay(Item, NewTree);
                NewTree->Right = T->Right;
            }
            free(T);
            T = NewTree;
        }
    }
    return T;
}
ElementType RetrieveInSplayTree(SplayTree T)
{
    return T->Element;
}
/*
 * SplayTreeTest.c - by FreeMan
 */
#include "SplayTree.h"
#include <stdio.h>
#define NumItems 500
main()
{
    printf("Testing Splay Tree...\n");
    SplayTree T;
    SplayTree P;
    int i;
    int j = 0;
    T = InitializeSplayTree();
    T = MakeSplayTreeEmpty(T);
    for (i = 0; i < NumItems; i++, j = (j + 7) % NumItems)
    {
        T = InsertInSplayTree(j, T);
    }
    for (j = 0; j < 2; j++)
        for (i = 0; i < NumItems; i++)
        {
            T = FindInSplayTree(i, T);
            if (RetrieveInSplayTree(T) != i)
            {
                printf("Error1 at %d\n", i);
            }
        }
    for (i = 0; i < NumItems; i += 2)
    {
        T = RemoveInSplayTree(i, T);
    }
    for (i = 1; i < NumItems; i += 2)
    {
        T = FindInSplayTree(i, T);
        if (RetrieveInSplayTree(T) != i)
        {
            printf("Error2 at %d\n", i);
        }
    }
    for (i = 0; i < NumItems; i += 2)
    {
        T = FindInSplayTree(i, T);
        if (RetrieveInSplayTree(T) == i)
        {
            printf("Error3 at %d\n", i);
        }
    }
    printf("Min is %d\n", RetrieveInSplayTree(T = FindMinInSplayTree(T)));
    printf("Max is %d\n", RetrieveInSplayTree(T = FindMaxInSplayTree(T)));
    return 0;
}
// Output:
/*
Testing Splay Tree...
Min is 1
Max is 499
*/