I've been attempting to create a treemap (binary search tree) insertion and display function for a bit and am puzzled by the recursive calls. I've tried quite a few things, but the problem seems to be in my mapInsert function. Here's all the code I've written so far in python3:
class EmptyMap(): """represents an empty map""" __slots__ = () class NonEmptyMap(): """represents a non empty map""" __slots__ = ('left', 'key', 'value', 'right') def mkEmptyMap(): """Constructor: mkEmptyMap() --> EmptyMap""" return EmptyMap() def mkNonEmptyMap (a, b, c, d): """constructor: mkNonEmptyMap: maptree * key * value * maptree""" node = NonEmptyMap() node.left = a node.key = b node.value = c node.right = d return node def mapInsert (key, value, map_instance): """takes parameters and returns instance of treeMap of NonEmptyMap objects""" if isinstance (map_instance, EmptyMap): #print ('1 empty created') #debug return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap()) elif isinstance (map_instance, NonEmptyMap): #problems start here #print (map_instance.left) #print (map_instance.right) #print(key < map_instance.key) if map_instance.key > key: #print('map_instance key greater than key') # recursively insert the given key on the left of the map_instance return mapInsert(key, value, mkNonEmptyMap(EmptyMap, map_instance.key, map_instance.value, map_instance.left)) elif map_instance.key < key: return mapInsert(key, value, mkNonEmptyMap(EmptyMap, map_instance.key, map_instance.value, map_instance.right)) elif map_instance.key == key: raise TypeError ('mapInsert: duplicate keys given') else: raise TypeError ('mapInsert: non map given for map_instance') return
When I run this code, the recursion goes on forever. I'd appreciate any help -- this is a class assignment that I've been struggling with for hours. My questions are: (0) what am I doing wrong in terms of the recursive insertion call and (1) anything else you see that I've missed in the way I've set it up (improperly) would help.
Thanks in advance for taking the time to help me out.