#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>

typedef struct node node;

struct node
{
  node* parent;
  node* left;
  node* right;
  int balance; //左右子树高度之差

  int key;
};

extern void traverseAVL1(node* root); //中序遍历, 下面定义


extern void traverseAVL2(node* root); //前序遍历, 下面定义


int searchNode(int key, node* root, node** parent) //按key查找结点

{
  node* temp;
  assert(root != NULL);
  temp = root;
  *parent = root->parent;
  while (temp !=NULL)
  {
    if (temp->key == key)
      return 1;
    else
    {
       *parent = temp;
      if (temp->key > key)
        temp = temp->left;
      else
        temp = temp->right;
    }
  }
  return 0;

}

node* minNode(node* root) //树root的最小结点

{
  if (root == NULL)
    return NULL;
  while (root->left != NULL)
    root = root->left;
  return root;
}

node* maxNode(node* root) //树root的最大结点

{
  if (root == NULL)
    return NULL;
  while (root->right != NULL)
    root = root->right;
  return root;
}

node* preNode(node* target) //求前驱结点

{
  if (target == NULL)
    return NULL;
  if (target->left != NULL)
    return maxNode(target->left);
  else
    while ((target->parent!=NULL) && (target!=target->parent->right))
      target = target->parent;
  return target->parent;
}

node* nextNode(node* target) //求后继结点

{
  if (target == NULL)
    return NULL;
  if (target->right != NULL)
    return minNode(target->right);
  else
    while ((target->parent!=NULL) && (target!=target->parent->left))
      target = target->parent;
  return target->parent;
}

node* adjustAVL(node* root, node* parent, node* child)
{
  node *cur;
  assert((parent != NULL)&&(child != NULL));
  switch (parent->balance)
  {
  case 2:
    if (child->balance == -1)//LR型

    {
      cur = child->right;
      cur->parent = parent->parent;
      child->right = cur->left;
      if (cur->left != NULL)
        cur->left->parent = child;
      parent->left = cur->right;
      if (cur->right != NULL)
        cur->right->parent = parent;
      cur->left = child;
      child->parent = cur;
      cur->right = parent;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = cur;
        else parent->parent->right = cur;
      else
        root = cur;
      parent->parent = cur;
      if (cur->balance == 0)
      {
        parent->balance = 0;
        child->balance = 0;
      }
      else if (cur->balance == -1)
      {
        parent->balance = 0;
        child->balance = 1;
      }
      else
      {
        parent->balance = -1;
        child->balance = 0;
      }
      cur->balance = 0;
    }
    else //LL型

    {
      child->parent = parent->parent;
      parent->left = child->right;
      if (child->right != NULL)
        child->right->parent = parent;
      child->right = parent;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = child;
        else parent->parent->right = child;
      else
        root = child;
      parent->parent = child;
      if (child->balance == 1) //插入时

      {
        child->balance = 0;
        parent->balance = 0;
      }
      else //删除时

      {
        child->balance = -1;
        parent->balance = 1;
      }
    }
   break;
   
  case -2:
    if (child->balance == 1) //RL型

    {
      cur = child->left;
      cur->parent = parent->parent;
      child->left = cur->right;
      if (cur->right != NULL)
        cur->right->parent = child;
      parent->right = cur->left;
      if (cur->left != NULL)
        cur->left->parent = parent;
      cur->left = parent;
      cur->right = child;
      child->parent = cur;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = cur;
        else parent->parent->right = cur;
      else
        root = cur;
      parent->parent = cur;
      if (cur->balance == 0)
      {
        parent->balance = 0;
        child->balance = 0;
      }
      else if (cur->balance == 1)
      {
        parent->balance = 0;
        child->balance = -1;
      }
      else
      {
        parent->balance = 1;
        child->balance = 0;
      }
      cur->balance = 0;
    }
    else //RR型

    {
      child->parent = parent->parent;
      parent->right = child->left;
      if (child->left != NULL)
        child->left->parent = parent;
      child->left = parent;
      if (parent->parent != NULL)
        if (parent->parent->left == parent)
          parent->parent->left = child;
        else parent->parent->right = child;
      else
        root = child;
      parent->parent = child;
      if (child->balance == -1) //插入时

      {
        child->balance = 0;
        parent->balance = 0;
      }
      else //删除时

      {
        child->balance = 1;
        parent->balance = -1;
      }
    }
    break;
  }
  return root;
}