AvlTreeInsert( ElementType X, AvlTree T){1 if( T == NULL)2 {3 /* Create and return a one-onde tree */4 T = malloc( sizeof( struct AvlNode ) );5 if( T == NULL )6 FatalError( "Out of space!!!");7 else8 {9 T->Element = X; T->Height = 0;10 T->Left = T->Right = NULL;11 }12 }13 else14 if( X < T->Element )15 {16 T->left = Insert(x, T->left );17 if( Height( T->left ) - Height( T->Right ) == 2 )18 if( X < T->Left->Element )19 T = SingleRotatewithLeft( T );20 else21 T = DoubleRotateWithLeft( T );22 }23 else24 if( X > T->Element )25 {26 T->Right = Insert( X, T->Right );27 if( Height( T->Right ) - Height( T->Left ) == 2 )28 if( X > T->Right->Element )29 T = SingleRotateWithRight( T );30 else31 T = DoubleRotateWithRight( T );32 }33 /* Else X is in the tree already; we'll do nothing */34 T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;35 return T;}