SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 76 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top