This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author hyeshik.chang
Recipients
Date 2005-10-12.11:58:27
SpamBayes Score
Marked as misclassified
Message-id
In-reply-to
Content
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]
History
Date User Action Args
2007-08-23 15:44:13adminlinkissue1324770 messages
2007-08-23 15:44:13admincreate