Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Node():
- def __init__(self, d = 0):
- self.key = d
- self.height = 1
- self.left = None
- self.right = None
- def height(node):
- if node is None:
- return 0
- return node.height
- def right_rotate(node):
- x = node.left
- T2 = x.right
- x.right = node
- node.left = T2
- node.height = max(height(node.left), height(node.right)) + 1
- x.height = max(height(x.left), height(x.right)) + 1
- return x
- def left_rotate(node):
- y = node.right
- T2 = y.left
- y.left = node
- node.right = T2
- node.height = max(height(node.left), height(node.right)) + 1
- y.height = max(height(y.left), height(y.right)) + 1
- return y
- def get_balance(node):
- if node is None:
- return 0
- return height(node.left) - height(node.right)
- def insert(node, key):
- global m
- if node is None:
- return Node(key)
- if key < node.key:
- node.left = insert(node.left, key)
- elif key > node.key:
- node.right = insert(node.right, key)
- else:
- return node
- node.height = 1 + max(height(node.left), height(node.right))
- balance = get_balance(node)
- if balance > 1 and key < node.left.key:
- return right_rotate(node)
- if balance < -1 and key > node.right.key:
- return left_rotate(node)
- if balance > 1 and key > node.left.key:
- node.left = left_rotate(node.left)
- return right_rotate(node)
- if balance < -1 and key < node.right.key:
- node.right = right_rotate(node.right)
- return left_rotate(node)
- return node
- def min_value_node(node):
- current = node
- while current.left is not None:
- current = current.left
- return current
- def delete_node(root, key):
- global m
- if root is None:
- return root
- if key < root.key:
- root.left = delete_node(root.left, key)
- elif key > root.key:
- root.right = delete_node(root.right, key)
- else:
- if root.left is None or root.right is None:
- temp = None
- if temp == root.left:
- temp = root.right
- else:
- temp = root.left
- if temp is None:
- temp = root
- root = None
- else:
- root = temp
- else:
- temp = min_value_node(root.right)
- root.key = temp.key
- root.right = delete_node(root.right, temp.key)
- if root is None:
- return root
- root.height = max(height(root.left), height(root.right)) + 1
- balance = get_balance(root)
- if balance > 1 and get_balance(root.left) >= 0:
- return right_rotate(root)
- if balance > 1 and get_balance(root.left) < 0:
- root.left = left_rotate(root.left)
- return right_rotate(root)
- if balance < -1 and get_balance(root.right) <= 0:
- return left_rotate(root)
- if balance < -1 and get_balance(root.right) > 0:
- root.right = right_rotate(root.right)
- return left_rotate(root)
- return root
- def count_(node):
- global m
- if node is not None:
- m += 1
- count_(node.left)
- count_(node.right)
- return m
- with open('output.txt', 'w') as fr, open('input.txt', 'r') as fin:
- m = 0
- arr = list(map(int, fin.readline().split()))
- tree = Node(arr[0])
- if arr[0] != 0:
- for a in arr[1::]:
- if (a != 0):
- if (a > 0):
- tree = insert(tree, a)
- else:
- tree = delete_node(tree, -a)
- for _ in range(count_(tree)):
- minimal = (min_value_node(tree)).key
- if minimal > 0:
- fr.writelines(str(minimal)+ ' ')
- tree = delete_node(tree, minimal)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement