[Python-Dev] collections.sortedtree

[Dan Stromberg]

On Wed, Mar 26, 2014 at 1:55 PM, Benjamin Peterson <benjamin at python.org> wrote:
> On Wed, Mar 26, 2014, at 13:31, Marko Rauhamaa wrote:
>>
>> I have made a full implementation of a balanced tree and would like to
>> know what the process is to have it considered for inclusion in Python
>> 3.
>
> It's not a bad idea. (I believe others have proposed an red-black tree.)
> Certainly, it requires a PEP and a few months of bikesheding, though.

I'd recommend a plain binary tree (for random keys), red-black tree
and treap (both for ordered or mostly-ordered keys, where red-black
tree gives low operation duration standard deviation, and treap gives
low average operation duration).

https://en.wikipedia.org/wiki/Binary_search_tree#Performance_comparisons
http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

It'd likely make sense to have either a pure python implementation, or
pure python and C-extended, so that Pypy and Jython can share the
feature with CPython.