АВЛ дерево

#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <malloc.h> 
#include <time.h> 
#include <Windows.h>  
typedef int ElementType; 
typedef struct AvlNode *Position; 
typedef struct AvlNode *AvlTree;  
struct AvlNode 
{             
ElementType Element;             
AvlTree Left;             
AvlTree Right;             
int Height;         };  
AvlTree MakeEmpty( AvlTree T ); 
Position Find( ElementType X, AvlTree T ); 
Position FindMin( AvlTree T ); 
Position FindMax( AvlTree T ); 
AvlTree Insert( ElementType X, AvlTree T ); 
ElementType Retrieve( Position P ); 
void printTree(AvlTree T, int l = 0); //функция удаления вершины и ее поддеревьев 
AvlTree MakeEmpty( AvlTree T )  
{   if( T != NULL )   
{     MakeEmpty( T->Left );     
MakeEmpty( T->Right );     
free( T );   }   
  return NULL; }  // поиск вершины со значением X 
  Position Find( ElementType X, AvlTree T ) 
  {   if( T == NULL )     
  return NULL;     
  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; }  
//функция возвращает вес вершины  
int Height( Position P ) 
{   if( P == NULL )     
return -1;   
else     
return P->Height;   
}  
//функция возвращает максимальное из двух чисел 
int Max( int Lhs, int Rhs )  
{  if(Lhs > Rhs)   
return Lhs;   
return Rhs; }  
/*функция выполняет правый поворот между вершиной K2 и ее левым потомком*/ 
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)) + 1;  
K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;   
return K1;  //Новый корень 
}  
/*функция выполняет левый поворот между вершиной K1 и ее правым потомком*/ 
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)) + 1;   
K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;   
return K2;  //новый корень 
}  
//функция выполняет двойной лево-правый поворот 
Position DoubleRotateWithLeft( Position K3 ) 
{   // поворот между K1 и K2/   
K3->Left = SingleRotateWithRight( K3->Left );   // поворот между K3 и K2   
return SingleRotateWithLeft( K3 );   
}  
//функция выполняет двойной право-левый поворот  
Position DoubleRotateWithRight( Position K1 ) 
{   // поворот между K3 и K2   
K1->Right = SingleRotateWithLeft( K1->Right );   // поворот между K1 и K2   
return SingleRotateWithRight( K1 ); }  
//функция вставки вершины в АВЛ-дерево 
AvlTree Insert( ElementType X, AvlTree T )
{   if( T == NULL )   
{     T = (AvlTree) malloc(sizeof(AvlNode));     
if( T == NULL )       
printf("Недостаточно памяти!!!\n" );     
else {       T->Element = X; T->Height = 0;       
T->Left = T->Right = NULL;     }   }   
else if( X < T->Element ) 
{     T->Left = Insert( X, T->Left );     
if( Height( T->Left ) - Height( T->Right ) == 2 )       
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 ) == 2 )         
if( X > T->Right->Element )           
T = SingleRotateWithRight( T );         
else           
T = DoubleRotateWithRight( T );   
}   
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;   
return T; 
}    
//функция возвращает значение, хранящееся в вершине 
ElementType Retrieve( Position P ) 
{   return P->Element; }  
//функция вывода АВЛ-дерева на печать 
void printTree(AvlTree T, int l)
{   
int i;   
if ( T != NULL ) 
{     
printTree(T->Right, l+1);     
for (i=0; i < l; i++)   
printf("    ");     
printf ("%4ld", Retrieve ( T ));     
printTree(T->Left, l+1);   
}   
else printf("\n"); 
}  
void main() 
{  
SetConsoleCP(1251);     
SetConsoleOutputCP(1251);  
int i, *a, maxnum;   
AvlTree T;     
Position P;     
int j = 0;   
printf("Введите количество элементов maxnum : ");   
scanf("%d",&maxnum); printf("\n");     
a = (int*) malloc(sizeof(int)*maxnum);   
srand(time(NULL)*1000);   // генерация массива   
for (i = 0; i < maxnum; i++)     
a[i] = rand()%100;   
printf("Вывод сгенерированной последовательности\n");   
for (i = 0; i < maxnum; i++)     
printf("%d \n\n",a[i]);      // добавление элементов в АВЛ-дерево     
T = MakeEmpty( NULL );   
for( i = 0; i < maxnum; i++ )         
T = Insert( a[i], T );   
printf("Вывод АВЛ-дерева\n");   
printTree(T);   
  printf("\nВведите вершину для поиска\n");   
  int temp; 
  scanf("%d",&temp);   
  Position Temp_node=NULL;   //поиск вершины с заданным номером temp  
Temp_node = Find(temp,T);   
if (Temp_node!=NULL)   
printf("\nВершина %d найдена\n",Temp_node->Element);   
else    
printf("\nТакой вершины нет!\n");   
getch();   
printf("\nMin = %d, Max = %d\n", 
Retrieve(FindMin(T)),  
Retrieve(FindMax(T)));   // удаление АВЛ-дерева   
T = MakeEmpty(T);   
free(a);   
getch();  
return; }