AVL树C语言完整实现(2)

BSTNode* rightbalance(BSTNode* root, BSTNode* parent, BSTNode* child)
{
 BSTNode *cur;
 assert((parent != NULL)&&(child != NULL));
 /* RL */
 if (child->bf == LH)
 {
  cur = child->lchild;
  cur->parent = parent->parent;
  child->lchild = cur->rchild;
  if (cur->rchild != NULL)
  {
   cur->rchild->parent = child;
  }
  parent->rchild = cur->lchild;
  if (cur->lchild != NULL)
  {
   cur->lchild->parent = parent;
  }
  cur->lchild = parent;
  cur->rchild = child;
  child->parent = cur;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = cur;
   }
   else
   {
    parent->parent->rchild = cur;
   }
  }
  else
  {
   root = cur;
  }
  parent->parent = cur;
  if (cur->bf == EH)
  {
   parent->bf = EH;
   child->bf = EH;
  }
  else if (cur->bf == LH)
  {
   parent->bf = EH;
   child->bf = RH;
  }
  else
  {
   parent->bf = LH;
   child->bf = EH;
  }
  cur->bf = EH;
 }
 /* RR */
 else
 {
  child->parent = parent->parent;
  parent->rchild = child->lchild;
  if (child->lchild != NULL)
   child->lchild->parent = parent;
  child->lchild = parent;
  if (parent->parent != NULL)
  {
   if (parent->parent->lchild == parent)
   {
    parent->parent->lchild = child;
   }
   else
   {
    parent->parent->rchild = child;
   }
  }
  else
  {
   root = child;
  }
  parent->parent = child;
  /* when insert */
  if (child->bf == RH)
  {
   child->bf = EH;
   parent->bf = EH;
  }
  /* when delete*/
  else
  {
   child->bf = LH;
   parent->bf = RH;
  }
 }
 return root;
}

BSTNode* insertNode(ElemType key, BSTNode* root)
{
 BSTNode *parent = NULL, *cur = NULL, *child = NULL;
 assert (root != NULL);
 /* node exists*/
 if (searchAVL(root,key,&parent))
 {
  return root;
 }
 cur = (BSTNode*)malloc(sizeof(BSTNode));
 cur->parent = parent;
 cur->key = key;
 cur->lchild = NULL;
 cur->rchild = NULL;
 cur->bf = EH;
 if (key<parent->key)
 {
  parent->lchild = cur;
  child = parent->lchild;
 }
 else
 {
  parent->rchild = cur;
  child = parent->rchild;
 }
 /*get the minimax tree needed to be adjusted*/
 while ((parent != NULL))
 {
  if (child == parent->lchild)
  {
   if (parent->bf == RH)
   {
    parent->bf = EH;
    return root;
   }
   else if (parent->bf == EH)
   {
    root = leftbalance(root, parent, child);
    break;
   }
   else
   {
    parent->bf = LH;
    child = parent;
    parent = parent->parent;
   }
  }
  else
  {
   if (parent->bf == LH) //是右孩子，不会引起不平衡
   {
    parent->bf = EH;
    return root;
   }
   else if (parent->bf == RH) //是右孩子，并且引起parent的不平衡

{
    root = rightbalance(root, parent, child);
    break;
   }
   else //是右孩子，并且可能引起parent的parent的不平衡
   {
    parent->bf = RH;
    child = parent;
    parent = parent->parent;
   }
  }
 }

return root;
}