|
bgneal@4
|
1 A Red-Black Tree in Python
|
|
bgneal@4
|
2 ##########################
|
|
bgneal@4
|
3
|
|
bgneal@4
|
4 :date: 2012-12-28 11:10
|
|
bgneal@4
|
5 :tags: Python, datastructures
|
|
bgneal@4
|
6 :slug: a-red-black-tree-in-python
|
|
bgneal@4
|
7 :author: Brian Neal
|
|
bgneal@4
|
8
|
|
bgneal@4
|
9 I've been working my way through Allen Downey's `Think Complexity`_ book. I'm
|
|
bgneal@4
|
10 not very far in, but so far it's a great way to brush up on algorithms and
|
|
bgneal@4
|
11 datastructures, and learn some new stuff about complexity science. Plus, all of
|
|
bgneal@4
|
12 the code is written in Python! I've been doing the exercises, and most of them
|
|
bgneal@4
|
13 take at most fifteen or twenty minutes. But at the end of his explanation on
|
|
bgneal@4
|
14 hash tables he casually lobs this one out (3.4, exercise 5):
|
|
bgneal@4
|
15
|
|
bgneal@4
|
16 A drawback of hashtables is that the elements have to be hashable, which
|
|
bgneal@4
|
17 usually means they have to be immutable. That’s why, in Python, you can use
|
|
bgneal@4
|
18 tuples but not lists as keys in a dictionary. An alternative is to use
|
|
bgneal@4
|
19 a tree-based map.
|
|
bgneal@4
|
20
|
|
bgneal@4
|
21 Write an implementation of the map interface called TreeMap that uses
|
|
bgneal@4
|
22 a red-black tree to perform add and get in log time.
|
|
bgneal@4
|
23
|
|
bgneal@4
|
24 I've never researched red-black trees before, but as a C++ programmer I know
|
|
bgneal@4
|
25 they are the datastructure that powers ``std::set`` and ``std::map``. So
|
|
bgneal@4
|
26 I decided to take a look. I quickly realized this was not going to be a simple
|
|
bgneal@4
|
27 exercise, as red-black trees are quite complicated to understand and implement.
|
|
bgneal@4
|
28 They are basically binary search trees that do a lot of work to keep themselves
|
|
bgneal@4
|
29 approximately balanced.
|
|
bgneal@4
|
30
|
|
bgneal@4
|
31 I spent a few nights reading up on red-black trees. A good explanation can be
|
|
bgneal@4
|
32 found in Wikipedia_. There are even a handful of Python implementations
|
|
bgneal@4
|
33 floating about, of varying quality. But finally I found a detailed explanation
|
|
bgneal@4
|
34 that really clicked with me at `Eternally Confuzzled`_. Julienne Walker derives
|
|
bgneal@4
|
35 a unique algorithm based upon the rules for red-black trees, and the
|
|
bgneal@4
|
36 implementation code is non-recursive and top-down. Most of the other
|
|
bgneal@4
|
37 implementations I found on the web seem to be based on the textbook
|
|
bgneal@4
|
38 `Introduction To Algorithms`_, and often involve the use of parent pointers
|
|
bgneal@4
|
39 and using dummy nodes to represent the nil leaves of the tree. Julienne's
|
|
bgneal@4
|
40 solution avoided these things and seemed a bit less complex. However the best
|
|
bgneal@4
|
41 reason to study the tutorial was the explanation was very coherent and
|
|
bgneal@4
|
42 detailed. The other sources on the web seemed to be fragmented, missing
|
|
bgneal@4
|
43 details, and lacking in explanation.
|
|
bgneal@4
|
44
|
|
bgneal@4
|
45 So to complete my `Think Complexity`_ exercise, I decided to port Julienne's
|
|
bgneal@4
|
46 red-black tree algorithm from C to Python, and hopefully learn something along
|
|
bgneal@4
|
47 the way. After a couple nights of work, and one `very embarrassing bug`_, I've
|
|
bgneal@4
|
48 completed it. I can't say I quite understand every bit of the algorithm, but
|
|
bgneal@4
|
49 I certainly learned a lot. You can view the `source code at Bitbucket`_, or
|
|
bgneal@4
|
50 clone my `Think Complexity repository`_.
|
|
bgneal@4
|
51
|
|
bgneal@4
|
52 Many thanks to Julienne Walker for the `great tutorial`_! And I highly recommend
|
|
bgneal@4
|
53 `Think Complexity`_. Check them both out.
|
|
bgneal@4
|
54
|
|
bgneal@4
|
55
|
|
bgneal@4
|
56 .. _Think Complexity: http://www.greenteapress.com/compmod/
|
|
bgneal@4
|
57 .. _Wikipedia: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
|
|
bgneal@4
|
58 .. _Eternally Confuzzled: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
|
|
bgneal@4
|
59 .. _great tutorial: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
|
|
bgneal@4
|
60 .. _Introduction to Algorithms: http://mitpress.mit.edu/books/introduction-algorithms
|
|
bgneal@4
|
61 .. _very embarrassing bug: http://deathofagremmie.com/2012/12/27/a-c-python-chained-assignment-gotcha/
|
|
bgneal@4
|
62 .. _source code at Bitbucket: https://bitbucket.org/bgneal/think_complexity/src/0326803882adc4a598d890ee4d7d39d93cb64af7/redblacktree.py?at=default
|
|
bgneal@4
|
63 .. _Think Complexity repository: https://bitbucket.org/bgneal/think_complexity
|
