This page presents a basic binary tree module, modified to work as a dictionary. It's also been modified to pass pylint, work on Python 2.x and 3.x (including PyPy and Jython), and has good automated tests.

If the keys you want to store are in random order, this is a very good choice of datastructure for O(log2(n)) lookups including find_min and find_max. However, if your keys are ordered, this is probably not a good datastructure for you (however, sometimes you can do an O(n) shuffle before storing things in a binary tree, to get a random order from ordered).

Want to store duplicates? Check out dupdict_mod.

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

You can download it from here.

Hits: 3932
Timestamp: 2024-11-21 15:03:30 PST

Back to Dan's tech tidbits

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