[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

Now examine:

Table ADT

Table operations:

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

[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
  2. defines quadratic probing
  3. Table operations can be O(1)-time on average
  4. (does not discuss chaining -- CSE1303)

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!

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 ?

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
©
L
.
A
l
l
i
s
o
n

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

Back to Table in general.

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

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
[use demo'!]

Binary Search Tree

[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

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