动态查找树之平衡二叉树（Balanced Binary Tree,AVL树）

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个结点的平衡树的最大深度为：