(Please help me with this with coding in python3)

BSTree

Modify the binary search tree implementation completed in class so that it can be used as a mapping structure. The Node class will be updated so as to hold separate key and value attributes (instead of a single value, as it currently does), and instead of the add method, you should implement the __getitem__ and __setitem__ methods in order to associate keys and values. __delitem__, __contains__, and __iter__ will also need to be updated, to perform key-based removal, search, and iteration. Finally, the keys, values, and items methods will return iterators that allow the keys, values, and key/value tuples of the tree (all sorted in order of their associated keys) to be traversed.

class BSTree: class Node: def __init__(self, key, val, left=None, right=None): self.key = key self.val = val self.left = left self.right = right def __init__(self): self.size = 0 self.root = None def __getitem__(self, key): # YOUR CODE HERE raise NotImplementedError() def __setitem__(self, key, val): # YOUR CODE HERE raise NotImplementedError() def __delitem__(self, key): # YOUR CODE HERE raise NotImplementedError() def __contains__(self, key): # YOUR CODE HERE raise NotImplementedError() def __len__(self): return self.size def __iter__(self): # YOUR CODE HERE raise NotImplementedError() def keys(self): # YOUR CODE HERE raise NotImplementedError()

def values(self): # YOUR CODE HERE raise NotImplementedError()

def items(self): # YOUR CODE HERE raise NotImplementedError() def pprint(self, width=64): """Attempts to pretty-print this tree's contents.""" height = self.height() nodes = [(self.root, 0)] prev_level = 0 repr_str = '' while nodes: n,level = nodes.pop(0) if prev_level != level: prev_level = level repr_str += ' ' if not n: if level < height-1: nodes.extend([(None, level+1), (None, level+1)]) repr_str += '{val:^{width}}'.format(val='-', width=width//2**level) elif n: if n.left or level < height-1: nodes.append((n.left, level+1)) if n.right or level < height-1: nodes.append((n.right, level+1)) repr_str += '{val:^{width}}'.format(val=n.key, width=width//2**level) print(repr_str) def height(self): """Returns the height of the longest branch of the tree.""" def height_rec(t): if not t: return 0 else: return max(1+height_rec(t.left), 1+height_rec(t.right)) return height_rec(self.root)

# 2 points

from unittest import TestCase

tc = TestCase() t = BSTree() tc.assertEqual(len(t), 0) tc.assertFalse(0 in t) t[0] = 'zero' tc.assertTrue(0 in t) tc.assertEqual(len(t), 1)

# 2 points

from unittest import TestCase

tc = TestCase() t = BSTree() tc.assertEqual(len(t), 0) t[0] = 'zero' tc.assertEqual(t[0], 'zero')

# 2 points

from unittest import TestCase

tc = TestCase() t = BSTree() tc.assertEqual(len(t), 0) t[0] = 'zero' del t[0] tc.assertFalse(0 in t) tc.assertEqual(len(t), 0)

# 2 points

from unittest import TestCase

tc = TestCase() t = BSTree() key_vals = [(0, 'zero'), (2, 'two'), (1, 'one')] sorted_key_vals = sorted(key_vals)

for k,v in key_vals: t[k] = v

for i,k in enumerate(t.keys()): tc.assertEqual(k, sorted_key_vals[i][0])

# 1 point

from unittest import TestCase

tc = TestCase() t = BSTree() key_vals = [(0, 'zero'), (2, 'two'), (1, 'one')] sorted_key_vals = sorted(key_vals)

for k,v in key_vals: t[k] = v

for i,v in enumerate(t.values()): tc.assertEqual(v, sorted_key_vals[i][1])

# 1 point

from unittest import TestCase

tc = TestCase() t = BSTree() key_vals = [(0, 'zero'), (2, 'two'), (1, 'one')] sorted_key_vals = sorted(key_vals)

for k,v in key_vals: t[k] = v

for i,(k,v) in enumerate(t.items()): tc.assertEqual(k, sorted_key_vals[i][0]) tc.assertEqual(v, sorted_key_vals[i][1])

# 5 points

from unittest import TestCase import random

tc = TestCase() t = BSTree() keys = list(range(100, 1000, 11)) random.shuffle(keys) vals = [random.randrange(1000) for _ in range(100, 1000, 11)]

for i in range(len(keys)): t[keys[i]] = vals[i]

for i in range(len(keys)): tc.assertEqual(t[keys[i]], vals[i])

# 5 points

from unittest import TestCase import random

tc = TestCase() t = BSTree() keys = list(range(100, 1000, 11)) shuffled_keys = keys.copy() random.shuffle(shuffled_keys)

for k in shuffled_keys: t[k] = str(k)

for i,k in enumerate(t.keys()): tc.assertEqual(k, keys[i])

for i,v in enumerate(t.values()): tc.assertEqual(v, str(keys[i]))

for i,(k,v) in enumerate(t.items()): tc.assertEqual(k, keys[i]) tc.assertEqual(v, str(keys[i]))

# 5 points

from unittest import TestCase import random

tc = TestCase() t = BSTree() keys = list(range(0, 100, 2)) random.shuffle(keys)

for x in keys: t[x] = x*2

for k in range(1, 101, 2): with tc.assertRaises(KeyError): v = t[k]