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

Question

Example of Insertion in Red Black Trees in Data Structures.

Answer 1

Red Black Trees is a binary search tree, where each node has a color i.e. red or black that is denoted by extra bit on that node. The root's color must be black and the new node must be red. The children of the red node should be colored red.

The insertion of a node in Red Black can be done by employing the following procedures:

• Instruction 1 - Verify if the tree is empty.
• Instruction 2 - When the tree has no node, insert the new node as the root node and color it black. Then terminate the insertion operation.
• Instruction 3 - When the tree has nodes, insert the new node and give it color red.
• Instruction 4 - When the new node's parent is black , terminate the operation.
• Instruction 5 -  When the new node's parent is red, then look at the color of the new node's sibling.
• Instruction 6 - Make an appropriate rotation and recolor it if the color is black or null.
• Instruction 7 - When the color is black, do the recoloring. Repeat the same until Red Black is formed.