Advertisement
Guest User

Untitled

a guest
May 21st, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.71 KB | None | 0 0
  1. class Node():
  2. def __init__(self, d = 0):
  3. self.key = d
  4. self.height = 1
  5. self.left = None
  6. self.right = None
  7. def height(node):
  8. if node is None:
  9. return 0
  10. return node.height
  11.  
  12.  
  13. def right_rotate(node):
  14. x = node.left
  15. T2 = x.right
  16. x.right = node
  17. node.left = T2
  18. node.height = max(height(node.left), height(node.right)) + 1
  19. x.height = max(height(x.left), height(x.right)) + 1
  20.  
  21. return x
  22.  
  23. def left_rotate(node):
  24. y = node.right
  25. T2 = y.left
  26.  
  27. y.left = node
  28. node.right = T2
  29.  
  30. node.height = max(height(node.left), height(node.right)) + 1
  31. y.height = max(height(y.left), height(y.right)) + 1
  32.  
  33. return y
  34.  
  35. def get_balance(node):
  36. if node is None:
  37. return 0
  38. return height(node.left) - height(node.right)
  39.  
  40. def insert(node, key):
  41. global m
  42. if node is None:
  43. return Node(key)
  44.  
  45. if key < node.key:
  46. node.left = insert(node.left, key)
  47. elif key > node.key:
  48. node.right = insert(node.right, key)
  49. else:
  50. return node
  51. node.height = 1 + max(height(node.left), height(node.right))
  52. balance = get_balance(node)
  53.  
  54. if balance > 1 and key < node.left.key:
  55. return right_rotate(node)
  56. if balance < -1 and key > node.right.key:
  57. return left_rotate(node)
  58. if balance > 1 and key > node.left.key:
  59. node.left = left_rotate(node.left)
  60. return right_rotate(node)
  61. if balance < -1 and key < node.right.key:
  62. node.right = right_rotate(node.right)
  63. return left_rotate(node)
  64. return node
  65.  
  66. def min_value_node(node):
  67. current = node
  68.  
  69. while current.left is not None:
  70. current = current.left
  71.  
  72. return current
  73.  
  74. def delete_node(root, key):
  75. global m
  76. if root is None:
  77. return root
  78. if key < root.key:
  79. root.left = delete_node(root.left, key)
  80.  
  81. elif key > root.key:
  82. root.right = delete_node(root.right, key)
  83. else:
  84. if root.left is None or root.right is None:
  85. temp = None
  86. if temp == root.left:
  87. temp = root.right
  88. else:
  89. temp = root.left
  90. if temp is None:
  91. temp = root
  92. root = None
  93. else:
  94. root = temp
  95. else:
  96. temp = min_value_node(root.right)
  97. root.key = temp.key
  98. root.right = delete_node(root.right, temp.key)
  99.  
  100. if root is None:
  101. return root
  102.  
  103. root.height = max(height(root.left), height(root.right)) + 1
  104.  
  105. balance = get_balance(root)
  106.  
  107. if balance > 1 and get_balance(root.left) >= 0:
  108. return right_rotate(root)
  109.  
  110. if balance > 1 and get_balance(root.left) < 0:
  111. root.left = left_rotate(root.left)
  112. return right_rotate(root)
  113.  
  114. if balance < -1 and get_balance(root.right) <= 0:
  115. return left_rotate(root)
  116.  
  117. if balance < -1 and get_balance(root.right) > 0:
  118. root.right = right_rotate(root.right)
  119. return left_rotate(root)
  120. return root
  121. def count_(node):
  122. global m
  123. if node is not None:
  124. m += 1
  125. count_(node.left)
  126. count_(node.right)
  127. return m
  128.  
  129. with open('output.txt', 'w') as fr, open('input.txt', 'r') as fin:
  130. m = 0
  131. arr = list(map(int, fin.readline().split()))
  132. tree = Node(arr[0])
  133. if arr[0] != 0:
  134. for a in arr[1::]:
  135. if (a != 0):
  136. if (a > 0):
  137. tree = insert(tree, a)
  138. else:
  139. tree = delete_node(tree, -a)
  140. for _ in range(count_(tree)):
  141. minimal = (min_value_node(tree)).key
  142. if minimal > 0:
  143. fr.writelines(str(minimal)+ ' ')
  144. tree = delete_node(tree, minimal)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement