This is an implementation of Scapegoat Trees.
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
- 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
You can download it here.
Want to store duplicates? Check out dupdict_mod.
See also this list of datastructures I've worked on.
Timestamp: 2024-02-29 11:26:14 PST
Back to Dan's tech tidbits
You can e-mail the author with questions or comments: