搜索树（二叉搜索树红黑树B树）

5星 · 超过95%的资源需积分: 9 25 浏览量更新于2023-07-13 收藏 1.74MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

下载

第11章搜索树

本章是关于树结构的最后一章，我们将给出一种适合于描述字典的树形结构。第 7章中的

字典描述仅能提供比较好的平均性能，而在最坏情况下的性能很差。当用跳表来描述一个 n 元

素的字典时，对其进行搜索、插入或者删除操作所需要的平均时间为 O ( l o g n ) ，而最坏情况下

的时间为 (n)。当用散列来描述一个n 元素的字典时，对其进行搜索、插入或者删除操作所需

要的平均和最坏时间分别为 ( l ) 和 (n)。使用跳表很容易对字典元素进行高效的顺序访问

（如按照升序搜索元素），而散列却做不到这一点。当用平衡搜索树来描述一个n 元素的字典时，

对其进行搜索、插入或者删除所需要的平均时间和最坏时间均为 ( l o g n ) ，按元素排名进行的

查找和删除操作所需要的时间为 O ( l o g n ) ，并且所有字典元素能够在线性时间内按升序输出。

正因为这样（无论是平衡还是非平衡搜索树），所以在搜索树中进行顺序访问时，搜索每个元

素所需要的平均时间为 ( l )。

实际上，如果所期望的操作为查找、插入和删除（均根据元素的关键值来进行），则可以

借助于散列函数来实现平衡搜索树。当字典操作仅按关键值来进行时，可将平衡搜索用于那些

对时间要求比较严格的应用，以确保任何字典操作所需要的时间都不会超过指定的时间量。平

衡搜索树也可用于按排名来进行查找和删除操作的情形。对于那些不按精确的关键值匹配进行

字典操作的应用（比如寻找关键值大于k 的最小元素），同样可使用平衡搜索树。

本章将首先介绍二叉搜索树。这种树提供了可与跳表相媲美的渐进复杂性。其搜索、插入

和删除操作的平均时间复杂性为 O ( l o g n)，最坏时间复杂性为 (n)。接下来将介绍两种大家比

较熟悉的平衡树：AV L 树和红-黑树。无论哪一种树，其搜索、插入和删除操作都能在对数时

间内完成（平均和最坏情况）。两种结构的实际运行性能也很接近， AV L 树一般稍微快一些。

所有的平衡树结构都使用“旋转”来保持平衡。 AV L 树在执行每个插入操作时最多需要一次旋

转，执行每个删除操作时最多需要 O ( l o gn)次旋转；而红-黑树对于每个插入和删除操作，都需

要执行一次旋转。这种差别对于大多数仅需 ( l )时间进行一次旋转的应用来说无关紧要，但对

于那些不能在常量时间内完成一次旋转的应用来说就非常重要了，比如平衡优先搜索树

McCreight 就是这样一种应用。平衡优先搜索树用于描述具有两个关键值的元素，此时，每个

关键值是一对数(x,y)。它同时是一个关于y 的优先队列和关于 x 的搜索树。在平衡优先搜索树

中执行旋转时，每次旋转都需耗时 O ( l o gn)。如果用红-黑树来描述平衡优先搜索树，由于每一

次插入或删除后仅需执行一次旋转，因此插入或删除操作总的时间复杂性仍保持为 O ( l o g n)；

当使用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 (n l o g n ) 时间内完成排序和在 (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 g n )的

时间内完成操作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 第二部分数据结构

下载

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 e

I 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 二叉搜索树的类定义

template<class E, class K>

class BSTree : public BinaryTree<E> {

p u b l i c :

bool Search(const K& k, E& e) const;

B S Tree<E,K>& Insert(const E& e);

B S Tree<E,K>& 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 第二部分数据结构

下载

剩余45页未读，继续阅读

春江听雨

粉丝: 22
资源: 8

会员权益专享

搜索树（二叉搜索树红黑树 B树）

会员权益专享

最新资源

搜索树（二叉搜索树 红黑树 B树）

红黑树和二叉搜索树的C语言实现及性能比较

二叉搜索树，红黑树，AVL平衡树，B树

红黑树、二叉搜索树的实现和性能比较

对比红黑树和二叉搜索树

红黑树和二叉搜索树的差别

为什么红黑树的搜索操作比二叉搜索树快？

红黑树和二叉搜索树的区别是不是只是红黑树多了一个颜色的判断？

二叉树 二叉搜索树 红黑树

树: 二叉搜索树 插入和删除 树遍历 AVL树 红黑树

讲一下红黑树和b树和二叉平衡树?

为什么红黑树的查询操作比二叉搜索树快

红黑树和二叉平衡树的比较

二叉平衡树和二叉搜索树

红黑树与平衡二叉搜索树的不同场景下的选择，各自优缺点

**HashMap1.8用的是红黑树,为什么没有用其他的树?比如说二叉搜索树**

解释一下啊、二叉搜索树

二叉搜索树时间复杂度

二叉搜索树的介绍与构建

二叉搜索树 的时间复杂度如何确认

平衡二叉树是二叉搜索树吗？

会员权益专享

最新资源

搜索树（二叉搜索树红黑树 B树）

二叉树二叉搜索树红黑树

树: 二叉搜索树插入和删除树遍历 AVL树红黑树

HashMap1.8用的是红黑树,为什么没有用其他的树?比如说二叉搜索树

二叉搜索树的时间复杂度如何确认