typedef int ElementType;

 #ifndef _AVLTREE_H_

 #define _AVLTREE_H_

 struct AvlNode;

 typedef struct AvlNode *Position;

 typedef struct AvlNode *AvlTree;

 AvlTree MakeEmpty(AvlTree T);

 Position Find(ElementType X, AvlTree T);

 Position FindMin(AvlTree T);

 Position FindMax(AvlTree T);

 AvlTree Insert(ElementType X, AvlTree T);

 AvlTree Delete(ElementType X, AvlTree T);

 ElementType Retrieve(Position P);

 void PrintTree(AvlTree T);

 #endif

 #include "fatal.h"

 #include "avltree.h"

 #include <malloc.h>

 struct AvlNode

 {

     ElementType Element;

     AvlTree Left;

     AvlTree Right;

     int     Height;

 };

 AvlTree MakeEmpty(AvlTree T) // 同二叉查找树

 {

     if(T != NULL) // 递归终止

     {

         MakeEmpty(T->Left);

         MakeEmpty(T->Right);

         free(T);

     }

     return T;

 }

 Position Find(ElementType X, AvlTree T) // 同二叉查找树

 {

     if(T == NULL)

         return NULL;

     else if(X < T->Element)

     {

         return Find(X, T->Left);

     }

     else if(X > T->Element)

     {

         return Find(X, T->Right);

     }

     else

         return T;

 }

 Position FindMin(AvlTree T) // 递归实现

 {

     if(T == NULL)

         return NULL;

     else if(T->Left == NULL)

         return T;

     else

         return FindMin(T->Left);

 }

 Position FindMax(AvlTree T) // 非递归实现

 {

     if(T != NULL)

         while(T->Right != NULL)

             T = T->Right;

     return T;

 }

 static int Height(Position P)

 {

     if(P == NULL)

         return -; // 空树高度为-1

     else

         return P->Height;

 }

 static int Max(int Left, int Right)

 {

     return Left > Right ? Left : Right;

 }

 /* This function can be called only if K2 has a left child */

 /* Perform a rotate between a node (K2) and its left child */

 /* Update heights, then return new root */

 static Position SingleRotateWithLeft(Position K2)

 {

     Position K1;

     K1 = K2->Left;

     K2->Left = K1->Right;

     K1->Right = K2;

     K2->Height = Max(Height(K2->Left), Height(K2->Right)) + ;

     K1->Height = Max(Height(K1->Left), Height(K1->Right)) + ;

     return K1;  /* New root */

 }

 /* This function can be called only if K1 has a right child */

 /* Perform a rotate between a node (K1) and its right child */

 /* Update heights, then return new root */

 static Position SingleRotateWithRight(Position K1)

 {

     Position K2;

     K2 = K1->Right;

     K1->Right = K2->Left;

     K2->Left = K1;

     K1->Height = Max(Height(K1->Left), Height(K1->Right)) + ;

     K2->Height = Max(Height(K2->Left), Height(K2->Right)) + ;

     return K2;  /* New root */

 }

 /* This function can be called only if K3 has a left */

 /* child and K3's left child has a right child */

 /* Do the left-right double rotation */

 /* Update heights, then return new root */

 static Position DoubleRotateWithLeft(Position K3)

 {

     /* Rotate between K1 and K2 */

     K3->Left = SingleRotateWithRight(K3->Left);

     /* Rotate between K3 and K2 */

     return SingleRotateWithLeft(K3);

 }

 /* This function can be called only if K1 has a right */

 /* child and K1's right child has a left child */

 /* Do the right-left double rotation */

 /* Update heights, then return new root */

 static Position DoubleRotateWithRight(Position K1)

 {

     /* Rotate between K3 and K2 */

     K1->Right = SingleRotateWithLeft(K1->Right);

     /* Rotate between K1 and K2 */

     return SingleRotateWithRight(K1);

 }

 // 1. 找位置; 2. 插入; 3. 平衡性; 4. 旋转

 AvlTree Insert(ElementType X, AvlTree T)

 {

     if(T == NULL)

     {

         /* Create and return a one-node tree */

         T = (AvlTree)malloc(sizeof(struct AvlNode));

         if(T == NULL)

             FatalError("Out of space!");

         else

         {

             T->Left = T->Right = NULL;

             T->Height = ;

             T->Element = X;

         }

     }

     else if(X < T->Element)

     {

         T->Left = Insert(X, T->Left);

         // 因为插到左边了, 所以肯定是左边比较高

         if(Height(T->Left) - Height(T->Right) == )

         {

             if(X < T->Left->Element)

                 T = SingleRotateWithLeft(T);

             else

                 T = DoubleRotateWithLeft(T);

         }

     }

     else if(X > T->Element)

     {

         T->Right = Insert(X, T->Right);

         // 插到右边了, 右边比较高

         if(Height(T->Right) - Height(T->Left) == )

         {

             if(X > T->Right->Element)

                 T = SingleRotateWithRight(T);

             else

                 T = DoubleRotateWithRight(T);

         }

     }

     /* Else X is in the tree already; we'll do nothing */

     T->Height = Max(Height(T->Left), Height(T->Right)) + ;

     return T;

 }

 AvlTree Delete(ElementType X, AvlTree T)

 {

     printf( "Sorry; Delete is unimplemented; %d remains\n", X );

     return T;

 }

 ElementType Retrieve(Position P)

 {

     return P->Element;

 }

 void PrintTree(AvlTree T)

 {

     if( T != NULL)

     {

         PrintTree(T->Left);

         printf("%d ", T->Element);

         PrintTree(T->Right);

     }

 }

 #include "avltree.h"

 #include <stdio.h>

 main( )

 {

     AvlTree T;

     Position P;

     int i;

     int j = ;

     T = MakeEmpty( NULL );

     for( i = ; i < ; i++, j = ( j +  ) %  )

         T = Insert( j, T );

     for( i = ; i < ; i++ )

         if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i )

             printf( "Error at %d\n", i );

  /* for( i = 0; i < 50; i += 2 )

         T = Delete( i, T );

     for( i = 1; i < 50; i += 2 )

         if( ( P = Find( i, T ) ) == NULL || Retrieve( P ) != i )

             printf( "Error at %d\n", i );

     for( i = 0; i < 50; i += 2 )

         if( ( P = Find( i, T ) ) != NULL )

             printf( "Error at %d\n", i );

 */

     printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ),

                Retrieve( FindMax( T ) ) );

     PrintTree(T);

     return ;

 }