Language: C

#include <stdio.h>
#include <string.h>

#define MAX_COMMAND_NUM 2000000000

#define PLUS_DEPTH     1
#define MINUS_DEPTH  (-1)

typedef struct ST_TREE_POINT TreePoint_t;

struct ST_TREE_POINT{
	int key;				/* key value */
	int depth;				/* Depth */
	TreePoint_t *top;		/* Top   Point */
	TreePoint_t *left;		/* Left  Point */
	TreePoint_t *right;		/* Right Point */
}AVL_TREE;

static void InsertPorocess(TreePoint_t *ptTreePoint, int key);
static void InsertLeftProcess(TreePoint_t *ptTreePoint, int key, int depth);
static void InsertRightProcess(TreePoint_t *ptTreePoint, int key, int depth);
static void ExtractPorocess(TreePoint_t *ptTreePoint);
static void CompareTreeDepth(TreePoint_t *ptTreePoint, int depth_l, int depth_r);
static void ChangeDepth(TreePoint_t *ptTreePoint, int value);
static void AllFreeProcess(TreePoint_t *ptTreePoint);

int main(void)
{
	int key;							/* insert key */
	int command[8];						/* command name */
	TreePoint_t *ptTreeTemp;			/* Tree Temp Data */
	TreePoint_t *ptRootPoint;			/* Tree Root Point */
	int loop = 0;
	
	/* Init Root Tree */
	ptRootPoint = NULL;
	
	/* get Name & time */
	while(((scanf("%s %d", command, &key)) != EOF) && loop <= MAX_COMMAND_NUM)
	{
		/* set Root point */
		if(ptRootPoint != NULL)
		{
			while(( ptRootPoint->top != NULL ) && ( ptRootPoint->depth != 0 ))
			{
				ptRootPoint = ptRootPoint->top;
			}
		}
		
		if( strcmp(command, "end") == 0 ) /* End Process */
		{
			break;
		}
		else if( strcmp(command, "insert") == 0 ) /* Insert Process */
		{
			InsertPorocess( ptRootPoint, key );
		}
		else if( strcmp(command, "extract") == 0 ) /* Extract Process */
		{
			ExtractPorocess( ptRootPoint );
		}
		else
		{
			/* error input */
		}
		loop++;
	}
	
	/* all free process */
	AllFreeProcess(ptRootPoint);
	
    return 0;
}

static void InsertPorocess(TreePoint_t *ptTreePoint, int key)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	if(ptTreePoint == NULL)
	{
		ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
		ptInsertData->key     = key;
		ptInsertData->depth   = 0;
		ptInsertData->top     = NULL;
		ptInsertData->left    = NULL;
		ptInsertData->right   = NULL;

		ptTreePoint = ptInsertData;
	}
	else if(ptTreePoint != NULL)
	{
		if(ptTreePoint->key > key)
		{
			InsertLeftProcess(ptTreePoint, key, 1);
		}
		else
		{
			InsertRightProcess(ptTreePoint, key, 1);
		}
	}
	
}

static void InsertLeftProcess(TreePoint_t *ptTreePoint, int key, int depth)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	if(ptTreePoint->left == NULL)
	{
		ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
		ptInsertData->key     = key;
		ptInsertData->depth   = depth;
		ptInsertData->top     = ptTreePoint;
		ptInsertData->left    = NULL;
		ptInsertData->right   = NULL;

		ptTreePoint->left = ptInsertData;
		
		/* if MAX depth change */
		if(ptTreePoint->right == NULL && depth > 1)
		{
			CompareTreeDepth(ptTreePoint->top, depth, 0);
		}
	}
	else
	{
		ptTreePoint = ptTreePoint->left;
		
		if(ptTreePoint->key > key)
		{
			InsertLeftProcess(ptTreePoint, key, (depth + 1));
		}
		else
		{
			InsertRightProcess(ptTreePoint, key, (depth + 1));
		}
	}
}

static void InsertRightProcess(TreePoint_t *ptTreePoint, int key, int depth)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	if(ptTreePoint->right == NULL)
	{
		ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
		ptInsertData->key     = key;
		ptInsertData->depth   = depth;
		ptInsertData->top     = ptTreePoint;
		ptInsertData->left    = NULL;
		ptInsertData->right   = NULL;

		ptTreePoint->right = ptInsertData;
		
		/* if MAX depth change */
		if(ptTreePoint->left == NULL && depth > 1)
		{
			CompareTreeDepth(ptTreePoint->top, 0, depth);
		}
	}
	else
	{
		ptTreePoint = ptTreePoint->right;
		
		if(ptTreePoint->key > key)
		{
			InsertLeftProcess(ptTreePoint, key, (depth + 1));
		}
		else
		{
			InsertRightProcess(ptTreePoint, key, (depth + 1));
		}
	}
}

static void ExtractPorocess(TreePoint_t *ptTreePoint)
{
	TreePoint_t * ptTempTree;
	if(ptTreePoint != NULL)
	{
		/* serch max key */
		while(ptTreePoint->right != NULL)
		{
			ptTreePoint = ptTreePoint->right;
		}
		
		printf("%d\n", ptTreePoint->key);
		
		if(ptTreePoint->left != NULL)
		{
			ptTempTree = ptTreePoint->left;
			
			ptTreePoint = ptTreePoint->top;
			free(ptTreePoint->right);
			ptTreePoint->right = ptTempTree;
			ChangeDepth(ptTempTree,  MINUS_DEPTH);
			CompareTreeDepth(ptTreePoint, 0, ptTempTree->depth);
		}
		else
		{
			ptTreePoint = ptTreePoint->top;
			free(ptTreePoint->right);
			CompareTreeDepth(ptTreePoint, 0, ptTreePoint->depth);
		}
	}
}

static void CompareTreeDepth(TreePoint_t *ptTreePoint, int depth_l, int depth_r)
{
	TreePoint_t * ptTempTree;
	TreePoint_t * ptNewTopTree;
	
	if(depth_l == 0)
	{
		ptTempTree = ptTreePoint;
		depth_l = ptTempTree->depth;
		
		/* serch max left depth */
		while(ptTempTree->left != NULL)
		{
			ptTempTree = ptTempTree->left;
			depth_l = ptTempTree->depth;
		}
	}
	else if(depth_r == 0)
	{
		ptTempTree = ptTreePoint;
		depth_r = ptTempTree->depth;
		/* serch max right depth */
		while(ptTempTree->right != NULL)
		{
			ptTempTree = ptTempTree->right;
			depth_r = ptTempTree->depth;
		}
	}
	
	/* equilibrium tree */
	if(depth_r - depth_l >= 2)
	{
		/* right is new Top tree */
		ptNewTopTree = ptTreePoint->right;
		
		/* change Tree top */
		ptNewTopTree->top = ptTreePoint->top;
		ptTempTree = ptNewTopTree->left;
		ptNewTopTree->left = ptTreePoint;
		ptNewTopTree->depth--;
		ChangeDepth(ptNewTopTree->right,  MINUS_DEPTH);
		
		/* change Top to left */
		ptTreePoint->top = ptNewTopTree;
		ptTreePoint->right = ptTempTree;
		ptTreePoint->depth++;
		ChangeDepth(ptTreePoint->left,  PLUS_DEPTH);
	}
	else if(depth_l - depth_r >= 2)
	{
		/* left is new Top tree */
		ptNewTopTree = ptTreePoint->left;
		
		/* change Tree top */
		ptNewTopTree->top = ptTreePoint->top;
		ptTempTree = ptNewTopTree->right;
		ptNewTopTree->right = ptTreePoint;
		ptNewTopTree->depth--;
		ChangeDepth(ptNewTopTree->right,  MINUS_DEPTH);
		
		/* change Top to right */
		ptTreePoint->top = ptNewTopTree;
		ptTreePoint->left = ptTempTree;
		ptTreePoint->depth++;
		ChangeDepth(ptTreePoint->left,  PLUS_DEPTH);
	}
}

static void ChangeDepth(TreePoint_t *ptTreePoint, int value)
{
	ptTempTree->depth += value;
	
	if(ptTreePoint->left != NULL)
	{
		ChangeDepth(ptTreePoint->left, value);
	}
	if(ptTreePoint->right != NULL)
	{
		ChangeDepth(ptTreePoint->right, value);
	}
}

static void AllFreeProcess(TreePoint_t *ptTreePoint)
{
	if(ptTreePoint->left != NULL)
	{
		AllFreeProcess(ptTreePoint->left);
	}
	if(ptTreePoint->right != NULL)
	{
		AllFreeProcess(ptTreePoint->right);
	}
	
	free(ptTreePoint);
}




Compiler output:
main.c: In function 'main':
main.c:50:28: error: passing argument 1 of 'strcmp' from incompatible pointer type [-Wincompatible-pointer-types]
   50 |                 if( strcmp(command, "end") == 0 ) /* End Process */
      |                            ^~~~~~~
      |                            |
      |                            int *
In file included from main.c:2:
/usr/include/string.h:156:32: note: expected 'const char *' but argument is of type 'int *'
  156 | extern int strcmp (const char *__s1, const char *__s2)
      |                    ~~~~~~~~~~~~^~~~
main.c:54:33: error: passing argument 1 of 'strcmp' from incompatible pointer type [-Wincompatible-pointer-types]
   54 |                 else if( strcmp(command, "insert") == 0 ) /* Insert Process */
      |                                 ^~~~~~~
      |                                 |
      |                                 int *
/usr/include/string.h:156:32: note: expected 'const char *' but argument is of type 'int *'
  156 | extern int strcmp (const char *__s1, const char *__s2)
      |                    ~~~~~~~~~~~~^~~~
main.c:58:33: error: passing argument 1 of 'strcmp' from incompatible pointer type [-Wincompatible-pointer-types]
   58 |                 else if( strcmp(command, "extract") == 0 ) /* Extract Process */
      |                                 ^~~~~~~
      |                                 |
      |                                 int *
/usr/include/string.h:156:32: note: expected 'const char *' but argument is of type 'int *'
  156 | extern int strcmp (const char *__s1, const char *__s2)
      |                    ~~~~~~~~~~~~^~~~
main.c: In function 'InsertPorocess':
main.c:81:47: error: implicit declaration of function 'malloc' [-Wimplicit-function-declaration]
   81 |                 ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
      |                                               ^~~~~~
main.c:3:1: note: include '<stdlib.h>' or provide a declaration of 'malloc'
    2 | #include <string.h>
  +++ |+#include <stdlib.h>
    3 | 
main.c:81:47: warning: incompatible implicit declaration of built-in function 'malloc' [-Wbuiltin-declaration-mismatch]
   81 |                 ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
      |                                               ^~~~~~
main.c:81:47: note: include '<stdlib.h>' or provide a declaration of 'malloc'
main.c: In function 'InsertLeftProcess':
main.c:110:47: warning: incompatible implicit declaration of built-in function 'malloc' [-Wbuiltin-declaration-mismatch]
  110 |                 ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
      |                                               ^~~~~~
main.c:110:47: note: include '<stdlib.h>' or provide a declaration of 'malloc'
main.c: In function 'InsertRightProcess':
main.c:146:47: warning: incompatible implicit declaration of built-in function 'malloc' [-Wbuiltin-declaration-mismatch]
  146 |                 ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
      |                                               ^~~~~~
main.c:146:47: note: include '<stdlib.h>' or provide a declaration of 'malloc'
main.c: In function 'ExtractPorocess':
main.c:194:25: error: implicit declaration of function 'free' [-Wimplicit-function-declaration]
  194 |                         free(ptTreePoint->right);
      |                         ^~~~
main.c:194:25: note: include '<stdlib.h>' or provide a declaration of 'free'
main.c:194:25: warning: incompatible implicit declaration of built-in function 'free' [-Wbuiltin-declaration-mismatch]
main.c:194:25: note: include '<stdlib.h>' or provide a declaration of 'free'
main.c:202:25: warning: incompatible implicit declaration of built-in function 'free' [-Wbuiltin-declaration-mismatch]
  202 |                         free(ptTreePoint->right);
      |                         ^~~~
main.c:202:25: note: include '<stdlib.h>' or provide a declaration of 'free'
main.c: In function 'ChangeDepth':
main.c:278:9: error: 'ptTempTree' undeclared (first use in this function)
  278 |         ptTempTree->depth += value;
      |         ^~~~~~~~~~
main.c:278:9: note: each undeclared identifier is reported only once for each function it appears in
main.c: In function 'AllFreeProcess':
main.c:301:9: warning: incompatible implicit declaration of built-in function 'free' [-Wbuiltin-declaration-mismatch]
  301 |         free(ptTreePoint);
      |         ^~~~
main.c:301:9: note: include '<stdlib.h>' or provide a declaration of 'free'