Guest User

Untitled

a guest
Oct 23rd, 2019
91
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Tree:
  2. def __init__(self, data=None, left=None, right=None):
  3. self.data = data
  4. self.left = left
  5. self.right = right
  6.  
  7. def size(self):
  8. size = 1
  9. size = size + self.left.size() if self.left is not None else size
  10. size = size + self.right.size() if self.right is not None else size
  11. return size
  12.  
  13. def merge(self, tree):
  14. if tree is None:
  15. return self
  16. if self.data <= tree.data:
  17. if self.right is None:
  18. return Tree(data=self.data, left=tree, right=self.left)
  19. return Tree(data=self.data, left=tree.merge(self.right), right=self.left)
  20. if tree.right is None:
  21. return Tree(data=tree.data, left=Tree(data=self.data, left=self.left, right=self.right), right=tree.left)
  22. return Tree(data=tree.data, left=self.merge(tree.right), right=tree.left)
  23.  
  24. def insert(self, data):
  25. self.__dict__ = self.merge(Tree(data, None, None)).__dict__.copy()
  26.  
  27. def popgen(self):
  28. while self.left is not None or self.right is not None:
  29. yield self.data
  30. if self.left is not None:
  31. self.__dict__ = self.left.merge(self.right).__dict__.copy()
  32. else:
  33. self.__dict__ = self.right.__dict__
  34. yield self.data
  35.  
  36. def to_list(self):
  37. return [x for x in self.popgen()]
  38.  
  39. @classmethod
  40. def from_list(cls, lst):
  41. if not lst:
  42. raise ValueError("cannot build a tree from an empty list")
  43. tree = Tree(lst[0], None, None)
  44. if len(lst) > 1:
  45. for e in lst[1:]:
  46. tree.insert(e)
  47. return tree
  48.  
  49.  
  50. def sort(lst):
  51. return Tree.from_list(lst).to_list()
  52.  
  53.  
  54. if __name__ == '__main__':
  55. import random
  56. before = [random.randint(1, 100) for _ in range(10)]
  57. after = sort(before)
  58. print('unsorted: ', before)
  59. print('sorted: ', after)
  60. print('native: ', sorted(before))
  61. assert after == sorted(before)
RAW Paste Data