[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:

• 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 unsorted 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

• 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

1. revises linear probing -- CSE1303
3. Table operations can be O(1)-time on average
4. (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

 0 1 2 3 4 5 6 7 ? ? ? ? ? ? ? ?

Suppose   hash("fred")=6,   hash("anne") = hash("jim") = 2

 0 1 2 3 4 5 6 7 ? ? anne ? ? ? fred ?

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

steps of size +1, +2, +3, ...

i.e. hash+1, hash+3, hash+6, . . . (mod N)

Called quadratic because . . . :

``` x:      1   2   3   4 ...
x2:     1   4   9  16 ...
diff1:    3   5   7 ...
diff2:      2   2 ...
diff3:        0 ...
```

A polynomial of degree `k', has constant kth-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

### Binary Search Tree (BST)

1. The empty tree is a BST

2. If T is not empty,

1. the elements in the left subtree are less than the element in the root

2. the elements in the right subtree are greater than the element in the root

3. the left subtree is a BST

4. the right subtree is a BST

NB. Don't forget last two conditions!

Binary Search Tree

 // clear T := empty_tree   &   garbage collect? return( ? T is the empty_tree ? ) 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:

1. no children, x in a leaf
• easy: free leaf; set sub-tree to empty_tree

2. one child
• fairly easy . . .

3. two children
• tricky . . .

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 !

 [use demo'!]

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).