《操作系统》课程教学资源（PPT课件）第十章 内部排序

二叉排序树上的删除,相当于删去 有序序列上的一个记录,应保证删 除结点后,二叉排序树的特性不变 删除结点可有三种情况: 1若被删除结点*为叶子结点,即其p和 p均为空树。由于叶子结点的存在若不 破坏整株树的结构,则只需修改其父结 点的指针即可。 2若*p结点只有左子树p或只有右子树p 此时只要令P或pR直接成为其父结点*f

二叉排序树上的删除，相当于删去 有序序列上的一个记录，应保证删 除结点后，二叉排序树的特性不变。 删除结点可有三种情况： 1.若被删除结点*p为叶子结点，即其pL和 pR均为空树。由于叶子结点的存在若不 破坏整株树的结构，则只需修改其父结 点的指针即可。 2.若*p结点只有左子树pL或只有右子树pR， 此时只要令pL或pR直接成为其父结点*f

的左子树即可。可见,也不破坏二叉排序 1树的特性 3若*结点的左、右子树均不空,不能简 单处理,可有两种情况。例 P PR

的左子树即可。可见，也不破坏二叉排序 树的特性。 3.若*p结点的左、右子树均不空，不能简 单处理，可有两种情况。例： F P f p pL pR (a)

F p P C Q Q C S (b)

f F P C p cCL Q P RqS Q L S L S F C cCL S S f S L P R (b) (c)

F C C q Q Q (d)

f F S C p c CL Q PR q QL SL (d)

叉排序树中删除一个 结点的算法 DeleteBST(T key) t if(!t return False else i if(EQ(key, T->data. key)) return Delete(D) if(LT( key T->data. key)) return DeleteBST(T->lchild, key) else return DeleteBST(T->rchild, keyi S//DeleteBST

二叉排序树中删除一个 结点的算法 DeleteBST(T , key) { if(!T) return False; else { if(EQ(key, T->data.key)) return Delete(T); if(LT(key,T->data.key)) return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key);} }//DeleteBST

上述三种情况的删除算法 Delete(p)/*p被删除点* tif(!p-> rchild)/*右子树空接其左子树* a=p; p=p->lchild; free il else if(!p->lhid)/*只接其右子树* tq=p; p=p->rchild free ai else &q=p: s=p->lchild;

上述三种情况的删除算法 Delete(p)/*p被删除点*/ { if(!p->rchild) /*右子树空接其左子树*/ {q=p;p=p->lchild;free(q);} else if(!p->lchild)/*只接其右子树*/ { q=p;p=p->rchild;free(q);} else { q=p; s=p->lchild;

while(s->rchild) q=s, s=p->lchild;y /*转左,然后向右到尽头* p->data=s->data;/*s指向删除结点的前驱* f(q!=p)q>rchd=s-> child;/*接*p的右子树*/ else q>chid=s->hid;/*接*p的左子树*/ delete s } return TrUe 3//Delete

while(s->rchild) { q=s; s=p->lchild;} /*转左，然后向右到尽头*/ p->data= s->data;/*s指向删除结点的前驱*/ if(q!=p) q->rchild= s->lchild;/*接*p的右子树*/ else q->lchild=s->lchild;/*接*p的左子树*/ delete s; } return TRUE; } //Delete

叉排序树的查找分类 从平均查找长度分析: 设有6个记录,其关键字序列为 (452453123793)或由另一种序列构成 (1224,37455393)其对应的二叉排序树: 45 24 37 53 45 12)③37(93) 53 (b) (93)

三.二叉排序树的查找分类 从平均查找长度分析： 设有6个记录，其关键字序列为 (45,24,53,12,37,93)或由另一种序列构成 (12,24,37,45,53,93)其对应的二叉排序树： 45 24 53 12 37 93 12 53 45 37 24 93 (a) (b)

(a)树的深度为3(b)树的深度为6 若每个记录的查找概率相等,为6 则树的平均查找长度为: 14 AsLa)=(1+2+2+3+3+3)= Aso=(1+2+3+4+5+6)=21 查找关键字与给定值的结点的过程,是从 根结点到该结点路径的过程,和给定值比 较的关键字个数等于路径长度加1(或结点

(a)树的深度为3 (b)树的深度为6 若每个记录的查找概率相等，为 ， 则树的平均查找长度为： AsL(a)= (1+2+2+3+3+3)= AsL(b)= (1+2+3+4+5+6)= 查找关键字与给定值的结点的过程，是从 根结点到该结点路径的过程，和给定值比 较的关键字个数等于路径长度加1（或结点 6 1 6 1 6 14 6 1 6 21

所在层次数) 4可见,含有n个结点的二叉排序树 的平均查找时间和树的形态有关 若构造二叉排序树时,按关键字有序构造, 树的深度为n。其平均查找长度为2,这 是最差的情况。 若二叉排序树的形态和折半查找的判定 树相同。其平均查找长度Log2n成正比

所在层次数）。 可见，含有n个结点的二叉排序树 的平均查找时间和树的形态有关。 若构造二叉排序树时，按关键字有序构造， 树的深度为n。其平均查找长度为 ，这 是最差的情况。 若二叉排序树的形态和折半查找的判定 树相同。其平均查找长度Log2n成正比。 2 n +1