Untitled

 avatar
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...