Dictionary

ADT Dictionary consists of a collection of items each of which contains:

• key
• data (value) $\to$ called a key-value pair (KVP)

Operations:

• search(k)
• insert(k, v)
• delete(k)

Unordered array or linked list:

• search $\Theta (n)$
• insert $\Theta (1)$
• delete $\Theta (n)$, because need to search

Questions

• Choose all the realizations of a Dictionary ADT from the data structures given below:
  • AVL Tree
  • Sorted Array
  • Linked List
  • Binary Search Tree
  • Max-Heap