[MUD-Dev] Re: Red Black Tree ?

[T. Alexander Popiel]

In message:  <361E2BAC.E9C9C8FE at mediacom.it>
             Valerio Santinelli <tanis at mediacom.it> writes:
>
>Can anybody explain me what's a red black tree or just point me to a page
>with some docs about it ?

There are several pages on the web of fairly uniformly low quality
(just search for 'red-black tree').  Here's the beginning of what
_Introduction to Algorithms_ by Cormen, Leiserson, and Rivest has
to say on the subject:

# A red-black tree is a binary search tree with one extra bit of storage per
# node: its color, which can be either RED or BLACK.  By constraining the
# way nodes can be colored on any path from the root to a leaf, red-black
# trees ensure that no such path is more than twice as long as any other,
# so that the tree is approximately balanced.
# 
# Each node of the tree now contains the fields color, key, left,
# right, and p.  If a chils or the parent of a node does not exist,
# the corresponding pointer field of the node contains the value NIL.
# We shall regard these NIL's as being pointers to external nodes (leaves)
# of the binary search tree and the normal, key-bearing nodes as being
# internal nodes of the tree.
# 
# A binary search tree is a red-black tree if it satisfies the following
# red-black properties:
# 
# 1. Every node is either red or black.
# 2. Every leaf (NIL) is black.
# 3. If a node is red, then both its children are black.
# 4. Every simple path from a node to a descendant leaf contains the same
#    number of black nodes.
# 
# We call the number of black nodes on any path from, but not including, a
# node x to a leaf the black-height of the node, denoted bh(x).  By property
# 4, the notion of black-height is well defined, since all descending
# paths from the node have the same number of black nodes.  We define the
# black-height of a red-black tree to be the black-height of its root.
# 
# The following lemma shows why red-black trees make good search trees.
# 
# Lemma 14.1: A red-black tree with n internal nodes has height at most
# 2lg(n+1).

[ Proof omitted ]

# An immediate consequence of this lemma is that the dynamic-set operations
# Search, Minimum, Maximum, Successor, and Predecessor can be implemented
# in O(lg n) time on red-black trees, since they can be made to run in
# O(h) time on a search tree of height H (as shown in Chapter 13) and any
# red-black tree of n nodes is a search tree with height O(lg n).  Although
# the the algorithms Tree-Insert and Tree-Delete form Chapter 13 run in O(lg
# n) time when given a red-black tree as input, they do not directly support
# the dynamic-set operations Insert and Delete, since they do not guarantee
# that the modified binary search tree will be a red-black tree.  We shall
# see in Sections 14.3 and 14.4, however, that these two operations can
# indeed be supported in O(lg n) time.

Enjoy.

- Alex