#2 repr(?) is very slow

[Nathan Hurst]

import avl

t = avl.new()
for i in range(2**16):
t.insert(i)

t

takes more than 10 seconds on a 2.4GHz machine

list(t)

'instant'

I think the problem is the infamous O(n^2) array concat problem with strings. The repr function works by concating each item's repr onto a string.

I don't have a patch, but there are two obvious solutions: a) convert to a list and return repr for that b) construct the string in bottom up order from the tree - concat reprs from neighbouring branches into a single string and move up the tree:

repr(node):
return repr(node.left) + "," + repr(node.right)