内蒙古大学《算法与数据结构》讲义11搜索树

下载第11章搜索树本章是关于树结构的最后一章，我们将给出一种适合于描述字典的树形结构。第 7章中的字典描述仅能提供比较好的平均性能，而在最坏情况下的性能很差。当用跳表来描述一个 n 元素的字典时，对其进行搜索、插入或者删除操作所需要的平均时间为 O ( l o gn)，而最坏情况下的时间为(n)。当用散列来描述一个n 元素的字典时，对其进行搜索、插入或者删除操作所需要的平均和最坏时间分别为( l )和(n)。使用跳表很容易对字典元素进行高效的顺序访问（如按照升序搜索元素） ，而散列却做不到这一点。当用平衡搜索树来描述一个n 元素的字典时，对其进行搜索、插入或者删除所需要的平均时间和最坏时间均为( l o gn)，按元素排名进行的查找和删除操作所需要的时间为 O ( l o gn)，并且所有字典元素能够在线性时间内按升序输出。正因为这样（无论是平衡还是非平衡搜索树） ，所以在搜索树中进行顺序访问时，搜索每个元素所需要的平均时间为( l )。实际上，如果所期望的操作为查找、插入和删除（均根据元素的关键值来进行） ，则可以借助于散列函数来实现平衡搜索树。当字典操作仅按关键值来进行时，可将平衡搜索用于那些对时间要求比较严格的应用，以确保任何字典操作所需要的时间都不会超过指定的时间量。平衡搜索树也可用于按排名来进行查找和删除操作的情形。对于那些不按精确的关键值匹配进行字典操作的应用（比如寻找关键值大于k 的最小元素） ，同样可使用平衡搜索树。本章将首先介绍二叉搜索树。这种树提供了可与跳表相媲美的渐进复杂性。其搜索、插入和删除操作的平均时间复杂性为 O ( l o gn)，最坏时间复杂性为(n)。接下来将介绍两种大家比较熟悉的平衡树：AV L树和红-黑树。无论哪一种树，其搜索、插入和删除操作都能在对数时间内完成（平均和最坏情况） 。两种结构的实际运行性能也很接近， AV L树一般稍微快一些。所有的平衡树结构都使用“旋转”来保持平衡。 AV L树在执行每个插入操作时最多需要一次旋转，执行每个删除操作时最多需要O ( l o gn)次旋转；而红-黑树对于每个插入和删除操作，都需要执行一次旋转。这种差别对于大多数仅需( l )时间进行一次旋转的应用来说无关紧要，但对于那些不能在常量时间内完成一次旋转的应用来说就非常重要了，比如平衡优先搜索树McCreight 就是这样一种应用。平衡优先搜索树用于描述具有两个关键值的元素，此时，每个关键值是一对数(x,y)。它同时是一个关于y 的优先队列和关于x 的搜索树。在平衡优先搜索树中执行旋转时，每次旋转都需耗时O ( l o gn)。如果用红-黑树来描述平衡优先搜索树，由于每一次插入或删除后仅需执行一次旋转，因此插入或删除操作总的时间复杂性仍保持为 O ( l o gn)；当使用AV L树时，删除操作的时间将变为O ( l o gn)。如果所描述的字典比较小（能够完全放入内存） ，AV L树和红-黑树均能提供比较高的性能，但对于很大的字典来说，它们就不适用了。当字典存储在磁盘上时，需要使用带有更高次数（因而有更小高度）的搜索树，本章也将介绍一个这样的搜索树 B-树。本章的应用部分将给出三个搜索树的应用。第一个是直方图的计算，第二个是 1 0 . 5 . 1节所介绍的N P-复杂问题箱子装载，最后一个是关于在电子布线中所出现的交叉分布问题。在直方图的应用中，使用散列函数来取代搜索树，从而使性能得到提高。在最优匹配箱子装载应用中，由于搜索不是按精确匹配完成的，所以不能使用散列函数。在交叉分布问题中，操作是按排名完成的，因此也不能使用散列函数。11.1 二叉搜索树11.1.1 基本概念7 . 1和7 . 4节介绍了抽象数据类型D i c t i o n a ry，从中可以发现当用散列来描述一个字典时，字典操作（包括插入、搜索和删除）所需要的平均时间为( l )。而这些操作在最坏情况下的时间正比于字典中的元素个数 n。如果扩充D i c t i o n a ry 的A D T描述，增加以下操作，那么散列将不能再提供比较好的平均性能：1) 按关键值的升序输出字典元素。2) 按升序找到第k 个元素。3) 删除第k 个元素。为了执行操作1 )，需要从表中取出数据，将它们排序后输出。如果使用除数为 D 的链表，那么能在(D+n) 的时间内取出元素，在O (nl o gn) 时间内完成排序和在(n) 时间内输出，因此共需时间O (D+nl o gn)。如果对散列使用线性开型寻址，则取出元素所需时间为(b)，b 是桶的个数，这时所需时间为O (b+nl o gn)。如果使用链表，操作2) 和3) 可以在O (D+n) 的时间内完成，而如果使用线性开型寻址，它们可在(b) 时间内完成。为了获得操作2) 和3) 的这种复杂性，必须采用一个线性时间算法来确定n 元素集合中的第k 个元素（参考1 4 . 5节） 。如果使用平衡搜索树，那么对字典的基本操作（搜索、插入和删除）能够在 O ( l o gn)的时间内完成，操作1) 能在(n)的时间内完成。通过使用带索引的平衡搜索树，也能够在 O ( l o gn)的时间内完成操作2) 和3 )。11 . 3节将考察其他一些散列无法做到而平衡树可以有效解决的应用。在学习平衡树之前，首先来看一种叫作二叉搜索树的简单结构。定义二叉搜索树 二叉搜索树（binary search tree）是一棵可能为空的二叉树，一棵非空的二叉搜索树满足以下特征：1) 每个元素有一个关键值，并且没有任意两个元素有相同的关键值；因此，所有的关键值都是唯一的。2) 根节点左子树的关键值（如果有的话）小于根节点的关键值。3) 根节点右子树的关键值（如果有的话）大于根节点的关键值。4) 根节点的左右子树也都是二叉搜索树。此定义中有一些冗余。特征2 )、3) 和4) 在一起暗示了关键值必须是唯一的。因此，特征 1 )可以用这样的特征代替：根节点必须有关键值。然而，前一种定义比这种简化的定义要清楚明了。图11 - 1给出了一些各元素含有不同关键值的二叉树。节点中的数字是元素的关键值。其中11-1a 中的树尽管满足特征1 )、2) 和3 )，但仍然不是二叉搜索树，因为它不满足特征 4 )，其中有一个子树的右子树的关键值（2 2）小于该子树根节点的关键值（2 5） 。而图11-1b 和c 都是二叉搜索树。我们可以放弃二叉搜索树中所有元素拥有不同关键值的要求，然后再用小于等于代替特征2) 中的小于，用大于等于代替特征 3) 中的大于，这样，就得到了一棵有重复值的二叉搜索树（binary search tree with duplicates） 。带索引的二叉搜索树（indexed binary search tree）源于普通的二叉搜索树，它只是在每个节点中添加一个L e f t S i z e域。这个域的值是该节点左子树的元素个数加 1。图11 - 2是两棵带索引3 2 0第二部分数 据 结 构下载的二叉搜索树。节点里面的数字是元素的关键值，外面的是 LeftSize 的值。注意，L e f t S i z e同时给出了一个元素在子树中排名。例如，在图11-2a 的树中，根为2 0的子树中的元素（已排序）分别为1 2，1 5，1 8，2 0，2 5和3 0，根节点的排名为4（即它在排序后的队列中是第 4个元素） ，在根为2 5的子树中的元素（已排序）为2 5和3 0，因此2 5的排名为1且LeftSize 的值也为1。图11-1 二叉树图11-2 带索引的二叉搜索树11.1.2 抽象数据类型B S Tree 和I n d e x e d B S Tr e eADT 11 - 1给出了二叉搜索树的抽象数据类型描述。带索引的二叉搜索树支持所有的二叉搜索树操作。另外，它还支持按排名进行的查找和删除操作。 ADT 11 - 2给出了它的抽象数据类型描述。可以按照类似的方法来描述抽象数据类型D B S Tre e(有重复值的二叉搜索树 )和D I n d e x e d B S Tre e。ADT 11-1 二叉搜索树的抽象数据类型描述抽象数据类型B S Tree 实例二叉树，每一个节点中有一个元素，该元素有一个关键值域；所有元素的关键值各不相同；任何节点左子树的关键值小于该节点的关键值；任何节点右子树的关键值大于该节点的关键值。操作C re a t e ( )：创建一个空的二叉搜索树S e a rc h ( k , e )：将关键值为k 的元素返回到e 中；如果操作失败则返回f a l s e，否则返回t r u eI n s e rt ( e )：将元素e 插入到搜索树中D e l e t e ( k , e )：删除关键值为k 的元素并且将其返回到e 中A s c e n d ( )：按照关键值的升序排列输出所有元素第11章搜索树3 2 1下载a) a) b) b) c) ADT 11-2 带索引的二叉搜索树的抽象数据类型描述抽象数据类型I n d e x e d B S Tree 实例除每一个节点有一个LeftSize 域以外，其他与B S Tree 相同操作C re a t e ( )：产生一个空的带索引的二叉搜索树S e a rc h ( k , e )：将关键值为k 的元素返回到e 中；如果操作失败返回f a l s e，否则返回t ru eI n d e x S e a rc h ( k , e )：将第k 个元素返回到e 中I n s e rt ( e )：将元素e 插入到搜索树D e l e t e ( k , e )：删除关键值为k 的元素并且将其返回到e 中I n d e x D e l e t e ( k , e )：删除第k 个元素并将其返回到e 中A s c e n d ( )：按照关键值的升序排列输出所有元素11.1.3 类B S Tr e e因为在执行操作时，二叉搜索树中元素的数量和树的外形同时改变，所以可以用 8 . 4节中的链表来描述二叉搜索树。如果从类B i n a r y Tr e e（见程序8 - 7）中派生类B S Tr e e，那么可以大大简化B S Tree 类的设计，见程序11 - 1。由于B S Tree 是从B i n a r y Tree 派生而来的，因此它继承了B i n a r y Tree 的所有成员。但是，它只能访问那些共享成员和保护成员。为了访问 B i n a r y Tree 私有成员r o o t，需要把B S Tree 定义为B i n a r y Tree 的友元。程序11-1 二叉搜索树的类定义templateclass BSTree : public BinaryTree p u b l i c :bool Search(const K& k, E& e) const;B S Tree& Insert(const E& e);B S Tree& Delete(const K& k, E& e);void Ascend() InOutput(); ;I n d e x e d B S Tree 类也可以定义为B i n a r y Tree 的一个派生类（见练习5） 。可以通过调用8 . 9节所定义的中序输出函数InOutput 将二叉搜索树按升序输出，该函数首先输出左子树中的元素（关键值较小的元素） ，然后输出根，最后输出右子树中的元素（关键值较大的元素） 。对于有n 个元素的树来说，该函数的时间复杂性为(n)。11.1.4 搜索假设需要查找关键值为 k 的元素，那么先从根开始。如果根为空，那么搜索树不包含任何元素，查找失败，否则，将 k 与根的关键值相比较，如果 k 小于根节点的关键值，那么就不必搜索右子树中的元素，只要在左子树中搜索即可。如果 k 大于根节点的关键值，则正好相反，只需在右子树中搜索即可。如果 k 等于根节点的关键值，则查找成功，搜索终止。在3 2 2第二部分数 据 结 构下载子树中的查找与此类似，程序 11 - 2给出了