算法技术手册（原书第2 版）

搜索算法

｜

115

搜索算法

需要的空间未必足够，因为我们对于动态的数据集合

事先

没有任何的了解，所以无法选

择一个比较合适的散列表规模来有效利用资源。而且散列表也不支持有序地遍历元素。

这里可以使用

搜索树

来存储动态数据集合。无论是在内存中还是在二级存储器上，搜索

树不仅性能出色，还能够有序地返回元素，这是散列表无法完成的。最常使用的搜索树

是

二叉搜索树

（

BST

），它的每一个内部结点都最多有两个子结点：

左子结点

和

右子结点

（见

图

5-7

）。

当遇到如下情况时，我们可以考虑使用二叉搜索树：

•

需要有序（升序或降序）地遍历数据。

•

数据的规模未知，而且实现必须应对各种可能的情况。

•

数据频繁改变，且有大量的删除和插入操作。

5.5.1 输入 / 输出

搜索树的输入和输出算法和

二分搜索

的格式基本一样。集合

C

中的每一个元素

e

都会被

存储到搜索树中，并且这些元素都会根据一个或者多个属性计算出键值

k

。这些键值不

仅决定了全集

U

，还必须是全序的。也就是说，给定两个键值

k

i

和

k

j

，只存在三种可能：

k

i

=

k

j

、

k

i

>

k

j

或

k

i

<

k

j

。

如果元素的值本身就是原生类型（如整数或字符串），那么这个值本身就可以作为键值。

否则，这些元素指向的数据结构中将会包含键值（动态计算非常耗费资源）。

5.5.2 使用环境

BST

是一个非空的

结点集合，它所包含的

键值

是全序的。最顶部的

根

结点是

BST

中其他

所有子结点的祖先。每个结点

n

至多包含两个二元结点（即每个结点最多包含两个子结

点），

n

左

和

n

右

。

BST

需要确保二叉搜索树的性质，换言之，如果 ...