Balanced trees

Steven D'Aprano steve+comp.lang.python at
Fri Mar 14 00:57:47 CET 2014

On Mon, 10 Mar 2014 19:34:48 +0200, Marko Rauhamaa wrote:

>> With a high level language like Python, using the provided hash table
>> will almost always cream any hand-built tree, no matter how
>> advantageous the data is to the tree.
> The main thing is there are use cases where order is essential. That's
> why I have had to implement the AVL tree in Python myself.

from collections import OrderedDict

gives you a fast, ordered mapping. In this case, the order is that of 
insertion order. If you want sort order instead, for "small" amounts of 
data, say below a million or ten million items, you're likely to have 
acceptable if not superior results by just sorting them items when and as 

Otherwise, I expect that following the basic technique of OrderedDict, 
and building your data structure from a dict and an associated list, 
keeping the two in sync, will be faster than a pure Python implementation 
of an AVL tree. But of course only testing it will make that clear.

Modifying the above recipe to keep items in something other than 
insertion order is left as an exercise.

Steven D'Aprano

More information about the Python-list mailing list