Red black Trees operations

Last Updated on

There are three operations to perform on Red-Black Trees

  1. Searching
  2. Insertion
  3. Deletion

Searching in Red-black trees

steps are according to a binary search tree or AVL tree.

Red black trees Insertion

In a Red Black tree, every new node must be inserted with the red colour.the insertion operation in red-black tree is similar to the insertion operation in BST but it is inserted with colour property

After insertion operation, we need to check whether the resultant tree is RBT or not by checking the properties of Red-Black trees . If all the properties are satisfied then we go for next operations otherwise we perform the following operations to make it as BST

  1. Recolour
  2. Rotation
  3. Rotation

The Insertion operations in RBT is done with the following steps

  1. Check whether the tree is empty
  2. If the tree is empty then Insert the new node with the colour black
  3. If the tree is not empty then insert the new node as a left node with colour res
  4. if the parent of the new node is black then exit from the operation
  5. if the parent of the new node is red then check the colour of the parent node of the new node
  6. If it is coloured black or NULL then make the suitable rotation and recolour it
  7. IF it is coloured red then perform & repeat the same until the tree becomes RBT tree

Red black Trees Deletion

  • The deletion operation in red-black tree is similar to deleting nodes in BST
  • But after every deletion operation, we need to check with the RBT tree properties
  • If any of the properties violated then make a suitable operation like rotation recolour and rotation followed by recolouring to make the resultant tree an RBTree