第七章Searching
7.1
Basic Search Techniques
A
table or a file is a group of elements, each of which is called a
record. Associated with each record is a key, which is used to
differentiate among different records.
In
the simplest form, the key is contained within the record at a
specific offset from the start of the record. Such a key is called
an internal key or an embedded key.
For
every file there is at least one set of keys that is unique. Such a
key is called a primary key.
It
will probably not be unique, since there may be two records with the
same state in the file, such a key is called a secondary key.
A
search algorithm is an algorithm that accepts an argument a and tries
to find a record whose key is a.
A
table of records in which a key is used for retrieval is often called
a search table or as dictionary.
Dictionary
as an abstract data type
typedef
KEYTYPE ... /* a type of key*/
typedef
RECTYPE … /* a type of record*/
RECTYPE
nullrec=... /*a “null” record*/
KEYTYPE
keyfunct(r)
RECTYPE
r;
{…
};
abstract
typedef [rectype] TABLE (RECTYPE);
abstract
member(tbl,k)
TABLE(RECTYPE)
tbl;
KEYTYPE
k;
postcondition
if(there exists an r in tbl such that keyfunct(r)==k)
then
member = TRUE
else
member = FALSE
abstract
RECTYPE search(tbl,k)
TABLE(RECTYPE)
tbl;
KEYTYPE
k;
postcondition
(not member(tbl,k)&& (search == nullrec)
||
(member(tbl,k) &&keyfunct(search)==k);
abstract
insert(tbl,r)
TABLE(RECTYPE)
tbl;
KEYTYPE
r;
precondition
member(tbl,keyfunct(r))==FALSE
postcondition
insert(tbl,r);
(tbl-[r])==tbl'
abstract
delete(tbl,k)
TABLE(RECTYPE)
tbl;
KEYTYPE
k;
postcondition
tbl==(tbl'-[search(tbl,k)]);
Binary
Search
The
most efficient method of searching a sequential table without the use
of auxiliary indices or table is the binary search.
O(logn)
low=0;
hi=n-1;
while(low<=hi)
{
mid=(low+hi)/2;
if(key==k(mid))
return
mid;
if(key<k(mid))
hi=mid-1;
else
low=mid+1
}
return
-1;
Interpolation
Search
Another
technique for searching an ordered array is called interpolation
search. If the keys are uniformly distributed between k(0) and k(n-1)
O(loglogn)
Tree
Searching
Inserting
into a binary tree
q=null;
p=tree;
while(p!=null)
{
if(key==k(p))
return
p;
q=p;
if(key<k(p))
p=left(p);
else
p=right(p);
}
v=maketree(rec,key);
if(q==null)
tree=v;
else
if(key<k(q))
left(q)=v;
else
right(q)=v;
return
v;
Deleting
from a binary search tree
q=null;
p=tree;
while(p!=null
&& k(p)!=key)
{
q=p;
p=(key<k(p)?left(p):right(p);
}
if(p==null)
return;
Balanced
Trees
If
the probability of searching for a key in a table is the same for all
keys, a balanced tree yields the most efficient search.
/*
Part I: search and inset into the binary tree*/
fp=null;
p=tree;
fya=null;
ya=p;
/*
ya points the youngest ancestor whick may become unbalanced*/
while(p!=null)
{
if(key==k(p))
return
p;
q=
(key <k(p))? left(p):right(p);
if(q!=null)
if(bal(q)!=0)
{
fya=p;
ya=q;
}
fp=p;
p=q;
}
q=maketree(rec,key);
bal(q)=0;
(key<k(fp))?left(fp)=q:right(fp)=q;
p=(key<k(ya))?left(ya):right(ya);
s=p;
while(p!=q)
{
if(key<k(p))
{
bal(p)=1;
p=left(p);
}
else
{
bal(p)=-1;
p=right(p);
}
}
/*Part
II:tree is unbalanced*/
imbal=(key<k(ya))?1:-1;
if(bal(ya)==0)
{
bal(ya)=imbal;
return
q;
}
/*
part III:rebalanced*/
if(bal(s)==imbal)
{
P=S;
if(imbal==-1)
rightrotation(ya);
else
leftrotation(ya);
bal(ya)=0;
bal(s)=0;
}
else
{
if(imbal==1)
{
p=right(s);
leftrotation(s);
left(ya)=p;
rightrotation(ya);
}
else
{
p=left(s);
right(ya)=p;
rightrotation(s);
leftrotation(ya);
}
if(bal(p)==0)
{
bal(ya)=0';
bal(s)=0;
}
else
{
if(bal(p)==imbal)
{
bal(ya)=-imbal;
bal(s)=0;
}
else
{
bal(ya)=0;
bal(s)=imbal;
}
}
bal(p)=0
}
if(fya==null)
tree=p;
else
ya=right(fya))?right(fya)=p:left(fya)=p;
return
q;
A
multiway search tree of order n is a general tree in which each node
has n or fewer subtrees and contains one fewer key than it has
subtrees.
p=tree;
if(p==null)
{
position
= -1;
return
-1;
}
i=nodesearch(p,key);
if(i<numtrees(p)-1&&
key==k(p,i)
{
position=i;
return
p;
}
return
search(son(p,i));
====================================
p=tree;
while(p!=null)
{
i=nodesearch(p,key);
if(i<numtrees(p)-1&&
key==k(p,i)
{
position=i;
return
p;
}
p=son(p,i);
}
position
= -1;
return
-1;
traversing
a multiway tree
if(tree
!=null)
{
nt=numtrees(tree);
for(i=0;i<nt-1;i++)
{
traverse(son(tree,i);
printf(“%d”,k(tree,i));
}
traverse(son(tree,nt);
}
B+-Trees
One
of the major drawbacks of the B-tree is the difficulty of traversing
the key sequentially.
11.4
Hashing
A
function that transforms a key into a table index is called a hash
function. If h is a hash function and key is a key, h(key) is called
the hash of key and is the index at which a record with the key
should be placed.
#define
TABLESIZE …
typedef
KEYTYPE …
typedef
RECTYPE …
struct
record{
KEYTYPE
k;
RECTYPE
r;
}
table[TABLESIZE];
int
search(KEYTYPE key,RECTYPE rec)
{
int
i;
i=h(key);
while(table[i].k!=key
&& table[i].k!=nullkey)
{
i=rh(i);
//rehash
}
if(table[i].k==nullkey)
{
table[i].k=key;
table[i].r=rec;
}
return
i;
}
struct
nodetype *search(KEYTYPE key, RECTYPE rec)
{
struct
nodetype *p,*q,*s;
i=h(key);
q=NULL;
p=bucket[i];
while(p!=NULL&&p->k!=key)
{
q=p;
p=p->next;
}
if(p->k==key)
return
p;
s=getnode();
s->k=key;
s->r=rec;
s->next=NULL;
if(q==NULL)
bucket[i]=s;
else
q->next=s;
return
s;
}
Perfect
Hash Functions
Given
a set of keys K={k1,k2,...,kn} a perfect hash function is a hash
function h such that h(ki)!=h(kj) for all distinct i and j.
h(key)=((r+s*key)%x)d
remainder
reduction perfect hash function.
