# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1355882044 21600
# Node ID b163f18eaf925ec876eafbe5d9f1d6f9c7c41c45
# Parent  bc2c07a059be4b2f9c790d6813ad32d9c0e8a649
Starting a redblacktree.py module for Section 3.4, Exercise 4.

diff -r bc2c07a059be -r b163f18eaf92 redblacktree.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/redblacktree.py	Tue Dec 18 19:54:04 2012 -0600
@@ -0,0 +1,65 @@
+"""A red-black tree for Section 3.4, Exercise 4 in Allen Downey's _Think
+Complexity_ book.
+
+http://greenteapress.com/complexity
+
+Copyright (C) 2012 Brian G. Neal.
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software is furnished to do so,
+subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
+FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
+COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
+IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+"""
+
+BLACK, RED = range(1)
+
+class Node(object):
+    """A node class for red-black trees.
+
+    A node has an optional parent, and optional left and right children. Each
+    node also has a color, either red or black. A node has a key and an optional
+    value. The key is used to order the red black tree by calling the "<"
+    operator when comparing keys.
+
+    In a red-black tree, nil children are always considered black.
+
+    """
+
+    def __init__(self, key, color=RED, value=None):
+        self.key = key
+        self.value = value
+        self.color = color
+
+        self.parent = None
+        self.left = None
+        self.right = None
+
+    @property
+    def grandparent(self):
+        """Return the grandparent of this node, or None if it does not exist."""
+        return self.parent.parent if self.parent else None
+
+    @property
+    def uncle(self):
+        """Return this node's uncle if it exists, or None if not.
+
+        An uncle is a parent's sibling.
+
+        """
+        g = self.grandparent
+        if g:
+            return g.left if g.right is self.parent else g.right
+        return None