AVL Tree

/*     r                  u
      / \                / \
     p   u      =>      r   t
        / \            / \
       s   t          p   s
*/
struct node *rotate_left(struct node *r) {
	struct node *u = r->right;
	r->right = u->left;
	u->left = r;
	return u;
}

/*     r                  o
      / \                / \
     o   s      =>      n   r
    / \                    / \
   n   p                  p   s
*/
struct node *rotate_right(struct node *r) {
	struct node *o = r->left;
	r->left = o->right;
	o->right = r;
	return o;
}

int balance = avl_height(r->right) - avl_height(r->left);

      n          n           n           n
     /          /             \           \
    l          l               r           r
   /            \             /             \
  j              m           p               t

left-left   left-right   right-left   right-right

      n                             l
     /                             / \
    l         rotate_right(n)     j   n
   /                                 
  j                             
left-left                        balanced

  n                      n                     m
 /                      /                     / \
l     rotate_left(l)   m    rotate_right(n)  l   n
 \                    /
  m                  l
left-right         left-left                balanced

if (balance <= -2) {
	int bl = avl_height(r->left->right) - 
			avl_height(r->left->left);
	if (bl <= 0) {                      /* left-left   */
		return rotate_right(r);
	} else {                            /* left-right  */
		r->left = rotate_left(r->left);
		return rotate_right(r);
	}
}

  n                      n                         p
   \                      \                       / \
    r   rotate_right(r)    p    rotate_left(n)   n   r
   /                        \
  p                          r
right-left            right-right               balanced

    n                              r
     \                            / \
      r       rotate_left(n)     n   t
       \
        t
 right-right                    balanced

if (balance >= 2) {
	int br = avl_height(r->right->right) - 
			avl_height(r->right->left);
	if (br >= 0) {                      /* right-right */
		return rotate_left(r);
	} else {                            /* right-left  */
		r->right = rotate_right(r->right);
		return rotate_left(r);
	}
}

#include 
#include 
#include 

struct node {
	int key;
	struct node *left, *right;
};

/*
       r
      / \
     p   u
        / \
       s   t
*/
struct node *rotate_left(struct node *r) {
	struct node *u = r->right;
	r->right = u->left;
	u->left = r;
	return u;
}
/*
       r
      / \
     o   s
    / \
   n   p
*/
struct node *rotate_right(struct node *r) {
	struct node *o = r->left;
	r->left = o->right;
	o->right = r;
	return o;
}

int avl_max(int a, int b) {
	return a > b ? a : b;
}

int avl_height(struct node *r) {
	if (r == NULL) {
		return -1;
	} else {
		return 1 + avl_max(avl_height(r->left), avl_height(r->right));
	}
}

struct node *avl_adjust(struct node *r) {
	int balance = avl_height(r->right) - avl_height(r->left);
	if (balance <= -2) {
		int bl = avl_height(r->left->right) - 
					avl_height(r->left->left);
		if (bl <= 0) {                      /* left-left   */
			return rotate_right(r);
		} else {                            /* left-right  */
			r->left = rotate_left(r->left);
			return rotate_right(r);
		}
	}
	if (balance >= 2) {
		int br = avl_height(r->right->right) - 
					avl_height(r->right->left);
		if (br >= 0) {                      /* right-right */
			return rotate_left(r);
		} else {                            /* right-left  */
			r->right = rotate_right(r->right);
			return rotate_left(r);
		}
	}
	return r;
}

struct node *avl_insert(struct node *r, int key) {
	if (r == NULL) {
		r = malloc(sizeof(struct node));
		r->key = key;
		r->left = NULL;
		r->right = NULL;
		return r;
	} else {
		if (key < r->key) {
			r->left = avl_insert(r->left, key);
		} else if (r->key < key) {
			r->right = avl_insert(r->right, key);
		}
		return avl_adjust(r);
	}
}

int avl_minimum(struct node *r) {
	if (r == NULL) return INT_MAX;
	if (r->left == NULL) return r->key;
	return avl_minimum(r->left);
}

int avl_maximum(struct node *r) {
	if (r == NULL) return -INT_MIN;
	if (r->right == NULL) return r->key;
	return avl_maximum(r->right);
}

struct node *avl_delete(struct node *r, int key) {
	if (r == NULL) { return NULL; }

	/* case 1: no child */
	if (r->key == key && r->left == NULL && r->right == NULL) {
		free(r);
		return NULL;
	}
	/* case 2: only right child */
	if (r->key == key && r->left == NULL) {
		free(r);
		return r->right;
	}
	/* case 2: only left child */
	if (r->key == key && r->right == NULL) {
		free(r);
		return r->left;
	}
	/* case 3: both children */
	if (r->key == key && r->left != NULL && r->right != NULL) {
		int min = avl_minimum(r->right);
		r->key = min;
		r->right = avl_delete(r->right, min);
	}

	if (r->key >  key) {
		r->left = avl_delete(r->left, key);
	}
	if (r->key <  key) {
		r->right = avl_delete(r->right, key);
	}

	return avl_adjust(r);
}

void print(struct node *r) {
	if (r == NULL) {
		printf("( )");
		return;
	}
	if (r->left == NULL && r->right == NULL) {
		printf("(%d)", r->key);
		return;
	}
	printf("(");
	print(r->left );
	printf("(%d)", r->key);
	print(r->right);
	printf(")");
}

int main(void) {
	struct node *root = NULL;
	for (int i = 0; i < 7; i++) {
		root = avl_insert(root, i);
		print(root);
		printf("\n");
	}

	root = avl_delete(root, 0);
	print(root);
	printf("\n");
	root = avl_delete(root, 1);
	print(root);
	printf("\n");
	root = avl_delete(root, 2);
	print(root);
	printf("\n");

	return 0;
}