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