Balanced trees

[Steven D'Aprano]

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 
needed.

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.

http://code.activestate.com/recipes/576693-ordered-dictionary-for-py24/

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




-- 
Steven D'Aprano
http://import-that.dreamwidth.org/