working on a tree list

tree.py

from itertools import repeat
 
class Tree(object):
    def __init__(self):
        self.tree = []
        self.balance = bytearray('')
 
    def insert(self, item):
        i = self._get_index(item)
        if i >= len(self.tree):
            self.tree.extend(repeat(_EMPTY, i+1 - len(self.tree)))
            self.balance.extend(repeat('0', i+1 - len(self.tree)))
        self.tree[i] = item #tree[i] is not guaranteed to be _EMPTY
 
    def delete(self, item):
        i = self._get_index(item)
        if self.tree[i] != item:
            i = (i-1)/2  #parent
            if self.tree[i] != item:
                raise ValueError("item "+repr(item)+" not in TreeList")
            self._remove(i)
        self._remove(i)
 
    def _get_index(self, item):
        tree = self.tree
        treelen = len(tree)
        i = 0
        while i < treelen:
            if tree[i] is _EMPTY:
                break
            cur = tree[i]
            if item <= cur:
                i = 2*i+1 #left
            else:
                i = 2*i+2 #right
        return i
 
    def _remove(self, i):
        tree = self.tree
        treelen = len(self.tree)
        nxt = i*2+1
        while nxt < treelen:
            tree[i] = tree[nxt]
            if tree[i] is _EMPTY:
                return
            i = nxt
            nxt = i*2+1
 
    def __iter__(self):
        tree = self.tree
        treelen = len(self.tree)
        stack = []
        cur = 0
        cur_valid = cur < treelen and tree[cur] is not _EMPTY
        while stack or cur_valid:
            if cur_valid:
                stack.append(cur)
                cur = cur*2+1 #left
                cur_valid = cur < treelen and tree[cur] is not _EMPTY
            else:
                cur = stack.pop()
                yield tree[cur]
                cur = cur*2+2 #right
                cur_valid = cur < treelen and tree[cur] is not _EMPTY
 
class empty(object):
    def __repr__(self): return "{0}"

_EMPTY = empty()

def test():
    tree = Tree()
    for i in range(10):
        tree.insert(i)
    assert list(range(10)) == list(tree)
    tree2 = Tree()
    data = [65, 23, 11, 655, 3, 1, 7, 11]
    for d in data:
        tree2.insert(d)
    assert list(tree2) == sorted(data)
    return tree