AVL Tree

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define max(a, b) \
   ({ __typeof__ (a) _a = (a); \
      __typeof__ (b) _b = (b); \
      _a > _b ? _a : _b; })
typedef struct node_t node_t;
struct node_t {
  int *val;
  int height;
  node_t *left, *right;
};
int main(void);
static node_t *balance(node_t *node);
static node_t *delete(node_t *node, int val);
static node_t *find(node_t *node, int val);
static node_t *insert(node_t *node, int val);
static node_t *move_down(node_t *node, node_t *right);
static node_t *new_node(int val);
static node_t *rotate_left(node_t *node);
static node_t *rotate_right(node_t *node);
static void describe_find(node_t *node, int val);
static void free_node(node_t *node);
static int height(node_t *node);
static void print_node(node_t *node, int depth);
static int random_int(int upper);
static int random_int(int upper) {
  return (int) ((rand() / ((double) RAND_MAX + 1.)) * upper);
}
static node_t *new_node(int val) {
  node_t *new = (node_t *) malloc(sizeof(node_t));
  new->val = (int *) malloc(sizeof(int));
  *new->val = val;
  new->height = 1;
  new->left = new->right = NULL;
  return new;
}
static node_t *rotate_left(node_t *node) {
  node_t *p = node->right;
  node->right = p->left;
  p->left = balance(node);
  return balance(p);
}
static node_t *rotate_right(node_t *node) {
  node_t *p = node->left;
  node->left = p->right;
  p->right = balance(node);
  return balance(p);
}
static node_t *find(node_t *node, int val) {
  if (!node) return NULL;
  if (*node->val == val)
    return node;
  else if (*node->val > val)
    return find(node->left, val);
  else
    return find(node->right, val);
}
static void describe_find(node_t *node, int val) {
  if (!node) return;
  if (*node->val == val)
    printf("%d found.\n", val);
  else if (*node->val > val) {
    puts("left");
    describe_find(node->left, val);
  } else {
    puts("right");
    describe_find(node->right, val);
  }
}
static int height(node_t *node) {
  return node ? node->height : 0;
}
static node_t *balance(node_t *node) {
  if (height(node->right) - height(node->left) < -1) {
    if (height(node->left->right) - height(node->left->left) > 0) node->left = rotate_left(node->left);
    return rotate_right(node);
  }
  if (height(node->left) - height(node->right) < -1) {
    if (height(node->right->left) - height(node->right->right) > 0) node->right = rotate_right(node->right);
    return rotate_left(node);
  }
  if (node) node->height = max(height(node->left), height(node->right)) + 1;
  return node;
}
static node_t *insert(node_t *node, int val) {
  if (find(node, val)) return node;
  if (!node) return new_node(val);
  if (*node->val > val)
    node->left = insert(node->left, val);
  else
    node->right = insert(node->right, val);
  return balance(node);
}
static node_t *move_down(node_t *node, node_t *right) {
  if (!node) return right;
  node->right = move_down(node->right, right);
  return balance(node);
}
static void free_node(node_t *node) {
  free(node->val);
  free(node);
}
static node_t *delete(node_t *node, int val) {
  node_t *left, *right;
  if (!node) return NULL;
  if (*node->val == val) {
    left = node->left;
    right = node->right;
    free_node(node);
    return move_down(left, right);
  } else {
    if (*node->val > val)
      node->left = delete(node->left, val);
    else
      node->right = delete(node->right, val);
    return balance(node);
  }
}
static void print_node(node_t *node, int depth) {
  int i;
  if (!node) return;
  if (node->left) print_node(node->left, depth + 1);
  for (i = 0; i < depth; i++)
    printf("\t");
  printf("%2d:%d\n", *node->val, node->height);
  if (node->right) print_node(node->right, depth + 1);
}
int main(void) {
  const int n = 10, m = 100;
  int i, c = 0, a[n], b[] = { 5, 9, 6, 11, 17, 19, 21, 23, 25, 35, 30, 28 };
  node_t *root = NULL;
  srand((unsigned) time(NULL));
  for (i = 0; i < n; i++) {
    a[i] = random_int(m);
    root = insert(root, a[i]);
    print_node(root, 0);
    puts("----------------------------------------");
  }
  for (i = 0; i < m; i++) {
    if (!find(root, i)) {
      printf("%2d ", i);
      if (++c % 20 == 0) puts("");
    }
    if (i == m - 1) puts("");
  }
  puts("----------------------------------------");
  for (i = 0; i < n; i++) {
    root = delete(root, a[i]);
    print_node(root, 0);
    puts("----------------------------------------");
  }
  for (i = 0; i < sizeof(b) / sizeof(int); i++) {
    root = insert(root, b[i]);
  }
  print_node(root, 0);
  puts("----------------------------------------");
  describe_find(root, 11);
  return 0;
}