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