Untitled
unknown
plain_text
3 years ago
5.2 kB
12
Indexable
THE CODE IS GIVEN BELOW: import os import math import bisect class Node: def __init__(self, word, meaning): self.word = word self.meaning = meaning self.left = None self.right = None # A Binary Tree class BinaryTree: def __init__(self): self.root = None # Insert a new node in the BST def insert(self, word, meaning): if self.root is None: self.root = Node(word, meaning) else: self._insert(self.root, word, meaning) def _insert(self, cur_node, word, meaning): if cur_node.word > word: if cur_node.left is None: cur_node.left = Node(word, meaning) else: self._insert(cur_node.left, word, meaning) elif cur_node.word < word: if cur_node.right is None: cur_node.right = Node(word, meaning) else: self._insert(cur_node.right, word, meaning) else: print("Word already exists in tree.") # Search a node in BST def search(self, word): if self.root is None: print("Tree is empty") return None else: return self._search(self.root, word) def _search(self, cur_node, word): if cur_node is None: return None elif cur_node.word == word: return cur_node.meaning elif cur_node.word > word: return self._search(cur_node.left, word) else: return self._search(cur_node.right, word) # A Hash Table class HashTable: def __init__(self, size): self.size = size self.slots = [] self.data = [] for i in range(self.size): self.slots.append([]) self.data.append([]) # Hashing Function def hashfunction(self, word, size): word_sum = 0 for i in range(len(word)): word_sum += ord(word[i]) return word_sum%size # Rehash function to get a different hash value def rehash(self, oldhash, size): return (oldhash+1)%size # Insert a new node in the Hash Table def insert(self, word, meaning): hashvalue = self.hashfunction(word,len(self.slots)) if self.slots[hashvalue] == []: self.slots[hashvalue] = BinaryTree() self.slots[hashvalue].insert(word, meaning) self.data[hashvalue].append(word) else: if word not in self.data[hashvalue]: self.slots[hashvalue].insert(word, meaning) self.data[hashvalue].append(word) # Search a node in the Hash Table def search(self, word): hashvalue = self.hashfunction(word,len(self.slots)) found = False if word in self.data[hashvalue]: found = True return self.slots[hashvalue].search(word) return None # Print the Hash Table def __str__(self): for slot in self.slots: if slot is not None: print(slot) # Read words from file def readFile(filename): words_dict = {} with open(filename, 'r') as file: for line in file.readlines(): line = line.strip() pair = line.split(": ") words_dict[pair[0]] = pair[1] return words_dict # Main Program def main(): size = int(input("Enter size of Hash Table: ")) h = HashTable(size) words_dict = readFile("my words.txt") # Insert words and meanings into Hash Table for key, value in words_dict.items(): h.insert(key, value) # Search a word search_word = input("Enter word to search: ") result = h.search(search_word) if result: print(f"{search_word}: {result}") else: print(f"{search_word} not found") if __name__ == '__main__': main() Explanationfor step 1 ADVANTAGES AND DIADVANTAGES ARE GIVEN BELOW: Advantages of using binary search tree: - - It is a fast data structure with a time complexity of O(log n). - It is easy to insert and delete elements. - It is able to store large amounts of data efficiently. - It is easy to traverse the tree in order to find elements. Disadvantages of using binary search tree: - It is not suitable for real-time applications as it may take a long time to search for elements. - It is not very efficient when dealing with large datasets. - It can be difficult to maintain if elements are not inserted in the correct order. Advantages of using Hash Table: - It is fast and efficient for searching, inserting and deleting elements. - It is able to store large amounts of data efficiently. - It is easy to implement and maintain. Disadvantages of using Hash Table: - It can be difficult to maintain if elements are not inserted in the correct order. - It is not suitable for real-time applications as it may take a long time to search for elements. - It can be difficult to implement if the data structure is not implemented properly. Final answer THE QUESTION IS ANSWERES COMPLETELY.
Editor is loading...