请问第18行是什么意思，X已经是T->left,为什么还会小于T- >left？

Question

AvlTree
Insert( 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 else
8 {
9 T->Element = X; T->Height = 0;
10 T->Left = T->Right = NULL;
11 }
12 }
13 else
14 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 else
21 T = DoubleRotateWithLeft( T );
22 }
23 else
24 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 else
31 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;
}

Answer 1

你理解错了，前面说的只是在T->left 中插入x，但是并不清楚在左子树的什么地方插入第18行的意思是在T的左子树的左子树插入，自然是执行一个向右的单旋转来平衡，如果是在T的左子树的右子树中插入，自然执行一个先左后右的双旋转来平衡