|
bgneal@15
|
1 """A red-black tree for Section 3.4, Exercise 4 in Allen Downey's _Think
|
|
bgneal@15
|
2 Complexity_ book.
|
|
bgneal@15
|
3
|
|
bgneal@15
|
4 http://greenteapress.com/complexity
|
|
bgneal@15
|
5
|
|
bgneal@15
|
6 Copyright (C) 2012 Brian G. Neal.
|
|
bgneal@15
|
7
|
|
bgneal@15
|
8 Permission is hereby granted, free of charge, to any person obtaining a copy of
|
|
bgneal@15
|
9 this software and associated documentation files (the "Software"), to deal in
|
|
bgneal@15
|
10 the Software without restriction, including without limitation the rights to
|
|
bgneal@15
|
11 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
|
|
bgneal@15
|
12 the Software, and to permit persons to whom the Software is furnished to do so,
|
|
bgneal@15
|
13 subject to the following conditions:
|
|
bgneal@15
|
14
|
|
bgneal@15
|
15 The above copyright notice and this permission notice shall be included in all
|
|
bgneal@15
|
16 copies or substantial portions of the Software.
|
|
bgneal@15
|
17
|
|
bgneal@15
|
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
bgneal@15
|
19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
|
|
bgneal@15
|
20 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
|
|
bgneal@15
|
21 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
|
|
bgneal@15
|
22 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
|
|
bgneal@15
|
23 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
|
bgneal@15
|
24
|
|
bgneal@15
|
25 """
|
|
bgneal@15
|
26
|
|
bgneal@16
|
27 BLACK, RED = range(2)
|
|
bgneal@15
|
28
|
|
bgneal@15
|
29 class Node(object):
|
|
bgneal@15
|
30 """A node class for red-black trees.
|
|
bgneal@15
|
31
|
|
bgneal@15
|
32 A node has an optional parent, and optional left and right children. Each
|
|
bgneal@15
|
33 node also has a color, either red or black. A node has a key and an optional
|
|
bgneal@15
|
34 value. The key is used to order the red black tree by calling the "<"
|
|
bgneal@16
|
35 operator when comparing keys. The optional value is useful for using the
|
|
bgneal@16
|
36 red-black tree to implement a map datastructure.
|
|
bgneal@15
|
37
|
|
bgneal@15
|
38 In a red-black tree, nil children are always considered black.
|
|
bgneal@15
|
39
|
|
bgneal@15
|
40 """
|
|
bgneal@15
|
41
|
|
bgneal@15
|
42 def __init__(self, key, color=RED, value=None):
|
|
bgneal@15
|
43 self.key = key
|
|
bgneal@15
|
44 self.value = value
|
|
bgneal@15
|
45 self.color = color
|
|
bgneal@15
|
46
|
|
bgneal@15
|
47 self.parent = None
|
|
bgneal@15
|
48 self.left = None
|
|
bgneal@15
|
49 self.right = None
|
|
bgneal@15
|
50
|
|
bgneal@15
|
51 @property
|
|
bgneal@15
|
52 def grandparent(self):
|
|
bgneal@15
|
53 """Return the grandparent of this node, or None if it does not exist."""
|
|
bgneal@15
|
54 return self.parent.parent if self.parent else None
|
|
bgneal@15
|
55
|
|
bgneal@15
|
56 @property
|
|
bgneal@15
|
57 def uncle(self):
|
|
bgneal@15
|
58 """Return this node's uncle if it exists, or None if not.
|
|
bgneal@15
|
59
|
|
bgneal@15
|
60 An uncle is a parent's sibling.
|
|
bgneal@15
|
61
|
|
bgneal@15
|
62 """
|
|
bgneal@15
|
63 g = self.grandparent
|
|
bgneal@15
|
64 if g:
|
|
bgneal@15
|
65 return g.left if g.right is self.parent else g.right
|
|
bgneal@15
|
66 return None
|
