On Wed, Mar 26, 2014 at 1:55 PM, Benjamin Peterson <benja...@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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
