Mercurial > public > think_complexity

comparison redblacktree.py @ 16:a00e97bcdb4a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Oops, make it importable.
author Brian Neal <bgneal@gmail.com>
date Tue, 18 Dec 2012 20:03:28 -0600
parents b163f18eaf92
children 977628018b4b
comparison
equal deleted inserted replaced
15:b163f18eaf92 16:a00e97bcdb4a
22 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 22 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
23 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 23 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 24
25 """ 25 """
26 26
27 BLACK, RED = range(1) 27 BLACK, RED = range(2)
28 28
29 class Node(object): 29 class Node(object):
30 """A node class for red-black trees. 30 """A node class for red-black trees.
31 31
32 A node has an optional parent, and optional left and right children. Each 32 A node has an optional parent, and optional left and right children. Each
33 node also has a color, either red or black. A node has a key and an optional 33 node also has a color, either red or black. A node has a key and an optional
34 value. The key is used to order the red black tree by calling the "<" 34 value. The key is used to order the red black tree by calling the "<"
35 operator when comparing keys. 35 operator when comparing keys. The optional value is useful for using the
36 red-black tree to implement a map datastructure.
36 37
37 In a red-black tree, nil children are always considered black. 38 In a red-black tree, nil children are always considered black.
38 39
39 """ 40 """
40 41