用类是不是慢点啊？？？



#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define RED 0
#define BLACK 1
using namespace std;
struct Node
{
    char key[35];
    Node *p, *left, *right;
    int color,n; //RED=0,BLACK=1,DOUBLE_BLACE=2,RED_BLACK=3
};

class RedBlackTree
{
    private:
        Node *root;
        Node *nil;
        int num_of_node;

        Node* TREE_SEARCH( char *key );
        bool LEFT_ROTATE( Node *x );
        bool RIGHT_ROTATE( Node *x );
        bool RB_INSERT_FIXUP( Node *z );
        bool RB_TRANSPLANT( Node *u, Node *v );
        void print( Node *rot );
    public:
        RedBlackTree( );
        Node* TREE_MINIMUM( Node *rot );
        bool RB_INSERT( char *key );
        bool SHOW();
};

RedBlackTree::RedBlackTree( )
{
    nil = new Node;
    //root->key = 0;
    nil->color = BLACK;
    nil->p = nil->left = nil->right = nil;
    root = nil;
    num_of_node = 0;
}

Node* RedBlackTree::TREE_MINIMUM( Node *rot )
{
    while( rot->left != nil )
        rot = rot->left;
    return rot;
}

bool RedBlackTree::SHOW()
{
    //cout << num_of_node << endl;
    print( root );
    return true;
}

void RedBlackTree::print( Node *rot )
{
    if( rot != nil )
    {
        print( rot->left );
        //cout << rot->key << " ";
        printf( "%s ", rot->key );
        printf( "%.4f \n", (float)rot->n/num_of_node*100 );
        //cout << rot->n << endl;
        print( rot->right );
    }
}

Node* RedBlackTree::TREE_SEARCH( char* key )
{
    Node *p = root;
    while( p && strcmp(key,p->key) )
    {
        if( strcmp(key,p->key)<0 )
            p = p->left;
        else
            p = p->right;
    }
    return p;
}

bool RedBlackTree::LEFT_ROTATE( Node *x )
{
        Node *y = x->right;
        x->right = y->left;

        if( y->left != nil )
            y->left->p = x;
        y->p = x->p;

        if( x->p == nil )
            root = y;
        else if( x == x->p->left )
            x->p->left = y;
        else
            x->p->right = y;
        y->left = x;
        x->p = y;

        return true;
}

bool RedBlackTree::RIGHT_ROTATE( Node *x )
{
        Node *y = x->left;
        x->left = y->right;

        if( y->right != nil )
            y->right->p = x;
        y->p = x->p;

        if( x->p == nil )
            root = y;
        else if( x == x->p->right )
            x->p->right = y;
        else
            x->p->left = y;
        y->right = x;
        x->p = y;

        return true;
}

bool RedBlackTree::RB_INSERT( char* key )
{
    num_of_node++;
    Node *z = new Node;
    strcpy( z->key, key );
    z->n = 1;
    bool flag = false;
    Node *y = nil;
    Node *x = root;
    while( x!=nil )
    {
        y = x;
        if( strcmp(z->key,x->key) < 0 )
            x = x->left;
        else if( strcmp(z->key,x->key)==0 )
        {
            flag = true;
            break;
        }
        else
            x = x->right;
    }

    if( flag )
    {
        x->n++;
        delete z;
        return true;
    }
    else
    {
        z->p = y;
        if( y == nil )
            root = z;
        else if( strcmp(z->key,y->key) < 0 )
            y->left = z;
        else y->right = z;
        z->left = nil;
        z->right = nil;
        z->color = RED;

        return 1;   //我把这个隐掉之后就TLE了。

        if( RB_INSERT_FIXUP( z ) ) return true;
        else return false;
    }
}

bool RedBlackTree::RB_INSERT_FIXUP( Node *z )   //那个return 1 就是让它不运行FIXUP函数。
{
    while( z->p->color == RED )
    {
        if( z->p == z->p->p->left )
        {
            Node *y = z->p->p->right;
            if( y->color == RED )
            {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }
            else
            {
                if( z == z->p->right )
                {
                    z = z->p;
                    LEFT_ROTATE( z );
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                RIGHT_ROTATE( z->p->p );
            }
        }
        else
        {
            Node *y = z->p->p->left;
            if( y->color == RED )
            {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }
            else
            {
                if( z == z->p->left )
                {
                    z = z->p;
                    RIGHT_ROTATE( z );
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                LEFT_ROTATE( z->p->p );
            }
        }
    }
    root->color = BLACK;
    return true;
}

bool RedBlackTree::RB_TRANSPLANT( Node *u, Node *v )
{
    if( u->p == nil )
        root = v;
    else if( u == u->p->left )
        u->p->left = v;
    else u->p->right = v;
    v->p = u->p;
    return true;
}

int main()
{
    //freopen( "text.txt", "r", stdin );
    char input[40];
    RedBlackTree tree;
    while( gets(input) )
    {
        //cout << str << endl;
        tree.RB_INSERT( input );
    }
    tree.SHOW();
    cout << endl;
	return 0;
}

• Re:用红黑树TLE，改成BST就9000+ms，W-H-Y？？？ (11) sths 2012-07-25 02:40:18