9.3.1　二叉排序树

二叉排序树（binary sort tree）或者是一棵空树，或者是具有下列性质的二叉树：

图9－3 二叉排序树示例

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）它的左、右子树也分别为二叉排序树。

例如，图9－3所示为二叉排序树。

二叉排序树的查找过程为：当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。

通常，可取二叉链表作为二叉排序树的存储结构，则上述查找过程如算法9.3（a）所描述。

算法9.3（a） 二叉排序树查找

例如，在图9－3所示的二叉排序树中查找关键字等于100的记录（树中结点内的数均为记录的关键字）。首先以key＝100和根结点的关键字作比较，因为key＞45，则查找以45为根的右子树，此时右子树不空，key＞53则继续查找以结点53为根的右子树，由于key和53的右子树根的关键字100相等，则查找成功，返回指向结点100的指针值。

1.二叉排序树的插入和删除

二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。为此，需将上一个节的二叉排序树的查找算法改写成算法9.3（b），以便能在查找不成功时返回插入位置。插入算法如算法9.4所示。

算法9.3（b） 二叉排序树查找

算法9.4 二叉排序树插入

若从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为｛45，24，53，45，12，24，90｝，则生成的二叉排序树如图9－4所示。

图9－4 二叉排序树的构造过程

容易看出，中序遍历二叉排序树可得到一个关键字的有序序列（这个性质是由二叉排序树的定义决定的，读者可以自己证明之）。这就是说，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。不仅如此，从上面的插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可，这就相当于在一个有序序列上插入一个记录而不用移动其他记录。它表明，二叉排序树既拥有类似于二分查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。

同样，在二叉排序树上删去一个结点也很方便。对于一般的二叉树来说，删去树中一个结点是没有意义的。因为它将使以被删结点为根的子树成为森林，破坏了整棵树的结构。然而，对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。

那么，如何在二叉排序树上删去一个结点呢？假设在二叉排序树上被删结点为＊p（指向结点的指针为p），其双亲结点为＊f（结点指针为f），且不失一般性，可设＊p是＊f的左孩子（图9－5（a）所示）。

下面分三种情况进行讨论。

（1）若＊p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

（2）若＊p结点只有左子树PL或者只有右子树PR，此时只要令PL或PR直接成为其双亲结点＊f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。

（3）若＊p结点的左子树和右子树均不空。显然，此时不能加上简单处理。从图9－5（b）可知，在删去＊p结点之前，中序遍历该二叉树得到的序列为｛…CLC…QLQSLSPPRF…｝，在删去＊p之后，为保持其他元素之间的相对位置不变，可以有两种做法：其一是令＊p的左子树为＊f的左子树，而＊p的右子树为＊s的右子树，如图9－5（c）所示；其二是令＊p的直接前驱（或直接后继）替代＊p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。如图9－5（d）所示，当以直接前驱＊s替代＊p时，由于＊s只有左子树SL，则在删去＊s之后，只要令SL为＊s的双亲＊q的右子树即可。

图9－5 在二叉排序树中删除＊q

图9－5 在二叉排序树中删除＊q（续）

在二叉排序树上删除一个结点的算法如算法9.5所示，其中由前述三种情况综合所得的删除操作如算法9.6所示。

算法9.5 二叉排序树上删除一个结点

其中删除操作过程如算法9.6所描述。

算法9.6 二叉排序树中的删除过程

2.二叉排序树的查找分析

从前述的两个查找例子（key＝100和key＝40）可见，在二叉排序树上查找其关键字等于给定值的结点的过程恰是走了一条从根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1（或结点所在层次数），因此，和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一。图9－6中（a）和（b）的两棵二叉排序树中结点的值都相同，但前者由关键字序列（45，24，53，12，37，93）构成，而后者由关键字序列（12，24，37，45，53，93）构成。图9－6（a）树的深度为3，而图9－6（b）树的深度为6。再从平均查找长度来看，假设6个记录的查找概率相等，为1／6，则图9－6（a）树的平均查找长度为

而图9－6（b）树的平均查找长度为

图9－6 不同形态的二叉查找树

因此，含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树。树的深度为n，其平均查找长度为（和顺序查找相同），这是最差情况。显然最好情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。因此，在排序树的过程中进行“平衡化”处理是非常重要的，这个过程我们称为平衡二叉树。（注：上述对二叉排序树的查找性能的讨论是在等概率的前提下进行的。）