# binary tree in python?

Darrell Gallion darrell at dorb.com
Wed Nov 8 03:31:52 CET 2000

```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()

```