Question
(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
(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]
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started