Python 3.x

Starter File:

# Implements the Table ADT # # Data structure: # a table is a object containing two atributes: # 'root' - value stores the root of a primitive binary tree # 'size' - value stores the number of nodes in the primitive binary tree # The methods ensure that the primitive binary tree satisfies the # binary search tree property import a9q2 as prim class Table(object): def __init__(self): self.__root = None self.__size = 0 def size(self): """  Purpose:  Return the size of the table.  Return:  :return: the number of key,value pairs in the table  """  return 0 def is_empty(self): """  Purpose:  Indicate whether the given table is empty.  Return:  :return: True if the table is empty  """  return False def retrieve(self, key): """  Return the value associated with the given key.  Preconditions:  :param key: a key  Postconditions:  none  Return  :return: True, value if the key appears in the table  False, None otherwise  """  return False, None def insert(self, key, value): """  Insert a new key, value into the table.  Preconditions:  :param key: a unique key for the value  :param value: a value  Postconditions:  If the key is not already in the table, it is added to the table  If the key is already there, change the value  Return  :return: True if the key,value was inserted  False if the value of an existing key was changed  """  return False def delete(self, key): """  Delete a given key and its associated value from the table.  Preconditions:  :param key: a unique key for the value  Postconditions:  If the key is not in the table, no change to the table  If the key is in the table, remove it  Return  :return: True if the key,value was deleted  """  return False def in_order(self): """  Returns a string of the keys showing the in-order sequence  """   def in_order_prim(kvtnode): if kvtnode is None: return " " else: before = in_order_prim(kvtnode.left) this = '('+str(kvtnode.key)+','+str(kvtnode.value)+')' after = in_order_prim(kvtnode.right) return before + this + after return in_order_prim(self.__root) 

a9q2.py:

import KVTreeNode as TN def member_prim(tnode, key): """  Purpose:  Check if value is stored in the binary search tree.  Preconditions:  :param tnode: a KVTreeNode with the BST property  :param key: a key  Postconditions:  none  :return: a pair True, value if key is in the tree  a pair False, None if the key is not in the tree  """  if tnode is None: return False, None elif tnode.key is key: return True, tnode.value elif key """  Insert a new key,value into the binary search tree.  Preconditions:  :param tnode: a KVTreeNode with the BST property  :param key: a key  Postconditions:  If the key is not already in the tree, it is added.  If the key is already in the tree, the old value is replaced  with the given value.  Return  :return: tuple (flag, tree)  flag is True if insertion succeeded;  tree contains the new key-value  flag is False if the value is already in the tree,  the value stored with the key is changed  """   if tnode is None: return True, TN.KVTreeNode(key, value) else: if tnode.key is key: tnode.value = value return False, tnode elif key """  Delete a value from the binary search tree.  Preconditions:  :param tnode: a KVTreeNode with the BST property  :param key: a key  Postconditions:  If the key is in the tree, it is deleted. The tree  retains the binary search tree property.  If the key is not there, there is no change to the tree.  Return  :return: tuple (flag, tree)  flag is True if deletion succeeded;  tree is the resulting without the value  flag is False if the value was not in the tree,  tree returned unchanged  """   def delete(tnode): if tnode is None: return False, tnode else: cval = tnode.key if cval == key: return reconnect(tnode) elif key  
 
 
Other Code that you may need
 
KVTtreenode.py:
 
# A KVTreeNode is a simple container with four pieces of # information: # key: the key for the node # value: the contained information # left: a reference to another KVTreeNode, or None # right: a reference to another KVTreeNode, or None # Implementation notes: # This ADT implementation uses a Python class class KVTreeNode(object): def __init__(self, key, value, left=None, right=None): """  Create a new KVTreeNode for the given data.  Pre-conditions:  key: A key used to identify the node  value: Any data value to be stored in the KVTreeNode  left: Another KVTreeNode (or None, by default)  right: Another KVTreeNode (or None, by default)  """  self.value = value self.left = left self.right = right self.key = key 
 
bstprism.py:
 
import TreeNode as TN def member_prim(tnode, target): """  Purpose:  Check if value is stored in the binary search tree.  Preconditions:  :param tnode: a binary search tree  :param target: a value  Postconditions:  none  :return: True if value is in the tree  """  if tnode is None: return False elif tnode.data is target: return True elif target """  Insert a new value into the binary search tree.  Preconditions:  :param tnode: a TreeNode with the BST property  :param value: a value  Postconditions:  If the value is not already in the tree, it is added  Return  :return: tuple (flag, tree)  flag is True if insertion succeeded;  tree contains the new value  flag is False if the value is already in the tree,  tree unchanged  """   if tnode is None: return True, TN.TreeNode(value) else: if tnode.data is value: return False, tnode elif value """  Delete a value from the binary search tree.  Preconditions:  :param tnode: a TreeNode with the BST property  :param target: a value  Postconditions:  If the value is in the tree, it is deleted.  If the value is not there, there is no change to the tree.  Return  :return: tuple (flag, tree)  flag is True if deletion succeeded;  tree is the resulting without the value  flag is False if the value was not in the tree,  tree returned unchanged  """  def delete(tnode): if tnode is None: return False, tnode else: cval = tnode.data if cval == target: return reconnect(tnode) elif target  
Treenode.py:
 
class TreeNode(object): def __init__(self, data, left=None, right=None): """  Create a new treenode for the given data.  Pre-conditions:  data: Any data value to be stored in the treenode  left, right: Another treenode (or None, by default)  Post-condition:  none  """  self.data = data self.left = left self.right = right 
  Question 3 (6 points): Purpose: To implement the Table ADT, as described in class. Degree of Difficulty: Should be Easy In this question, you'll implement the full Table class, as we discussed in class. The Table class has the following methods: size0 Returns the number of key-value pairs in the Table. is empty) Returns True if the Table t is empty, False otherwise. insert(k.v) Stores the value v with the key k in the Table. If the key k is already in the Table, the value v replaces any value already stored for that key given key: otherwise return the tuple False, None. ?f the key k is not in the Table. retrievelk) If the key k is in the Table, return a tuple True, value, where value is the value stored with the delete(k) If the key k is in the Table, delete the key-value pair from the table and return True, return False A starter file has been provided for you, which you can find on Moodle named a9q3.py. The-init- method is already implemented for you, and all of the others have an interface and a trivial do-nothing To complete this question, you should import a9q2 your solution to Question 2 into the Table ADT. Your Table methods can call the primitive BST functions. Your Table methods may have to do a few house- keepingitems (such as change the size attribute when inserting or deleting), but most of the work is done by your solution to Question 2. List of files on Moodle for this question a9q3.py partially completed a9q3score.py - A script that will help you check your progress on a9q3.py