第5章　查找

概述

我们可能会在一个给定的元素集合C上执行下述三个基本查询：

存在性查询：C包含一个目标元素t吗？

很多时候我们只想知道一个给定集合C中是否包含一个特定的值t。如果这样的元素存在并且其值和t相等，那么这个查询的结果将是真，否则的话就是假。

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

检索查询：返回C中值和t匹配的元素。

当复杂的元素存储在该集合时，元素匹配的定义是基于键值或者元素的属性集合的子集匹配。例如，当在一个从机动车辆部门获得的信息集合中检索时，查询者需要提供驾驶员的驾照号码来获得许可驾驶员的全部信息。

关联查找：返回集合中和目标键值元素k关联的信息。

在复杂的结构中存储额外的信息是非常常见的。我们可以将额外的信息和集合中的元素k相关联，然后根据需要检索和操作。

对于本章讨论的算法，我们假设存在一个集合U，并且U包含了将要检索的值e。集合C是U的一个子集，目标元素t是U的一个元素。如果t是一个键值，那么U是一个可能的键值集合。

正如我们所见，知道C中的元素能否被随机存储或者能否被遍历是非常重要的。当集合能够为任意元素建立索引时，我们使用记号A来表示这种集合，用A[i]表示集合中的第i个元素。为了方便起见，我们使用值nil来表示不在U中的元素，当查询要求返回集合中的特定元素，但是元素又不是当前指向的元素时，这个值是非常有用的。一般来说，我们假设不可能在集合中寻找nil。

本章的算法描述了特定的方法来结构化数据，以便于更加高效地处理这些请求。一种方法是考虑使用第4章介绍过的排序算法对集合C进行排序。我们将会看到，处理查询的效率的确会得到改善，但是在维护有序集合时，会有一些其他开销，尤其是在可能会有对几何中的元素进行大量的删除和插入操作的时候。你首先必须选择合适的结构，并不仅仅是为了加速某一类查询的性能，同时也要在面对随机存储和大量重复的查询，维护集合结构时，降低整体的性能开销。