8.3.2 二叉排序树（2）在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们继续讨论二叉排序树

上一节课，我们介绍了作为动态查找表的二叉排序树

讨论了二叉排序的查找以及插入

这节课我们讨论二叉排序树的删除

在二叉排序树中删除树中的一个结点

有两个问题要注意

一是要保证删除该结点以后仍然是一棵二叉排序树

二是删除以后不要降低二叉排序树的查找效率

这里结合图示直接看一下

首先做一个假设

假设已经查找到了要删除的结点

指针p指向被删除的节点

同时指针f指向p的双亲节点

不失一般性，我们讨论p是f的左孩子的情况

p是f的右孩子的情况是一个对称的问题

类似处理就可以了

根据被删除结点的不同特点，分三种情况来讨论

第一种情况，如果要删除的结点*p是二叉排序树中的叶子结点

比如说，图1中的情况

要删除的节点是p所指的20

它的双亲是24

这种情形只需要把结点20直接从二叉排序树中删除就可以了

这样的删除对树中其它结点没有什么影响

直接删除后整棵树任然满足二叉排序树的定义

第二种情况呢

如果要删除的结点*p，只有左子树

或者只有右子树

例如图2中的情况，要删除的节点是61

它的双亲是100，61只有以90为根的右子树

那么只需要双亲100的左指针指向61的孩子90就可以了

根据二叉排序树的性质，90为根的子树是二叉排序树

它原本就在100的左子树中

所有删除后任然满足二叉排序树的定义

第三种情况，稍微复杂一些

如果要删除的结点*p

有左子树，也有右子树

比如图3所示

要删除45

45是整棵树的根

上一节中，我们提到过

如果对二叉排序树进行中序遍历

那么它的访问序列是一个有序序列

要删除有左子树，也有右子树的结点

方法是用它在中序序列中的直接前驱

或者直接后继，来替代该结点，这里以直接前驱为例

45的直接前驱是它左子树中的37

37是左子树中的最大关键字，它一定没有右孩子

以直接前驱37的替代45，随后删除存放37的这个结点

同第二种情况

37是左子树中的最大关键字

这样替代删除后，任然满足二叉排序树的定义

用直接后继替代的方法是对称的，不再重复了

这里结合一个具体的实例

讨论了二叉排序树的删除

下面我们总结一下一般情况

任然假设指针p指向被删除的节点

同时指针f指向p的双亲节点

讨论p是f的左孩子的情况

第一种，如果p是叶子，那么直接删除

f->lchild=NULL即可

当然一般程序中需要释放被删除的结点

第二种* p结点只有左子树PL或者只有右子树PR

那么， f->lchild=p->lchild; 或 f->lchild=p->rchild;

双亲的左孩子指针指向左子树PL或者右子树PR的根即可

第三种* p结点有左子树PL

也有右子树PR，左右子树均不空

如图1所示，图1中

给出了包含要删除结点的二叉排序树的的局部

其中p指向被删除的节点大P

f指向它的双亲节点大F，Pr是大P的右子树

P的左子树是以大C为根的这棵子树

中序遍历该二叉排序树可以得到一个有序序列

那么删除树中一个结点后

应该保持序列中其它元素之间的相对位置不变

保持仍然是一棵二叉排序树

教材中介绍了两种做法

第1种做法是让p的左子树成为f的左子树

P的右子树Pr，成为P左子树中最大关键字S的右子树

结果如图2所示，做中序遍历，相对位置不变

这样的做法会带来一个问题

就是它可能导致整个二叉排序树变深

因为C为根的子树整体上升了一层

子树中结点的查找效率有所改善

但是P的右子树Pr 下移的层次可能很多

Pr中结点的查找效率可能大幅度降低

导致整个二叉排序树的效率下降

第2种方法，就是我们刚才结合例子介绍的方法

用P的直接前驱或者直接后继替代P

然后再从二叉排序树中

删去它的直接前驱或者直接后继

算法9.8采用的就是第2种

仍然以直接前驱为例

该方法中首先要找到P的直接前驱

P的直接前驱是其左子树C中最大关键字

因为二叉排序树中，右子树的关键字大于根结点的关键字

找C中最大关键字的办法是从左子树的根C开始

不断向右找右孩子，直到找到一个没有右孩子的结点为止

这个结点的关键字就是左子树C中的最大关键字

观察图1，图中是结点S，用S替代P

随后删除原来保存S的结点

它的左子树变成其双亲Q的右子树，结果如图2所示

第2种方法肯定不会增加任何结点的层次

整棵树中的查找效率不会降低

下面我们考虑一下二叉排序树的查找性能

前面我们介绍过二叉排序树的几个示例

并计算了它们查找成功和查找不成功的平均查找长度

我们注意到二叉排序树的查找性能，受其形态的影响

讨论了插入和删除后，我们又注意到

二叉排序树的形态受插入和删除次序的影响

看一个例子，例子中给出了两个整数的插入序列

两个序列中包含的关键字完全一样

但是插入的次序不同

所获得的二叉排序树如图1和图2所示

二者形态差异是比较大的

计算二者查找成功的平均查找长度

分别7/3和7/2，差异是比较明显的

图2的情况实际上已经退化成了一个顺序查找

一般而言，动态查找表中

要插入的关键字有多少个可能都是未知的

更不用说插入的次序了

那么对二叉排序树的形态，更进一步说

二叉排序树的查找效率

是否我们就束手无策了呢

还是有办法的，下节课会介绍平衡的二叉排序树

目的就是为了解决这个问题

好同学们，这节课我们就要到这儿

下次课再见