codevs 4244 平衡树练习

二次联通门 : codevs 4244 平衡树练习

Splay实测指针占用空间大约是数组的3倍， 且时间上也慢了差不多1s

数组版评测记录如下

指针版评测记录如下

    以上数据仅限这一个题， 对于别的题，指针其实是比数组快的

　　虽然这样。。。

　　但是指针写起来就是看着顺眼。。。。

/*

    指针版

*/

#include <cstdio>

#include <cstdlib>

void read (int &now)

{

    now = ;

    register char word = getchar ();

    bool temp = false;

    while (word < '' || word > '')

    {

        if (word == '-')

            temp = true;

        word = getchar ();

    }

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

    if (temp)

        now = -now;

}

struct Splay_Tree_Data

{

    Splay_Tree_Data *child[];

    Splay_Tree_Data *father;

    int size, weigth;

    int key;

    inline void Updata ()

    {

        this->size = this->weigth;

        if (this->child[] != NULL)

            this->size += this->child[]->size;

        if (this->child[] != NULL)

            this->size += this->child[]->size;

    }

    inline int Get_Pos ()

    {

        return this->father->child[] == this;

    }

    Splay_Tree_Data ()

    {

        child[] = NULL;

        child[] = NULL;

        size = weigth = ;

        father = NULL;

        key = ;

    }

};

Splay_Tree_Data *Root;

class Splay_Tree_Type

{

    private :

        inline void Rotate (Splay_Tree_Data *now)

        {

            Splay_Tree_Data *Father = now->father;

            if (now == NULL || Father == NULL)

                return ;

            int pos = now->Get_Pos () ^ ;

            Father->child[pos ^ ] = now->child[pos];

            if (now->child[pos])

                now->child[pos]->father = Father;

            if ((now->father = Father->father) != NULL)

                now->father->child[now->father->child[] == Father] = now;

            Father->father = now;

            now->child[pos] = Father;

            Father->Updata ();

            now->Updata ();

            if (now->father == NULL)

                Root = now;

        }

        inline void Splay (Splay_Tree_Data *now, Splay_Tree_Data *to = NULL)

        {

            for (; now->father != to; Rotate (now))

                if (now->father->father != to)

                    Rotate (now->Get_Pos () == now->father->Get_Pos () ? now->father : now);

        }

    public :

        void Insert (int x)

        {

            Splay_Tree_Data *now = Root;

            if (Root == NULL)

            {

                Root = new Splay_Tree_Data;

                Root->key = x;

                Root->father = NULL;

                return ;

            }

            int pos;

            while (true)

            {

                if (now->key == x)

                {

                    now->size ++;

                    now->weigth ++;

                    Splay (now);

                    return ;

                }

                pos = x > now->key ?  : ;

                if (now->child[pos] == NULL)

                {

                    now->child[pos] = new Splay_Tree_Data;

                    now->child[pos]->father = now;

                    now->child[pos]->key = x;

                    Splay (now->child[pos]);

                    return ;

                }

                now = now->child[pos];

            }

        }

        bool Find (int x)

        {

            Splay_Tree_Data *now = Root;

            while (true)

            {

                if (x == now->key)

                    return true;

                else if (x < now->key && now->child[] != NULL)

                    now = now->child[];

                else if (x > now->key && now->child[] != NULL)

                    now = now->child[];

                else

                    return false;

            }

        }

};

Splay_Tree_Type Tree;

int N, M;

int main (int argc, char *argv[])

{

    int x;

    for (read (N), read (M); N--; )

    {

        read (x);

        Tree.Insert (x);

    }

    for (; M--; )

    {

        read (x);

        if (Tree.Find (x))

            printf ("1 ");

        else

            printf ("0 ");

    }

    return ;

}

/*

    数组版

*/

#include <cstdio>

#define Max 10000002

void read (int &now)

{

    now = ;

    register char word = getchar ();

    bool temp = false;

    while (word < '' || word > '')

    {

        if (word == '-')

            temp = true;

        word = getchar ();

    }

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

    if (temp)

        now = -now;

}

class Splay_Tree_Type

{

    private :

        struct Splay_Tree_Date

        {

            int key;

            int father;

            int child[];

        }

        tree[Max];

        int Count;

        int Root;

        inline int Get_Son (int now)

        {

            return tree[tree[now].father].child[] == now;

        }

        inline void Rotate (int now)

        {

            int father = tree[now].father;

            int Grand = tree[father].father;

            int pos = Get_Son (now);

            tree[father].child[pos] = tree[now].child[pos ^ ];

            tree[tree[father].child[pos]].father = father;

            tree[now].child[pos ^ ] = father;

            tree[father].father = now;

            tree[now].father = Grand;

            if (Grand)

                tree[Grand].child[tree[Grand].child[] == father] = now;

        }

        inline void Splay (int now)

        {

            for (int father; father = tree[now].father; Rotate (now))

                if (tree[father].father)

                    Rotate (Get_Son (now) == Get_Son (father) ? father : now);

            Root = now;

        }

    public :

        void Insert (int x)

        {

            if (!Root)

            {

                Count++;

                tree[Count].key = x;

                Root = Count;

                return ;

            }

            int now = Root, father = ;

            while (true)

            {

                if (tree[now].key == x)

                    return ;

                father = now;

                now = tree[now].child[x > tree[father].key];

                if (!now)

                {

                    Count++;

                    tree[Count].key = x;

                    tree[Count].father = father;

                    tree[father].child[x > tree[father].key] = Count;

                    Splay (Count);

                    return ;

                }

            }

        }

        int Find (int x)

        {

            int now = Root;

            while (true)

            {

                if (x == tree[now].key)

                    return ;

                if (x < tree[now].key && tree[now].child[])

                    now = tree[now].child[];

                else if (x > tree[now].key && tree[now].child[])

                    now = tree[now].child[];

                else

                    return ;

                if (!now)

                    return ;

            }

        }

};

Splay_Tree_Type Make;

int main (int argc, char *argv[])

{

    int N, M;

    read (N);

    read (M);

    int x;

    for (; N--; )

    {

        read (x);

        Make.Insert (x);

    }

    for (; M--; )

    {

        read (x);

        printf ("%d ", Make.Find (x));

    }

    return ;

}