Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis

Marks: 5M

Year: Dec 2015, May 2016

A red-black tree is a binary search tree with the following colouring properties:

1. Every node is colour either red or black.
2. The root is black.
3. If a node is red, its children must be black.
4. Every path from a node to a null pointer must contain the same number of black nodes.

A consequence of the colouring rules is that the height of a red-black tree is at most 2 log(N+1). Consequently, searching is guaranteed to be a logarithmic operation. Figure below shows a red-black tree. Red nodes are shown with double circles.

The difficulty, as usual, is inserting a new item into the tree. The new item, as usual, is placed as a leaf in the tree. If we color this item black, then we are certain to violate condition 4, because we will create a longer path of black nodes. Thus, the item must be colour red. If the parent is black, we are done. If the parent is already red, then we will violate condition 3 by having consecutive red nodes. In this case, we have to adjust the tree to ensure that condition 3 is enforced (without introducing a violation of condition 4).

The basic operations that are used to do this are color changes and tree rotations.