----- NEEDS JAVASCRIPT ON. -----
[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Sunday, 28-Nov-2021 05:33:19 AEDT
Instructions :
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Dictionary / Lookup Tables / Searching: Introduction
Have seen
sorting
which can speed up searching
in lookup (dictionary)
e.g. by use of binary search
Now examine:
Table ADT
implementation by various data structures
Table operations:
clear - create an empty lookup table
insert - add a new element
lookup - search for a given key
delete - delete a given key
empty? - query if table is empty or not
[see rules that operations obey]
Table
table by un sorted array, a[1..N]
clear: O(1) time
lookup: O(n)-time, average and worst
insert: lookup + O(1)
delete: lookup + O(1)
empty?: O(1)-time
table by sorted array, a[1..N]
clear: O(1) time
lookup: O(log(n))-time
insert: O(n)-time, worst and average
delete: O(n)-time, worst and average
empty?: O(1)-time
Table
[class!] revise hashing
linear probing
quadratic probing
chaining
[Lecturer: the next few slides discuss Hashing
and particularly quadratic probing, can skip
or cover quickly depending on class background.]
slide H1, revision
Revision of Hash
Tables
revises linear probing -- CSE1303
defines quadratic probing
Table operations can be O(1)-time on average
(does not discuss chaining -- CSE1303)
key_type is a sparse data type
e.g. strings
infinitely-many possible strings, but
only finitely many used in any one example
hash : key_type -> [0,N-1], in a pseudo-random way
slide H2
Example hash function (on strings)
hash("xy...z") =
( ( ... (ascii(x)*3 + ascii(y))*3 + ... ) *3 + ascii(z)) mod N
This works well because [__________________].
slide H3
Collisions!
| Strings | = infinity
| [ 0 .. N-1 ] | = N
hash : Strings -> [0..N] must be many-to-one.
slide H4
Empty hash table
Suppose hash("fred")=6,
hash("anne") = hash("jim") = 2
0
1
2
3
4
5
6
7
? ?
anne
? ? ?
fred
?
What about jim?
(Chaining would now add jim to a linked list after anne.)
slide H5
A probing strategy is used to find a free place for jim.
0
1
2
3
4
5
6
7
? ?
anne ?jim?
? ? ?
fred
?
Linear probing tries hash+1, hash+2, hash+3, . . . (mod N).
0
1
2
3
4
5
6
7
? ?
anne
jim
? ?
fred
?
(NB. Complications for deletion.)
slide H6
Suppose hash(jill) = 3, probe . . .
0
1
2
3
4
5
6
7
? ?
anne
jim
jill
?
fred
?
The problem with linear probing is that collisions
from "close" hash values tend to merge
into big "blocks".
Can degenerate to linear search, O(N).
slide H7
Quadratic probing
steps of size +1, +2, +3, ...
i.e. hash+1, hash+3, hash+6, . . . (mod N)
Called quadratic because . . . :
x: 1 2 3 4 ...
x^{2} : 1 4 9 16 ...
diff1: 3 5 7 ...
diff2: 2 2 ...
diff3: 0 ...
A polynomial of degree `k', has constant k^{th} -differences.
(This was the key to
Babbage's
difference engine.) . . .
slide H8
. . . can see that if hash(x) = hash(y)+1
then probes for collisions on `x' and on `y'
quickly separate out
leads to smaller "blocks" and
hence better performance, see
[test figures ]
[lecturer: draw diagram to illustrate; class: take notes!]
(Have to be careful to be able to probe all locations.)
Back to
Table
in general.
A table can be implemented by other data-structures
which must implement the Table ADT's operators and rules.
Specification v. implementation
[lecturer: discuss software engineering implications;
class: take notes]
Many implementations of Table e.g. by
The empty tree is a BST
If T is not empty,
the elements in the left subtree are less than
the element in the root
the elements in the right subtree are greater than
the element in the root
the left subtree is a BST
the right subtree is a BST
NB. Don't forget last two conditions!
Binary Search
Tree
clear
T := empty_tree
& garbage collect?
empty?
return( ? T is the empty_tree ? )
search for x in T
if T is empty_tree then
not present
else if x < element(T) then
search for x in left(T)
else if x > element(T) then
search for x in right(T)
else found !
Binary Search
Tree,
insert x in T :
if empty? T then
T := fork x empty_tree empty_tree
else if x < element(T) then
insert x in left(T)
else if x > element(T) then
insert x in right(T)
else // x equals element(T)
. . . it depends . . . [discuss]
end_if
Note, elements
are inserted in
new leaves .
Binary Search Tree,
delete x from T :
first lookup x in T,
? may be error if absent ?
assuming x found, three cases:
no children, x in a leaf
easy: free leaf; set sub-tree to empty_tree
one child
two children
delete from
Binary Search Tree,
one child :
T:-------> x T:.
. .
. .
. .
. .
T' T'
before after
Free internal node; set T to sub-tree T'
delete `x' from
Binary Search Tree,
two children :
T:------------> x
. .
. .
. .
. .
. .
T1 T2
Deleting x node would lose one of T1 or T2, so . . .
find smallest element, y, in right tree, T2
[or ____________]
overwrite x with y,
delete y from T2 !
Binary Search Tree
smallest element, y, is the left-most in a BST
(largest element is the right-most )
NB. y cannot have two children (!) ,
so deleting y is "easy"
Complexity
lookup, insert, delete O(log(n))-time on average
O(n)-time, worst-case
[why___________]
[lecturer: briefly or skip; class: study at home!]
Tree delete(ElementType id, Tree T)
{ if(T != null)
{ if( id < T.elt )
T.left = delete(id, T.left);
else if( id > T.elt )
T.right = delete(id, T.right);
else /* found id: T.elt == id */
if(T.left == null) /* left is empty_tree */
T=T.right;
else if(T.right == null) /* right is empty_tree */
T=T.left;
else /* neither subtree is empty_tree */
findAndDel(T); /* see next slide */
}
return T;
} /* also see over page . . . */
[lecturer: briefly or skip; class: study at home!]
void findAndDel(Tree T)
/* find smallest element in right subtree, copy it
to the root node and delete the original. */
{ Tree R = T.right; /* one step right, then */
while( R.left != null ) /* as far left as possible */
R = R.left;
T.elt = R.elt; /* copy */
T.right = delete(T.elt, T.right); /* delete original! */
return;
}
Dictionary / Lookup Tables / Searching: Summary
Lookup
Table
ADT, abstract properties
can implement by
unsorted array,
sorted array,
hashing,
binary search tree, or
(to come ) AVL tree,
[demo' ]
or other
e.g. Trie etc. . . .
© L.Allison ,
Sunday, 28-Nov-2021 05:33:19 AEDT
users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/09table.shtml
Computer Science,
Software Engineering,
Science (Computer Science).