Dictionaries and Binary Search Trees

Dictionaries and Binary Search Trees

• Dictionaries are abstract data types with various applications, including translations, storing key-value pairs, and mapping words between languages.
• Dictionaries in computer science store at most one value for each key.
• Key methods for dictionaries include:
  • put(key: K, value: V): Adds a key-value pair.
  • get(key: K): Retrieves the value associated with a key.
  • remove(key: K): Removes a key-value pair.
  • contains(key: K): Checks if a key exists in the dictionary.
  • isEmpty: Checks if the dictionary is empty.

Implementation with Linked Nodes

• Dictionaries can be implemented using linked nodes, similar to queues or stacks.
• Each node stores a key, value, and a pointer to the next node.
• get(key) and contains(key) methods: In worst-case, checking every node takes O(n) time.
• remove(key) method: Worst-case running time is O(n).
• put(key, value) method: Worst-case running time is O(n) due to scanning all nodes.

Implementation with Arrays

• Dictionaries can be implemented using arrays.
• Each array entry stores a key-value pair.
• get(key) and contains(key) methods: In the worst case, checking each entry takes O(n) time.
• remove(key) method: Worst-case running time is O(n), requiring array entry swaps.
• put(key, value) method: Worst-case running time is O(n), requiring scanning all entries.

Conclusion

• Simple implementations of dictionaries using linked nodes or arrays have O(n) worst-case time complexity for most operations.
• Hashing techniques can be used to achieve better, amortized O(1) time complexity.

Binary Search Trees (BSTs)

• BSTs are tree-based data structures.
• Definition: A binary search tree is either empty or has a root node with keys greater than all keys in the left subtree and smaller than all keys in the right subtree. This is an inductive definition implying the left and right subtrees must be binary search trees themselves.
• Searching: The general idea is to compare the target key with the root key. If the target key is smaller, proceed to the left subtree recursively; otherwise, proceed to the right subtree recursively.
  • Worst-case time complexity for searching is O(h), which represents the height of the tree.
• Insertion: Similar recursive approach to searching to determine location for new key -value pair; insert new node as leaf node.
  • Worst-case time complexity for insertion is O(h).
• Removal: Removing a key potentially involves a complex recursive approach to maintain the BST structure properties.
  • In the case of removing the maximum, look at possible right subtrees.
  • If the right subtree is empty then the maximum is the current node.
  • Find the largest element in the left subtree, swap with the key to be deleted and then recursively remove the largest element to maintain BST structure.
  • Worst-case time complexity is O(h).

Traversal

• Levelorder: Enqueue the root in queue, dequeue and add keys and enqueue children nodes and so on.
• Preorder: Visit root, recursively traverse left subtree then recursively traverse right subtree.
• Inorder: Recursively traverse left subtree, visit root, recursively traverse right subtree.
• Postorder: Recursively traverse left subtree, recursively traverse right subtree, then visit root.

Running Time Summary

• Time complexity depends on the height of the tree (h).
  • Best case: O(1) if element is found immediately
  • Worst Case: O(n) if the tree is skewed (linked list)
  • Average Case: O(log n) for balanced trees