Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 用红黑树TLE，改成BST就9000+ms，W-H-Y？？？

Posted by Harry93 at 2012-07-24 23:05:44 on Problem 2418
```用类是不是慢点啊？？？

#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;
}
```

Followed by: