Simple example of ranged binary tree in Python, able to perform slice retrieval

simpletree.py

# coding: utf-8

class EmptyClass(object):
    def __repr__(self):
        return ""

Empty = EmptyClass()

class Node(object):
    def __init__(self, value, key=None):
        self.left = Empty
        self.right = Empty
        self.value = value
        if key is None:
            self.key = lambda x:x
        else:
            self.key = key

    def insert(self, new_value):
        if self.key(new_value) < self.key(self.value):
            self._inner_insert(new_value, self.left, "left")
        else:
            self._inner_insert(new_value, self.right, "right")

    def _inner_insert(self, new_value, branch_value, branch_name):
        if branch_value is Empty:
            setattr(self, branch_name, new_value)
        elif isinstance(branch_value, Node):
            branch_value.insert(new_value)
        else:
            new_branch = Node(branch_value, self.key)
            new_branch.insert(new_value)
            setattr(self, branch_name, new_branch)

    def __lshift__(self, value):
        self.insert(value)

    def __repr__(self):
        return " ".join((repr(self.left), repr(self.value), repr(self.right)))

    def __getitem__(self, value):
        if isinstance(value, slice):
            return self._getslice(value)
        return self._getitem_and_next(value)[0]

    def _getitem_and_next(self, value):
        keyed = self.key(value)
        if keyed == self.key(self.value):
            return value, self.closer_right()
        if keyed < self.key(self.value):
            if isinstance(self.left, Node):
                if keyed > self.left.key(self.left.value):
                    return self.value, self.closer_right()
                result = self.left._getitem_and_next(value)
                if result[1] is Empty:
                    return result[0], self.value
                return result
            if self.left is Empty:
                return self.value, self.closer_right()
            if keyed <= self.key(self.left):
                return self.left, self.value
            return self.value, self.closer_right()
        else:
            if isinstance(self.right, Node):
                return self.right._getitem_and_next(value)
            if self.right is Empty:
                raise ValueError("No value less or equal %s" % value)
            return self.right

    def closer_right(self):
        if isinstance(self.right, Node):
            return self.right.leftmost()
        return self.right

    def leftmost(self):
        if isinstance(self.left, Node):
            return self.left.leftmost()
        if self.left is Empty:
            return self.value
        return self.left

    def _getslice(self, value):
        return list(self.iterslice(value.start, value.stop))

    def iterslice(self, start, stop):
        result, next_ = self._getitem_and_next(start)
        keyed_stop = self.key(stop)
        while result is not Empty and self.key(result) < keyed_stop:
            yield result
            result, next_ = self._getitem_and_next(next_)
        raise StopIteration

>>> b  = simpletree.Node("fnord")
>>> b << "dalmata"; b << "castelo"; b << "elefante"; b << "amarelo"; b << "pizza"; b << "gelo"; b<<"zebra"
>>> b
'amarelo' 'castelo'  'dalmata' 'elefante' 'fnord' 'gelo' 'pizza' 'zebra'
>>> b["a"]
'amarelo'
>>> b["a":"g"]
['amarelo', 'castelo', 'dalmata', 'fnord']

This version is really b0rk for some cases - I fixed it, but added more features and it is no longer that "simple" for a gist. Write me if you need the better version. Although this i s not a complete binary-tree project: there is no node removal or any kind of tree balancing.