This patch drafts a new type "rbtree" implementing
Redblack Tree for collections module. It's just a
preliminary material for the future discussion and
includes a least working code.

Usage:

[basic list-like tree operations]

>>> from collections import rbtree
>>> r = rbtree()
>>> map(r.insert, [9, 3, 4, 100, 'dalki', 'subak', -51])
[None, None, None, None, None, None, None]
>>> r.values()
[-51, 3, 4, 9, 100, 'dalki', 'subak']
>>> r.remove(100)
>>> r.values()
[-51, 3, 4, 9, 'dalki', 'subak']
>>> r.insert('snisni')
>>> r.values()
[-51, 3, 4, 9, 'dalki', 'snisni', 'subak']
>>> 9 in r
True
>>> 8 in r
False

[labeled nodes operations]

>>> r = rbtree()
>>> r['dalki'] = 5; r['subak'] = 1; r['spam'] = 7
>>> r.values()
[1, 5, 7]
>>> r.keys()
['subak', 'dalki', 'spam']
>>> r['egg'] = 1
>>> r.items()
[('egg', 1), ('dalki', 5), ('spam', 7)]
>>> del r['spam']
>>> r.items()
[('egg', 1), ('dalki', 5)]

[mixed altogether]

>>> r.insert(7)
>>> r.insert(0)
>>> r.items()
[(None, 0), ('egg', 1), ('dalki', 5), (None, 7)]
>>> r['dalki'] = 7
>>> r.items()
[(None, 0), ('egg', 1), ('dalki', 7)]

[heapq-like stuff]

>>> r = rbtree()
>>> map(r.insert, range(20))
[None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None,
None, None]
>>> r.nfirst(3)
[0, 1, 2]
>>> r.nfirst(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> r.nlast(5)
[19, 18, 17, 16, 15]
>>> r.popleft(5)
[0, 1, 2, 3, 4]
>>> r.values()
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> r.popright(15)
[19, 18, 17, 16]
>>> r.values()
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> r['ham'] = 14
>>> r.poprightitems(14, True)
[(None, 15), ('ham', 14)]

[cmp, key and reverse are also supported]

>>> r = rbtree(key=lambda x: x%10)
>>> map(r.insert, range(30))
[None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None,
None, None, None, None, None, None, None, None, None,
None, None, None]
>>> r.values()
[20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
>>> r['yay'] = 78
>>> r.values()
[20, 21, 22, 23, 24, 25, 26, 27, 78, 29]
>>> r.items()
[(None, 20), (None, 21), (None, 22), (None, 23), (None,
24), (None, 25), (None, 26), (None, 27), ('yay', 78),
(None, 29)]
>>> r.clear()
>>> r.values()
[]
>>> r = rbtree(reverse=True)
>>> map(r.insert, range(10))
[None, None, None, None, None, None, None, None, None,
None]
>>> r.values()
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Logged In: YES 
user_id=55188

Added a unittest and fixed a bug on initcollection() calling
PyType_Ready(&rbtree_type).

Logged In: YES 
user_id=55188

Added iterator and reverse iterator implementations and
__copy__ method.

Logged In: YES 
user_id=55188

Updated the patch for the current svn.

Logged In: YES 
user_id=21627

This implementation gives me many questions:
- what is the rationale for keeping a separate keys
dictionary? If applications wanted that, couldn't they
maintain a key dictionary themselves? It just seems strange
to rely on hashing inside a rbtree implementation.
- Currently, you need two RichCompare invocations for
insertion/contains. Couldn't that be reduced to just one
comparison if __cmp__ is used?
- for key functions, wouldn't it usually be better to cache
the key?
- shouldn't tp_clear also be implemented?
- this entire code needs many more comments. For example,
why does the forward iterator first follow the right-most
links? I would have expected that it needs to start with the
leftmost node first (and somehow, it does - but why?)

I'm curious what the use case is for this.  It is not the purpose of the
collections module to implement all possible storage techniques
(b-trees, pairing heaps and whatnot).  What problem is being solved?

AFAICT, this offers a ordered dictionary style API without the
restriction of hashability, instead using the typically much more
expensive compare operation.  Also, the big-oh times degrade from O(1)
so that now we have O(log n) searches, insertions, and deletions.

I agree with Raymond.

In general, the collections module should define containers that are
named after their function rather than their implementation.  That way
the implementation can be changed at a later date (or in other Python
implementations) without causing confusion, and it makes it more obvious
what use-case the new collection is solving.  That's my opinion, anyway.

As much as I'd love to see more container types in the collections
module (my kingdom for a heap with .decrease_key()!), I don't see what
use-case this implementation of red-black trees fills.

Let's reject it then.