SHARE
TWEET

Untitled

a guest Feb 21st, 2020 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. Name: Maggie Yu
  3. PennKey: 19438439
  4. Hours of work required: 5
  5. '''
  6.  
  7. '''
  8. In all functions below, the keyword "pass" is used to
  9. indicate to the interpreter that the corresponding codeblock
  10. is empty. This is necessary in order for the interpreter
  11. not to consider empty code blocks as syntax errors.
  12. You will replace each of these "pass" keywords by your
  13. code completing the function as described in the comments.
  14. '''
  15.  
  16.  
  17. class Node:
  18.     def __init__(self, key):
  19.         '''
  20.         Construct an instance of the Node class
  21.         args:
  22.             key: the key for the node
  23.         args: None
  24.         '''
  25.         self.num = key
  26.         self.l_child = None
  27.         self.r_child = None
  28.  
  29. class BST:
  30.     def __init__(self):
  31.         '''
  32.         Construct an instance of the BST class
  33.         args: None
  34.         Note: the BST should be initially empty
  35.         '''
  36.         self.root = None
  37.         self.size = 0
  38.  
  39.     def isempty(self):
  40.         '''
  41.         Whether the tree is empty
  42.         args: None
  43.         ret:
  44.             True if the tree is empty, False otherwise
  45.         '''
  46.         if self.size == 0: return True
  47.         else: return False
  48.  
  49.     def add(self, key):
  50.         '''
  51.         Add a node to the BST with a given key
  52.         args:
  53.             key: the key to insert in the BST
  54.         ret: None
  55.  
  56.         Notes: if the key is already in the BST, you
  57.         must silently ignore it (i.e., without raising
  58.         an exception). If you are interested, you may
  59.         want to look into issuing a warning.
  60.         '''
  61.         self.ip = Node(key)
  62.         if self.size == 0:
  63.             self.root = self.ip
  64.         else:
  65.             add_helper(self.root, self.ip)
  66.         self.size = self.size + 1
  67.  
  68.  
  69.     def delete(self, key):
  70.         '''
  71.         Remove the node with a matching key from the BST
  72.         args:
  73.             key: the key to delete
  74.         ret: None
  75.  
  76.         Notes: if the key is not present in the BST, you
  77.         must raise a ValueError exception with a descriptive
  78.         message.
  79.         '''
  80.         l = list(self)
  81.         if key in l:
  82.             og = del_helper_find(self.root, self.root, key, l)
  83.             og = del_helper(self.root, self.root, key, l)
  84.         else:
  85.             raise ValueError()
  86.         self.size = self.size - 1
  87.         return og
  88.  
  89.     def __iter__(self):
  90.         '''
  91.         A generator for iterating over the values of the key
  92.         args: None
  93.         Note: You should use a combination of yield and yield
  94.         from in order to iterate over the tree.
  95.         '''
  96.         yield from iter_helper(self.root.l_child)
  97.         yield self.root.num
  98.         yield from iter_helper(self.root.r_child)
  99.    
  100.  
  101.     def __contains__(self, key):
  102.         '''
  103.         Whether the given key is in the BST
  104.         args:
  105.             key: the key to search for
  106.         ret:
  107.             True if the key is in the BST, false otherwise
  108.         '''
  109.         pass
  110.  
  111.     def __len__(self):
  112.         '''
  113.         The number of elements in the BST
  114.         args: None
  115.         ret:
  116.             The number of elements in the BST
  117.  
  118.         Note: you should avoid traversing the BST in this function
  119.         '''
  120.         return self.size
  121.  
  122.  
  123. def add_helper(node, new_node):
  124.     if new_node.num > node.num:
  125.         if node.r_child == None:
  126.             node.r_child = new_node
  127.         else:
  128.             add_helper(node.r_child, new_node)
  129.  
  130.     elif new_node.num < node.num:
  131.         if node.l_child == None:
  132.             node.l_child = new_node
  133.         else:
  134.             add_helper(node.l_child, new_node)
  135.  
  136. def del_helper_find(base, root, del_num, node_list):
  137.     if root.num == del_num:
  138.         return root
  139.     elif root.num > del_num:
  140.         del_helper_find(base, root.r_child, del_num, node_list)
  141.     elif root.num < del_num:
  142.         del_helper_find(base, root.l_child, del_num, node_list)
  143.             # del_shift(node)
  144.  
  145. def del_helper(base, root, del_node, node_list):
  146.     if root.l_child == None and root.r_child == None:
  147.         root = None
  148.     elif root.l_child == None:
  149.         root = root.r_child
  150.         return root
  151.     elif root.r_child == None:
  152.         root = root.l_child
  153.     else:
  154.         a = node_list.index(del_node.num)
  155.         b = node_list[a+1]
  156.         del_helper_find(base, base, b, node_list)
  157.  
  158.  
  159.  
  160. def iter_helper(node):
  161.     if node != None:
  162.         yield from iter_helper(node.l_child)
  163.         yield node.num
  164.         yield from iter_helper(node.r_child)
  165.  
  166.  
  167.  
  168.    
  169.  
  170.  
  171.  
  172.  
  173. def main():
  174.     '''
  175.     Use this for testing! Make sure to be thorough and test for
  176.     corner cases. There are many corner cases to look out for
  177.     when working with trees!
  178.     '''
  179.     my_tree = BST()
  180.     my_tree.add(1)
  181.     print(my_tree)
  182.     my_tree.add(10)
  183.     my_tree.add(2)
  184.     my_tree.add(3)
  185.     my_tree.add(4)
  186.     my_tree.add(999)
  187.     my_tree.delete(1)
  188.     print(list(my_tree))
  189.     # for elem in my_tree:
  190.         # assert elem in my_tree
  191.     # print(iter(my_tree.root))
  192.     l = iter(my_tree)
  193.     print(next(l))
  194.     print(next(l))
  195.    
  196. if __name__ == '__main__':
  197.     '''
  198.     This calls the function main() when executing python3 hw3.py
  199.     '''
  200.     main()
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