nt->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 (keykey)
{
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;
root = leftbalance(root, parent, child);
break;
}
else
{
parent->bf = LH;
break;
}
}
}
if (dNode->parent != NULL)
{
if (dNode == dNode->parent->lchild)
{
dNode->parent->lchild = NULL;
}
else
{
dNode->parent->rchild = NULL;
}
}
free(dNode);
dN