reading algorithm

Searching

Symbol Tables(and Ordered Symbol Tables)

• Definition: A symbol table is a data structure for key-value pairs that supports two operations:
  insert (put) a new pair into the table and search for (get) the value as- sociated with a given key.
• Duplicated Keys:
  • Only one value is associated with each key (no duplicate keys in a table).
  • When a client puts a key-value pair into a table already containing that key (and an associated value),
    the new value replaces the old one.Only one value is associated with each key (no duplicate keys in a table).
• No null key
• No null value
• Deletion
  • lazy: put(key, null)
  • eager: delete(key)
• Client For Benchmarking
  • Search and insert operations are intermixed.
  • The number of distinct keys is not small.
  • Substantially more searches than inserts are likely.
  • Search and insert patterns, though unpredictable, are not random.
    
    
    

Alternative Solution

• SequentialSearchST(Linked List)
  • O(N) for get
  • O(N) for put
• BinarySearchST
  • O(logN) for get
  • O(N) for put
    
• BinarySearch Tree
  • Definition: A binary search tree (BST) is a binary tree where each node has a
    Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the
    keys in all nodes in that node’s left subtree and small- er than the keys in all nodes in that node’s right subtree.
  • Size: size(x) = size(x.left) + size(x.right) + 1