Answer to Question #204108 in Java | JSP | JSF for Zahra

Question

What are Red Black Trees? Explain Insertion in a Red Black Tree with a suitable example.

Answer 1

Red black tree is a binary tree having colour as an extra attribute which can be red or black.

Insertion

1. Check if the tree is empty
2. If the tree is empty, insert a new node as the root node having a black colour.
3. If it is not empty, insert a new node on the left having a red colour.
4. If the parent of new node is black then exit the operation
5. If the parent of new node is red, check the color of parent node's sibling of newNode.
6. If it is colored Black or NULL then make suitable Rotation and Recolor it.
7. If it is colored Red then perform Recolor. Repeat the same until tree becomes Red Black Tree.