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