用C语言实现一个AVL树

AVL树是一种平衡二叉树，它的每个节点的左右子树的高度相差不超过1。这个性质使得AVL树插入和删除操作的时间复杂度能够保持在对数级别，这与二叉搜索树相比具有较高的效率。

下面是一个用C语言实现AVL树的示例代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct AVLTreeNode {
  int key;
  int height;
  struct AVLTreeNode *left;
  struct AVLTreeNode *right;
} AVLTreeNode;

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

int height(AVLTreeNode *node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

AVLTreeNode* newAVLTreeNode(int key) {
  AVLTreeNode* node = (AVLTreeNode*) malloc(sizeof(AVLTreeNode));
  node->key = key;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return node;
}

AVLTreeNode* rightRotate(AVLTreeNode *y) {
  AVLTreeNode *x = y->left;
  AVLTreeNode *T2 = x->right;
  x->right = y;
  y->left = T2;
  y->height = max(height(y->left), height(y->right)) + 1;
  x->height = max(height(x->left), height(x->right)) + 1;
  return x;
}

AVLTreeNode* leftRotate(AVLTreeNode *x) {
  AVLTreeNode *y = x->right;
  AVLTreeNode *T2 = y->left;
  y->left = x;
  x->right = T2;
  x->height = max(height(x->left), height(x->right)) + 1;
  y->height = max(height(y->left), height(y->right)) + 1;
  return y;
}

int getBalance(AVLTreeNode *node) {
  if (node == NULL) {
    return 0;
  }
  return height(node->left) - height(node->right);
}

AVLTreeNode* insert(AVLTreeNode* node, int key) {
  if (node == NULL) {
    return newAVLTreeNode(key);
  }
  if (key < node->key) {
    node->left = insert(