red black tree implementation in Python

This is a Python 2 and Python 3 implementation (tested on CPython, Pypy and Jython) of Red-Black Trees.

It passes pylint, so the code probably isn't too awful.

Most of this code was written by Duncan Smith; I (Dan Stromberg) just put some finishing touches on it.

It supports set and dictionary use.

Also included is a basic Binary Tree, from which the Red Black Trees inherit.

Example use:

$ python3
below cmd output started 2022 Wed Nov 30 07:54:41 PM PST
Python 3.7.3 (default, Oct 31 2022, 14:04:00) 
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import red_black_dict_mod
>>> rbd = red_black_dict_mod.RedBlackTree()
>>> for i in range(30, -1, -1):
...     rbd[i] = 2**i
... 
>>> list(rbd.items())
[(0, 1), (1, 2), (2, 4), (3, 8), (4, 16), (5, 32), (6, 64), (7, 128), (8, 256), (9, 512), (10, 1024), (11, 2048), (12, 4096), (13, 8192), (14, 16384), (15, 32768), (16, 65536), (17, 131072), (18, 262144), (19, 524288), (20, 1048576), (21, 2097152), (22, 4194304), (23, 8388608), (24, 16777216), (25, 33554432), (26, 67108864), (27, 134217728), (28, 268435456), (29, 536870912), (30, 1073741824)]
>>> 
>>> import red_black_set_mod
>>> rbs = red_black_set_mod.RedBlackTree()
>>> for i in range(30, -1, -1):
...      rbs.add(i)
... 
30 blk
29 red
28 red
27 red
26 red
25 red
24 red
23 red
22 red
21 red
20 red
19 red
18 red
17 red
16 red
15 red
14 red
13 red
12 red
11 red
10 red
9 red
8 red
7 red
6 red
5 red
4 red
3 red
2 red
1 red
0 red
>>> list(rbs)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
>>>

Looking to store duplicates in a red-black tree? See dupdict_mod.

Hits: 12746
Timestamp: 2024-11-21 15:10:35 PST

Back to Dan's tech tidbits

You can e-mail the author with questions or comments: