Mercurial > public > pelican-blog

comparison content/Coding/022-python-red-black-tree.rst @ 4:7ce6393e6d30

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