Status InsertAVL (BSTree &T,ElemType s)
{ if (T==NULL) T=s;
else {
f=NULL; //记录a的双亲
a=T; //记录在查找中平衡因子不为零的结点
p=T; //进行比较的结点
q=NULL; //记录p的双亲
While (p!=NULL) //查找结点
{ if (p->bf!=0) { a=p; f=q;}
q=p;
if (s->data<p->data) p=p->Lchild;
else p=p->Rchild;
}
}
if (s->data<q->data) q->Lchild=s;
else q->Rchild=s; //将s插入
//修改a至s路径上结点的平衡因子
if (s->data<a->data)
{ p=a->Lchild; b=p; d=1;}
else { p=a->Rchild; b=p; d=-1;} //这段中,d应该也是平衡因子,但不明白为什么要用两个平衡因子bf和d;还有b是什么东东??? 老师的变量名称让人费解。。。有高手来解释下吗?关于高度平衡二叉树的插入算法。。。
while (p!=s)
if (s->data<p->data)
{ p->bf=1; p=p->Lchild; }
else {p->bf=-1; p=p->Rchild;}
if (a->bf==0) a->bf=d;
else if (a->bf+d==0) a->bf=0;
else {if (d==1)
if (b->bf==1) LL 旋转
else LR旋转
else if (b->bf==-1) RR旋转
else RL旋转
//修改a的双亲
case
f=NULL: T=b;
f->Lchild=a: f->Lchild=b;
f->Rchild=a: f->Rchild=b;
end of case
}
}
高度平衡二叉树的插入算法
有高手来解释一下这段算法吗?从老师的课件中拿过来的,