data structures using operations on red-black trees preforming read-only operation (like traversing the nodes in treeon red-black tree requires no modification from those used for binary search trees remember that every red-black tree is special case of binary search tree howeverinsertion and deletion operations may violate the properties of red-black tree thereforethese operations may create need to restore the redblack properties that may require small number of ( (log nor amortized ( )colour changes inserting node in red-black tree the insertion operation starts in the same way as we add new node in the binary search tree howeverin binary search treewe always add the new node as leafwhile in red-black treeleaf nodes contain no data so instead of adding the new node as leaf nodewe add red interior node that has two black leaf nodes note that the colour of the new node is red and its leaf nodes are coloured in black once new node is addedit may violate some properties of the red-black tree so in order to restore their propertywe check for certain cases and restore the property depending on the case that turns up after insertion but before learning these cases in detailfirst let us discuss certain important terms that will be used grandparent node (gof node (nrefers to the parent of ' parent ( )as in human family trees the code to find node' grandparent can be given as followsstruct node grand_parent(struct node * /no parent means no grandparent if (( !null&( -parent !null)return -parent -parentelse return nulluncle node (uof node (nrefers to the sibling of ' parent ( )as in human family trees the code to find node' uncle can be given as followsstruct node *uncle(struct node *nstruct node *gg grand_parent( )//with no grandparentthere cannot be any uncle if ( =nullreturn nullif ( -parent = -leftreturn -rightelse return -leftwhen we insert new node in red-black treenote the followingall leaf nodes are always black so property always holds true property (both children of every red node are blackis threatened only by adding red noderepainting black node redor rotation property (all paths from any given node to its leaf nodes has equal number of black nodesis threatened only by adding black noderepainting red node blackor rotation