0001 /****************************************************************************************** 0002 * Test of RedBlack Tree 0003 ******************************************************************************************/ 0004 #include "RedBlack_test.h" 0005 0006 /****************************************************************************************** 0007 * Test a RedBlack 0008 ******************************************************************************************/ 0009 template <typename T> void testRedBlack( Rank n ) { 0010 RedBlack<T> rb; 0011 //for ( int i = 0; i < 256; i++ ) { 0012 // int e = i % 2 ? i : -i; 0013 // printf("Inserting "); print(e); printf(" ...\n"); 0014 // BinNodePosi<T> p = rb.insert(e); 0015 // if ( p->data != e) { print(p->data); printf(" <> "); print(e); printf("\n"); } 0016 // printf("Done with"), print(p), printf("\n"), print(rb); 0017 //} 0018 //return; 0019 while ( rb.size() < n ) { 0020 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0021 switch ( dice ( 6 ) ) { 0022 case 0: { //查找(概率 = 1/6) 0023 printf ( "Searching for " ); print ( e ); printf ( " ...\n" ); 0024 BinNodePosi<T> p = rb.search ( e ); 0025 p ? 0026 printf ( "Found with" ), print ( p ), printf ( "\n" ) : 0027 printf ( "Not found\n" ); 0028 break; 0029 } 0030 case 1: 0031 case 2: { //删除(概率 = 2/6) 0032 printf ( "Removing " ); print ( e ); printf ( " ...\n" ); 0033 rb.remove ( e ) ? printf ( "Done\n" ), print ( rb ) : printf ( "Not exists\n" ); 0034 break; 0035 } 0036 default: { //插入(概率 = 3/6) 0037 printf ( "Inserting " ); print ( e ); printf ( " ...\n" ); 0038 BinNodePosi<T> p = rb.insert ( e ); 0039 if ( p->data != e ) { print ( p->data ); printf ( " <> " ); print ( e ); printf ( "\n" ); } 0040 printf ( "Done with" ), print ( p ), printf ( "\n" ), print ( rb ); 0041 break; 0042 } 0043 } 0044 } 0045 while ( rb.size() > 0 ) { 0046 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0047 printf ( "Removing " ); print ( e ); printf ( " ...\n" ); 0048 rb.remove ( e ) ? printf ( "Done\n" ), print ( rb ) : printf ( "Not exists\n" ); 0049 } 0050 } 0051 0052 /****************************************************************************************** 0053 * 测试主入口 0054 ******************************************************************************************/ 0055 int main( int argc, char* argv[] ) { 0056 if ( 2 > argc ) { printf( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0057 srand((unsigned int)time(NULL)); //随机种子 0058 //srand( 31415926 ); //固定种子(假种子,调试用) 0059 testRedBlack<int>( atoi( argv[1] ) ); //元素类型可以在这里任意选择 0060 return 0; 0061 }