Red-Black Tree

Red-Black Tree:
Defintion:

A red-black tree is a binary search tree with one extra attribute for each node:
the colour, which is either red or black.

Red-Black Trees: These are binary trees with the following properties.

Every node has a value.

The value of any node is greater than the value of its left child and less than the value of its right child.

Every node is colored either red or black.

The root is black.

Every leaf (NULL) is black.

If a node is red, then both its children are black.

Every path from the root to a leaf contains the same number of black nodes.

An n node red/black tree has the property that its height is O(lg(n)).
Red-black trees: Trees which remain balanced - and thus guarantee O(logn) search times - in a dynamic environment.
Another important property is that a node can be added to a red/black tree and, in O(lg(n)) time,
the tree can be readjusted to become a larger red/black tree. Similarly, a node can be deleted from
a red/black tree and, in O(lg(n)) time, the tree can be readjusted to become smaller a red/black tree.
Due to these properties, red/black trees are useful for data storage.

There are some other balanced tree structures: AVL-trees, and B-trees.

Maintaining the storage and keeping balance of tree:

Insertion: The rules for readjustment when inserting depend on the concept of rotation.

Deletion See Section 13.4 on pages 288 to 294. (Introduction To Algorithms, Cormen, Leiserson, Rivest and Stein)

CODES from Ford & Topp:
Using the RBTREE Class RBTREE Class

Exercise from Ford & Topp:
Consider the following insertion sequence:
15, 55, 28, 45, 32, 40, 35, 38, 36, 37
(a) Draw the corresponding binary search tree
(b) Draw a red-black tree that corresponds to the data.
Click here for the solution.