binary tree in python?

[Darrell Gallion]

From: "Hrvoje Niksic" 
> 
> Here is a nice binary tree implementation by Tim Peters.  You can save
> it to a file named `bintree.py' and do things like:
> 

Took your code and twisted it into something like a B+ tree for fun.

--Darrell

import bisect, random

class TreeBplus:
    def __init__(self, maxNodeSz):
        root='root'
        self._dict={root:[]}
        self._root= root
        self._maxNodeSz=maxNodeSz

    def insert(self, val):
        root = self._root
        lastRoot= root
        while root != None:
            rootList= self._dict[root]
            if len(rootList) < self._maxNodeSz:
                bisect.insort (rootList, val)
                return
            else:
                x=bisect.bisect(rootList, val)
                if x == len(rootList):
                    # Move the last element in rootList
                    # out to another node to make room
                    a=rootList[-1]
                    rootList[-1]=val
                    valA=self._dict.get(a,None)
                    if valA:
                        self._dict[val]=valA
                        del self._dict[a]
                    self.insert(a)
                    return
                else:
                    root=rootList[x]
                    self._dict.setdefault(root, [])

    def inorder(self):
        result = []
        self.__helper(self._dict[self._root], result)
        return result

    def __helper(self, rootList, result):
        for r in rootList:
            if r != self._root and self._dict.has_key(r):
                self.__helper(self._dict[r], result)
            result.append(r)

def test():
    data=range(200)
    dataOrig=data[:]
    random.shuffle(data)
    tree=TreeBplus(5)
    for d in data:
           tree.insert(d)

    print 'Root:', tree._root
    import pprint
    pprint.pprint(tree._dict)
    print '*'*50
    sorted=tree.inorder()
    assert(sorted==dataOrig)
    print '='*50

for x in range(3):
    test()