In this notebook you will 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.
If __setitem__
is called with an existing key, the method will simply locate the associated node and update its value with the newly provided value (as you would expect a mapping structure to do). If either __getitem__
or __delitem__
are called with a key that does not exist in the tree, a KeyError
should be raised.
The API described above will allow the tree to be used as follows:
t = BSTree()
t[0] = 'zero'
t[5] = 'five'
t[2] = 'two'
print(t[5])
t[5] = 'FIVE!!!'
for k,v in t.items():
print(k, '=', v)
del t[2]
print('length =', len(t))
The expected output of the above follows:
five
0 = zero
2 = two
5 = FIVE!!!
length = 2
The following BSTree
class contains an updated Node
, and stubs for the methods you are to implement. The first few simple test cases beneath the class definition should help clarify the required behavior.
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 += '\n'
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)
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)
from unittest import TestCase
tc = TestCase()
t = BSTree()
tc.assertEqual(len(t), 0)
t[0] = 'zero'
tc.assertEqual(t[0], 'zero')
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)
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])
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])
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])
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])
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]))
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]