Red Black trees are a critical data-structure in the Linux kernel. I’ve often wondered what made them unique to other trees, but ignored the impulse to dive into it much beyond reading the excellent Wikipedia article on red black trees.
An rbtree achieves O(log n) time complexity for search, insert, and remove. The key properties of an rbtree are as follows:
- A node is either red or black.
- The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
- All leaves are black.
- Both children of every red node are black.
- Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
I finally manned-up and decided to write a sample red black tree in python. Despite having covered binary trees ad nauseam in college, I was surprised how challenging it was to write a completely functional red black tree. After a few nights of “free time” dedicated to the project, I finally have something to show for it.
$ ./rbtree.py ***** Populating Red Black Tree with 1000 Nodes ***** ***** Test Insert Complexity O(log N) ***** PASS ***** Test In-Order Traversal ***** PASS ***** Test Search Complexity O(log N)***** PASS ***** Test Remove Functionality ***** PASS
The source comes with a built-in self test that inserts the values 1-1000 in random order, locates them all, then removes them in random order. It verifies the 5 properties of the rbtree at each step, and prints the results.
While I am glad to have done it, I am truly embarrassed at how long it took me to complete. On the bright side, the principles I had to dust off to get this done are now painfully fresh in my head. If you’d like to see the source, it’s available here: rbtree.py
Lastly, there is a clever interactive demo here (requires java):
Red Black Tree Demonstration
Next up… python metaclasses, and why Guido is an evil bastard.