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 ( Rank 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    //srand( 31415926 ); //固定种子（假种子，调试用）
0050    testAVL<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择
0051    return 0;
0052 }