发布时间 : 星期一 文章动态查找树之平衡二叉树（Balanced Binary Tree,AVL树）更新完毕开始阅读ef873a4f2b160b4e767fcfde
if(SearchBST(T,e.key)!=NULL) printf(\else printf(\return 1;
}//SearchBSTD
int Delete(BSTree &T,KeyType key,int &shorter) {
int success=0;//标志成功删除与否 if(T) {
if(EQ(key,T->data.key))
{//相等，即当前结点就是要删除的结点
if(T->lchild!=NULL&&T->rchild!=NULL) {//要删除结点的左右子树都不空 BSTree q,r;
//接下来，找到要删除数据的前驱结点，并且将数据与直接前驱 //交换。这样我们将其前驱删除掉后，再调整平衡树就好了。 q=T->lchild;
r=q;//用r来指向其前驱接点。 while(q) { r=q;
q=q->rchild; }//while(q)
KeyType temp=T->data.key; T->data.key=r->data.key; r->data.key=temp;
//接下来，在左子树上删除其前驱接点 success=Delete(T->lchild,key,shorter); if(shorter)
{//由于删除操作导致了树变小了 switch(T->bf) {
case LH:T->bf=EH;break; case EH:T->bf=RH;break;
case RH:RightBalanceD(T,shorter);break; }//switch }//if
}//if-要删除结点左右子树都不空 else
{//要删除接点有一个子树不为空 BSTree p=T;
T=(T->lchild!=NULL)?T->lchild:T->rchild; delete p;
success=1;//删除成功 shorter=1;//树变短了。 }//else }//if=
else if(LT(key,T->data.key))
{//在左子树上查询要删除的结点
success=Delete(T->lchild,key,shorter); if(shorter) {
switch(T->bf) {
case LH: T->bf=EH; shorter=0;break; case EH: T->bf=RH; break;
case RH: RightBalanceD(T,shorter); break; }//switch }//if-shorter }//if<
else if(BT(key,T->data.key)) {//在右子树上查询要删除的结点
success=Delete(T->rchild,key,shorter); if(shorter) {
switch(T->bf) {
case LH: LeftBalanceD(T,shorter); break; case EH: T->bf=LH; break;
case RH: T->bf=EH; shorter=0;break; }//switch }//if-shorter }//else if> }//if(T)
return success; }//Delete
int DeleteD(BSTree &T) {
ElemType e; int shorter;
printf(\scanf(\
Delete(T,e.key,shorter); return 1; }//Delete int main() {
BSTree T;
InitDSTable(T); InsertAVLD(T);
TraverseDSTable(T,Visit); SearchBSTD(T); DeleteD(T);
TraverseDSTable(T,Visit); DestroyDSTable(T); return 1; }
五、复杂度分析
在平衡二叉树上进行查找的过程与二叉排序树的查找算法相同。因此，在查找过程中和关键字进行比较的次数不超过树的深度。含有n个结点的平衡树的最大深度为：