A Tree-based Map in Python

Question

mapSearch is a function that takes a key and a map, and returns the value associated with the key or None if the key is not there then return None.

Question: When I run the search function, it keeps returning the same value no matter what I put in for the key.

class EmptyMap():
    __slots__ = ()


class NonEmptyMap():
    __slots__ = ('left', 'key', 'value', 'right')

EMPTY_MAP = EmptyMap()

def mkEmptyMap():
    return EMPTY_MAP

def mkNonEmptyMap(b1, key, value, b2):
    node = NonEmptyMap()
    node.left = b1;
    node.key = key;
    node.value = value;
    node.right = b2;
    return node;

def mapInsert(key, value, mp):

if isinstance(mp, EmptyMap):
    return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())

else:
    if key == mp.key:
        mp.value = value
    elif mp.key < key:
        mp.left = mapInsert(key, value, mp.left)
    else:
        mp.right = mapInsert(key, value, mp.right)

    return mp

def search(key, mp):
    if isinstance(mp, EmptyMap):
        return None
    elif isinstance(mp, NonEmptyMap):
        if key == mp.key:
            return mp.value
        elif mp.key < key:
            mp.left = search(key, mp.left)
            return mp.value
        else:
            mp.right = search(key, mp.right)
            return mp.value

Answer 1

I'm pretty sure the issue you're encountering is simply that you're not getting the return value you expect from mapInsert. The current code always returns the node that the provided value was inserted in, even if that is a leaf node somewhere deep in your tree. (And actually, not that I look closely at it there are some additional bugs with what you're recursing on and returning.)

I think you should change your return statements in the else block of mapInsert to return mp, rather than the result of the recursive call. The result of the call should be assigned to mp.left or mp.right, depending on which side we recursed on.

def mapInsert(key, value, mp):

    if isinstance(mp, EmptyMap):
        return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())

    else:
        if key == mp.key:
            mp.value = value
        elif mp.key < key:
            mp.left = mapInsert(key, value, mp.left) # don't return recursive result
        else:
            mp.right = mapInsert(key, value, mp.right) # pass the right child here!

        return mp # always return mp from this branch

Note that a more "Pythonic" design would probably use methods in a class, rather than a separate function to handle this kind of thing. This would require somewhat different handling of empty trees though.

Answer 2

One obvious issue:

    if key == mp.key:
        mp.value = value
    elif mp.key > key:
        return mapInsert(key, value, mp.left)
    else:
        return mapInsert(key, value, mp.left)

One of these doesn't return anything at all, the other two return the same thing.