AA tree

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node node_t;
struct node {
  char *name;
  char *number;
  node_t *left;
  node_t *right;
  int level;
};
node_t *new_node(const char *name, const char *number) {
  node_t *new = (node_t *) malloc(sizeof(node_t));
  new->name = (char *) malloc(20);
  new->number = (char *) malloc(12);
  strcpy(new->name, name);
  strcpy(new->number, number);
  new->left = new->right = NULL;
  new->level = 1;
  return new;
}
node_t *skew(node_t *p) {
  if (!p) return NULL;
  if (!p->left) return p;
  if (p->level != p->left->level) return p;
  node_t *left = p->left;
  p->left = left->right;
  left->right = p;
  return left;
}
node_t *split(node_t *p) {
  if (!p) return NULL;
  if (!p->right) return p;
  if (!p->right->right) return p;
  if (p->level != p->right->right->level) return p;
  node_t *right = p->right;
  p->right = right->left;
  right->left = p;
  right->level++;
  return right;
}
node_t *insert(node_t *p, const char *name, const char *number) {
  if (!p) return new_node(name, number);
  int compare = strcmp(p->name, name);
  if (compare < 0) p->left = insert(p->left, name, number);
  else if (compare > 0) p->right = insert(p->right, name, number);
  p = skew(p);
  p = split(p);
  return p;
}
bool leaf(node_t *p) {
  return !p->right && !p->left;
}
node_t *successor(node_t *p) {
  node_t *t = p->right;
  if (!t) return NULL;
  if (!t->left) return t;
  for (t = t->left; !t && !t->left; t = t->left)
    ;
  return t;
}
node_t *predecessor(node_t *p) {
  node_t *t = p->left;
  if (!t) return NULL;
  if (!t->right) return t;
  for (t = t->right; !t && !t->right; t = t->right)
    ;
  return t;
}
int level(node_t *p) {
  if (!p) return 0;
  return p->level;
}
node_t *decrease_level(node_t *p) {
  if (leaf(p)) {
    p->level = 1;
    return p;
  }
  if (!p->left) return p;
  if (!p->right) return p;
  if (leaf(p->left)) p->left->level = 1;
  int min = level(p->left);
  if (leaf(p->right)) p->right->level = 1;
  if (min > level(p->right)) min = level(p->right);
  min++;
  if (min < level(p)) {
    p->level = min;
    if (min < level(p->right)) p->right->level = min;
  }
  return p;
}
node_t *delete(node_t *p, const char *name) {
  if (!p) return NULL;
  int compare = strcmp(p->name, name);
  if (compare > 0) p->right = delete(p->right, name);
  else if (compare < 0) p->left = delete(p->left, name);
  else {
    if (leaf(p)) return NULL;
    else if (!p->left) {
      node_t *t = successor(p);
      char *name = t->name;
      char *number = t->number;
      p->right = delete(p->right, t->name);
      p->name = name;
      p->number = number;
    }
    else {
      node_t *t = predecessor(p);
      char *name = t->name;
      char *number = t->number;
      p->left = delete(p->left, t->name);
      p->name = name;
      p->number = number;
    }
  }
  p = decrease_level(p);
  p = skew(p);
  if (!p) return NULL;
  if (!p->right) return p;
  p->right = skew(p->right);
  if (!p->right->right) return p;
  p->right->right = skew(p->right->right);
  p = split(p);
  p->right = split(p->right);
  return p;
}
void print_tree(node_t *p) {
  if (!p) {
    puts("NULL");
    return;
  }
  if (p->left) print_tree(p->left);
  for (int i = 0; i < p->level - 1; i++)
    printf("\t");
  printf("%s %s %d\n", p->name, p->number, p->level);
  if (p->right) print_tree(p->right);
}
node_t *search(node_t *p, const char *name) {
  if (!p) return NULL;
  int compare = strcmp(p->name, name);
  if (compare > 0) return search(p->right, name);
  else if (compare < 0) return search(p->left, name);
  return p;
}
void search_g(node_t *p) {
  puts("Search g");
  node_t *found = search(p, "g");
  if (found) puts("Found g");
  else puts("Not Found g");
  puts("----");
}
node_t *delete_and_print(node_t *p, const char *name) {
  printf("Delete %s\n", name);
  node_t *t = delete(p, name);
  print_tree(t);
  puts("----");
  return t;
}
int main(void) {
  char name[20];
  char number[12];
  char buf[BUFSIZ];
  node_t *root = NULL;
  FILE *in = fopen("dat", "r");
  while (fgets(buf, BUFSIZ, in) != NULL) {
    sscanf(buf, "%19s %11s", name, number);
    printf("Insert %s\n", name);
    root = insert(root, name, number);
    print_tree(root);
    puts("----");
  }
  const char * const e[] = { "a", "b", "c", "d", "e", "f", "g" };
  for (int i = 0; i < sizeof(e) / sizeof(e[0]); i++) {
    search_g(root);
    root = delete_and_print(root, e[i]);
  }
  return EXIT_SUCCESS;
}