Pls Help! Need binary search tree module

[Raymond Hettinger]

Steve Mak wrote:

> I was wondering if anyone had a simple binary search tree module I could
> use? I need to write a program that counts the number of occurrences of each
> word in a file, and outputs the word and corresponding counts
> alphabetically. And it is required that one of the data structure is a
> binary search tree.
>

Here's a list oriented, binary counting tree for you:

def add( n, elem ):
    if n == None:
        n = [ elem, 1, None, None ]
    elif n[0] == elem:
        n[1] += 1
    else:
        tgt = 2     # choose left side
        if elem > n[0]:
            tgt = 3 # choose right side
        n[tgt] = add( n[tgt], elem )
    return n

n = None
for w in "the man and the moon and the tree".split():
    n = add(n,w)
print n


Raymond