Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def height(Node_for_tree):
- if Node_for_tree is not None:
- return Node_for_tree.height
- else:
- return -1
- class Node_for_tree:
- def __init__(self, key, DocID):
- self.key = key
- self.height = 0
- self.right = None
- self.left = None
- self.DocID = DocID
- def balance(self):
- return height(self.right) - height(self.left)
- class AVL_Tree:
- def __init__(self):
- self.root = None
- self.how_much_nodes = 0
- def Turn_left(self, Old_root):
- New_root = Old_root.right
- New_root_left = New_root.left
- New_root.left = Old_root
- Old_root.right = New_root_left
- Old_root.height = 1 + max(height(Old_root.left), height(Old_root.right))
- New_root.height = 1 + max(height(New_root.left), height(New_root.right))
- return New_root
- def Turn_right(self, Old_root):
- New_root = Old_root.left
- New_root_right = New_root.right
- New_root.right = Old_root
- Old_root.left = New_root_right
- Old_root.height = 1 + max(height(Old_root.left), height(Old_root.right))
- New_root.height = 1 + max(height(New_root.left), height(New_root.right))
- return New_root
- def add_key(self, key, DocID, Node):
- if Node is not None:
- if key < Node.key:
- Node.left = self.add_key(key, DocID, Node.left)
- elif key > Node.key:
- Node.right = self.add_key(key, DocID, Node.right)
- else:
- Node.DocID.append(DocID)
- return Node
- else:
- self.how_much_nodes += 1
- return Node_for_tree(key, Set(DocID))
- Node.height = 1 + max(height(Node.left), height(Node.right))
- balance = Node.balance()
- if balance == 2:
- if Node.right.balance() == 1:
- return self.Turn_left(Node)
- else:
- Node.right = self.Turn_right(Node.right)
- return self.Turn_left(Node)
- if balance == -2:
- if Node.left.balance() == -1:
- return self.Turn_right(Node)
- else:
- Node.left = self.Turn_left(Node.left)
- return self.Turn_right(Node)
- return Node
- def add_value_in_Set(self, key, DocID, Node):
- if Node is not None:
- if key < Node.key:
- Node.left = self.add_key(key, DocID, Node.left)
- elif key > Node.key:
- Node.right = self.add_key(key, DocID, Node.right)
- else:
- return Node
- else:
- self.how_much_nodes += 1
- return Node_for_tree(key, DocID)
- Node.height = 1 + max(height(Node.left), height(Node.right))
- balance = Node.balance()
- if balance == 2:
- if Node.right.balance() == 1:
- return self.Turn_left(Node)
- else:
- Node.right = self.Turn_right(Node.right)
- return self.Turn_left(Node)
- if balance == -2:
- if Node.left.balance() == -1:
- return self.Turn_right(Node)
- else:
- Node.left = self.Turn_left(Node.left)
- return self.Turn_right(Node)
- return Node
- def print_keys(self, Node):
- if Node.left is not None:
- self.print_keys(Node.left)
- print(Node.key, end = ' ')
- if Node.right != None:
- self.print_keys(Node.right)
- class Set:
- def __init__(self, value):
- self.Tree = AVL_Tree()
- self.Tree.root = self.Tree.add_value_in_Set(value, 'Present', self.Tree.root)
- def append(self, value):
- self.Tree.root = self.Tree.add_value_in_Set(value, 'Present', self.Tree.root)
- def get(self):
- self.Tree.print_keys(self.Tree.root)
- print('')
- class Inverted_Index(AVL_Tree):
- def index_document(self, document, DocID):
- for word in document:
- self.root = self.add_key(word, DocID, self.root)
- def search(self, key):
- Node = self.root
- while Node is not None:
- if key > Node.key:
- Node = Node.right
- elif key < Node.key:
- Node = Node.left
- else:
- Node.DocID.get()
- return
- print(-1)
- def get_keys(self):
- self.print_keys(self.root)
- def how_much_docs(self, Node):
- amount_of_docs = 0
- if Node.left != None:
- amount_of_docs += self.how_much_docs(Node.left)
- amount_of_docs += Node.DocID.Tree.how_much_nodes
- if Node.right != None:
- amount_of_docs += self.how_much_docs(Node.right)
- return amount_of_docs
- def get_avarage_documents_per_key(self):
- print(round(self.how_much_docs(self.root)/self.how_much_nodes))
- #Старт программы#
- if __name__ == '__main__':
- num_documents = int(input())
- Inverted_Index = Inverted_Index()
- for i in range(num_documents):
- document = list(map(str, input().split()))
- Inverted_Index.index_document(document, i)
- num_queries = int(input())
- for i in range(num_queries):
- queries_item = input()
- Inverted_Index.search(queries_item)
- Inverted_Index.get_avarage_documents_per_key()
- try:
- print_keys_flag = input()
- should_print_keys = print_keys_flag == 'print_keys'
- except:
- should_print_keys = False
- if should_print_keys:
- Inverted_Index.get_keys()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement