BSTNode* leftbalance（BSTNode* root, BSTNode* parent, BSTNode* child）
{
BSTNode *cur;
assert（（parent != NULL）&&（child != NULL））；
/* LR */
if （child->bf == RH）
{
cur = child->rchild;
cur->parent = parent->parent;
child->rchild = cur->lchild;
if （cur->lchild != NULL）
{
cur->lchild->parent = child;
}
parent->lchild = cur->rchild;
if （cur->rchild != NULL）
{
cur->rchild->parent = parent;
}
cur->lchild = child;
cur->rchild = parent;
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 == RH）
{
parent->bf = EH;
child->bf = LH;
}
else
{
parent->bf = RH;
child->bf = EH;
}
cur->bf = EH;
}
/* LL */
else
{
child->parent = parent->parent;
parent->lchild = child->rchild;
if （child->rchild != NULL）
{
child->rchild->parent = parent;
}
child->rchild = 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 == LH）
{
child->bf = EH;
parent->bf = EH;
}
/* when delete*/
else
{
child->bf = RH;
parent->bf = LH;
}
}
return root;
}
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;
}
BSTNode* deleteNode（ElemType key, BSTNode* root）
{
BSTNode *dNode=NULL, *parent=NULL, *child = NULL;
ElemType temp;
assert（root!=NULL）；
if （！searchAVL（root,key,&parent））
{
return root;
}
if （parent == NULL）
{
dNode = root;
}
else if （（parent->lchild!=NULL）&&（parent->lchild->key==key））
{
dNode = parent->lchild;
}
else
{
dNode = parent->rchild;
}
child = dNode;
while （（child->lchild!=NULL）||（child->rchild!=NULL）） //确定需要删除的结点
{
if （child->bf == LH）
{
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->lchild）
{
if （parent->bf == LH）
{
parent->bf = EH;
child = parent;
parent = parent->parent;
}
else if （parent->bf == RH）
{
child = parent->rchild;
root = rightbalance（root, parent, child）；
break;
}
else
{
parent->bf = RH;
break;
}
}
else
{
if （parent->bf == RH）
{
parent->bf = EH;
child = parent;
parent = parent->parent;
}
else if （parent->bf == LH）
{
child = parent->lchild;