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