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

Marks: 3M

Year: Dec 2015

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.