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 ADT

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

• [class!] revise hashing
  
  
  • linear probing
    
    
  • quadratic probing
    
    
  • chaining
    
    

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)

• 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

Example hash function (on strings)

hash("xy...z") =

  ( ( ... (ascii(x)*3 + ascii(y))*3 + ... ) *3 + ascii(z)) mod N

This works well because [__________________].

Collisions!

• | Strings | = infinity
  
  
• | [ 0 .. N-1 ] | = N
  
  
• hash : Strings -> [0..N] must be many-to-one.

Empty hash table

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

What about jim?  (Chaining would now add jim to a linked list after anne.)

A probing strategy is used to find a free place for jim.

Linear probing tries hash+1, hash+2, hash+3, . . . (mod N).

(NB. Complications for deletion.)

Suppose hash(jill) = 3, probe . . .

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

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 k^th-differences. (This was the key to Babbage's difference engine.) . . .

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

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

• 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___________]

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

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