Scapegoat trees are interesting mostly because they:
Don't require any accounting overhead to keep a tree balanced
Are parameterized in such a way as to spend more or less time
balancing. The constant accepted is reputed to be between
0.5 and 1, however I found that between 0.6 and 0.9 was more
like it.
Are apparently rather poor at storing ordered keys, but can be quite good
at random or mostly random keys.
This implementation is derived from Matt Johnson's. I've
modified it to pass pylint; work on Python 2.x and 3.x (including PyPy and Jython); and to be thoroughly, automatically
tested.
