Dictionaries and Binary Search Trees PDF

# Chapter 15: Dictionaries and Binary Search Trees ## 15.1 Abstract Data Type - In this chapter, we consider the data type of a dictionary, which is a last abstract data type with lots of applications. - A dictionary is a mapping of keys to values where each key has at most one value. - Dictionari...

# Chapter 15: Dictionaries and Binary Search Trees ## 15.1 Abstract Data Type - In this chapter, we consider the data type of a dictionary, which is a last abstract data type with lots of applications. - A dictionary is a mapping of keys to values where each key has at most one value. - Dictionaries have three main operations: - `put(key, value)`: Inserts a new key-value pair into the dictionary. - `get(key)`: Returns the value associated with the given key if the key exists. - `remove(key)`: Removes the key and associated value from the dictionary. - The `MyDict` trait defines the interface for a dictionary data type. ## 15.1.1 Implementation with Linked Nodes - A dictionary can be implemented with a singly linked list where each node contains a key-value pair. - The `get()` and `contains()` methods iterate through the linked list to find the key. - The `remove()` method updates the links to remove the node containing the specified key. - The `put()` method inserts a new node at the end of the linked list if the key is not already present. - All these operations take O(n) time in the worst case where n is the number of key-value pairs. ## 15.1.2 Implementation with Arrays - A dictionary can be implemented with an array where each array element stores a key-value pair. - The `get()` and `contains()` methods iterate through the array to find the key. - The `remove()` method swaps the element containing the key with the last element and decrements the array size. - The `put()` method inserts the new key-value pair at the end of the array if there is space available. - All these operations also take O(n) time in the worst case where n is the number of key-value pairs. ## 15.1.3 Conclusion - The naive implementations using linked lists or arrays have O(n) time complexity for all operations. - A better approach for implementing dictionaries is using "hashing" which allows for O(1) average time complexity, but this is not discussed in the document. - For the following sections, a different approach using binary search trees is going to be used to implement dictionaries. ## 15.2 Binary Search Trees - Binary Search Trees are used to represent sets of keys that are totally ordered. - **Attention**: Binary Search Trees and Heaps are totally different concepts even though they are both binary trees. - We will ignore values for simplicity, although each key has a corresponding value in reality. ## 15.2.1 Definition - A binary search tree can be defined recursively: - The empty tree is a binary search tree. - A non-empty tree is a binary search tree if its root is greater than all elements in its left subtree and smaller than all elements in its right subtree, and both subtrees themselves are binary search trees. ## 15.2.2 Searching - The search operation works by comparing the search key with the root key: - If the tree is empty, the search key is not found. - If the search key matches the root key, the search key is found. - If the search key is smaller than the root key, the search continues in the left subtree recursively. - If the search key is larger than the root key, the search continues in the right subtree recursively. - In the worst case, the search operation takes O(h) time where h is the height of the tree. ## 15.2.3 Insertion - The insertion operation works similarly to the search operation: - The search key is compared with the root key and the search continues in the appropriate subtree recursively. - A new node containing the search key is inserted at the leaf node. - If the search key is already present, the value is updated. - The worst-case time complexity of insertion is also O(h). ## 15.2.4 Removing - Removing a node from a binary search tree has different cases: - **Removing the maximum**: If the node has a right subtree, the maximum is in the right subtree. The maximum is found by recursively calling the `removeMax()` function on the right subtree until a node with no right subtree is found. The node with the maximum is then removed and its left subtree becomes the new right subtree of the node where the maximum was removed. If the node has no right subtree, it is the maximum itself and its left subtree replaces it. - **General case**: The `remove()` function recursively searches for the key. If the key is found: - If the node has no left subtree, it is replaced by its right subtree. - If the node has a left subtree, the maximum from the left subtree is found and replaces the node. The `removeMax()` function is used to remove the maximum from the left subtree. - The worst-case time complexity for removing an element is O(h). ## 15.2.5 Traversing a tree - Two traversal algorithms for binary search trees are discussed: - **Levelorder**: This method uses a queue to visit nodes level by level. The root is enqueued first. After visiting a node, its children are enqueued. The process continues until the queue is empty. - **Preorder**: This method recursively traverses the tree: - Visit the root node. - Recursively traverse the left subtree. - Recursively traverse the right subtree. - Other traversal methods such as **inorder** and **postorder** are briefly described. - These traversal methods provide different orders for visiting the elements of the tree. Footnotes: <br> &#x20; ¹ This sentence points to a footnote that is not included in the document.