Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: May 15

Definition: A red black tree is a binary tree where each node has a color attribute, the value of which is either red or black.

Following are the properties of red black trees:

A node is either red or black.

The root is black.

Every leaf is a NULL node.

All leaves are black.

Both children of every red node are black.

Every simple path from a node to a descendant leaf contains the same number of black nodes.

The red-black tree algorithm is a method for balancing trees. Colour of the node is instrumental in determining the balance of the tree.

During insert and delete operations, nodes may be rotated to maintain tree balance.

Both average and worst-case search time is O(log n).