伸展树

//自顶向下的展开过程

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;
            RightTreeMin->Left = X;
            RightTreeMin = X;
            X = X->Left;
        }
        else 
        {
            if(Item > X->Right->Element)
                X = SingleRotateWithRight(X);
            if(X->Right == NullNode)
                break;
            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;
}