This is an implementation of Scapegoat Trees.

Scapegoat trees are interesting mostly because they:

  1. Don't require any accounting overhead to keep a tree balanced
  2. 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.
  3. 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.

You can download it here.

Want to store duplicates? Check out dupdict_mod.

See also this list of datastructures I've worked on.


Hits: 3495
Timestamp: 2024-11-10 08:02:56 PST

Back to Dan's tech tidbits

You can e-mail the author with questions or comments: