node* insertNode(int key, node* root)
{
  node *parent, *cur, *child;
  assert (root != NULL);
  if (searchNode(key, root, &parent)) //结点已存在

    return root;
  else
  {
    cur = (node*)malloc(sizeof(node));
    cur->parent = parent;
    cur->key = key;
    cur->left = NULL;
    cur->right = NULL;
    cur->balance = 0;
    if (key<parent->key)
    {
      parent->left = cur;
      child = parent->left;
    }
    else
    {
      parent->right = cur;
      child = parent->right;
    }
   
    while ((parent != NULL)) //查找需要调整的最小子树

    {
      if (child == parent->left)
        if (parent->balance == -1)
        {
          parent->balance = 0;
          return root;
        }
        else if (parent->balance == 1)
        {
          parent->balance = 2;
          break;
        }
        else
        {
          parent->balance = 1;
          child = parent;
          parent = parent->parent;
        }
      else if (parent->balance == 1)
      {
        parent->balance = 0;
        return root;
      }
      else if (parent->balance == -1)
      {
        parent->balance = -2;
        break;
      }
      else
      {
        parent->balance = -1;
        child = parent;
        parent = parent->parent;
      }
    }
   
    if (parent == NULL)
      return root;
    return adjustAVL(root, parent, child);
  }
}

node* deleteNode(int key, node* root)
{
  node *dNode, *parent, *child, *tp;
  int temp, tc;
  assert(root!=NULL);
  if (!searchNode(key, root, &parent))
    return root;
  else
  {
    if (parent == NULL)
      dNode = root;
    else if ((parent->left!=NULL)&&(parent->left->key==key))
      dNode = parent->left;
    else dNode = parent->right;

    child = dNode;
    while ((child->left!=NULL)||(child->right!=NULL)) //确定需要删除的结点
    {
      if (child->balance == 1)
        child = preNode(dNode);
      else child = nextNode(dNode);
      temp = child->key;
      child->key = dNode->key;
      dNode->key = temp;
      dNode = child;
    }
   
    child = dNode;
    parent = dNode->parent;
      
    while ((parent != NULL)) //查找需要调整的最小子树
    {
      if (child == parent->left)
        if (parent->balance == 1)
        {
          parent->balance = 0;
          child = parent;
          parent = parent->parent;
        }
        else if (parent->balance == -1)
        {
          parent->balance = -2;
          child = parent->right;
          temp = parent->right->balance;//临时变量保存
          tp = parent->parent;//临时变量保存
          if (tp != NULL)
            if (parent == tp->left)
              tc = 1;
            else tc = -1;
          else tc = 0;
         
          root = adjustAVL(root, parent, child);
         
          if (temp == 0)
            break;
          else
          {
            if (tc == 1)
              child = tp->left;
            else if (tc == -1)
              child = tp->right;
            parent = tp;
          }

        }
        else
        {
          parent->balance = -1;
          break;
        }
      else if (parent->balance == -1)
      {
        parent->balance = 0;
        child = parent;
        parent = parent->parent;
      }
      else if (parent->balance == 1)
      {
        parent->balance = 2;
        child = parent->left;
        temp = parent->left->balance;//临时变量保存
        tp = parent->parent;//临时变量保存
        if (tp != NULL)
          if (parent == tp->left)
            tc = 1;
          else tc = -1;
        else tc = 0;
        
        root = adjustAVL(root, parent, child);
        
        if (temp == 0)
          break;
        else
        {
          if (tc == 1)
            child = tp->left;
          else if (tc == -1)
            child = tp->right;
          parent = tp;
        }
      }
      else
      {
        parent->balance = 1;
        break;
      }
    }
   
    if (dNode->parent != NULL)
      if (dNode == dNode->parent->left)
        dNode->parent->left = NULL;
      else dNode->parent->right = NULL;
    free(dNode);
    if (root == dNode)
      root = NULL; //root被删除, 避免野指针
    dNode = NULL;
   
    return root;
  }
}

node* createAVL(int *data, int size)
{
  int i, j;
  node *root;
  if (size<1)
    return NULL;
  root = (node*)malloc(sizeof(node));
  root->parent = NULL;
  root->left = NULL;
  root->right = NULL;
  root->key = data[0];
  root->balance = 0;
  
  for(i=1;i<size;i++)
    root = insertNode(data[i], root);
  return root;
}

void destroyAVL(node* root)
{
  if (root != NULL)
  {
    destroyAVL(root->left);
    destroyAVL(root->right);
    free(root);
    root=NULL;
  }
  
}

void traverseAVL1(node* root) //中序遍历

{
  if (root != NULL)
  {
    traverseAVL1(root->left);
    printf("%d, %d\n", root->key, root->balance);
    traverseAVL1(root->right);
  }
}

void traverseAVL2(node* root) //先序遍历

{
  if (root != NULL)
  {
    printf("%d, %d\n", root->key, root->balance);
    traverseAVL2(root->left);
    traverseAVL2(root->right);
  }
}

int main(int argc, char *argv[])
{
  int data[] = {1, 5, 7, 4, 3, 2, 11, 9, 10};
  node* root;
  root = createAVL(data, sizeof(data)/sizeof(data[0]));

  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);
  
  root = deleteNode(5, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(3, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(1, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(7, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(4, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  root = deleteNode(2, root);
  printf("++++++++++++++++++++++++++++\n");
  traverseAVL1(root);
  printf("\n");
  traverseAVL2(root);

  destroyAVL(root);
}