文档介绍：计算机算法 ——设计与分析导论
南开大学计算机科学与技术系
刘璟
1
Chapter 4. 数据集合上的搜索(Searching)算法
动态数据集(Dynamic Set)与抽象数据类型(ADT)
二叉搜索树(Binary Search Trees)
随机二叉搜索树(Randomly Built Binary Search Tree)
红黑树(Red-Black Tree)
2-3-4树
Hashing技术
2
动态数据集(Dynamic Set)与抽象数据类型(ADT)
静态数据集(Static Set)中的数据是固定不变的。
动态数据集(Dynamic Set)则是由不断变动的同类型数据元素组成的数据集合。
动态数据集(Dynamic Set)可以表示为一个数据元素的数组:
class DynamicSet {
int setSize;
Object[arraySize] elements;
...
} //Object为数据元素的类型,setSize为当前集合中的元素个数
3
用数组表示集合操作方便,但当集合中的元素个数不断增加时,数组的长度必须扩大。一般采用空间倍增(array doubling)技术,即另外申请一个加倍长度的新数组,把集合中的数据传送过来,取代原有的空间。
其过程为:
arrayDouble(set) {
newSize = 2*arraySize ;
newElements = new Object(newSize) ;
Transfer all elements from the to the newElement;
= newElements ;
= newSize ;
}
更为灵活的存储形式是利用指针和链表(例如线性链表和树结构),这种存储形式在搜索算法中经常用到。
4
搜索问题:在集合中检索出其关键字域的值等于给定值的数据元素。
已知:动态数据集类型DynamicSet的一个实例set和值x。
求:集合set中一个元素Object element, = x。
数据集合上的操作(operation)可以分为两类:
查询(queries)操作:对数据集不做任何变动,仅仅返回有关集合的某些信息;
修改(modifying operations)操作:要对数据集合的某些域进行改动。
一些典型的操作:
Search(S,k):搜索,一个查询操作。对于给定的数据集合S和一个关键字值k,返回S中一个元素(element)的指针x,使得x->key=k。当S中没有符合条件的元素时,返回的指针为空(NULL)。
5
Insert(S,x):插入,一个修改操作。把由x指向的数据元素加入到集合S中,一般假定在x指向的数据元中,与集合运算相关的所有分量(域)都已经初始化。
Delete(S,x):删除,一个修改操作。给定指向集合S中一个元素的指针x,将此元素从S中删除。
Minimum(S):求最小元,一个查询操作。若集合S中所有数据元素的关键字值为一全序集,则返回具有最小关键字值的数据元素的指针。
Maximum(S):求最大元,一个查询操作。返回具有最大关键字值的数据元素的指针。
Deletemin(S):删除最小元,一个修改操作。它相当于Minimum(S)和Delete(S,x)的联合,
即:Delete(S,Minimum(S))。
6
essor(S,x):求后继数据元,一个查询操作。若S中的数据元素按关键字值从小到大排列,x是指向S中某一数据元素的指针,则返回x所指向的数据元素的下一个数据元素的指针。若x指向最后一个数据元素,则返回NULL。
Predecessor(S,x):求前导数据元,一个查询操作。返回x所指向的数据元素的前一个数据元素的指针。若x指向第一个数据元素,则返回NULL。
搜索算法(及相关操作算法)的设计实际上是实现适合各种不同应用需要的ADT,例如:
字典(Dictionary)作为抽象数据类型,可以分为两类:
·静态字典:(静态数据集S,Search);
·动态字典:(动态数据集S,Search,Insert,Delete)。
优先队列(Priority Queue):(动态数据集S,Insert,Deletemin)。
7
二叉搜索树
二叉搜索树又称为二元字典树,是一种最常用的动态数据集的数据结构,可以用于实现字典和优先队列等ADT。
二叉搜索树(Binary Search Trees)
BST的