Red black Trees operations

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.

Searching a Node

Red black trees Insertion

In a Red-Black tree, every new node must be inserted with the red colour.the insertion operation in the red-black tree is similar to the insertion operation in BST but it is inserted with the 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 color black
  3. If the tree is not empty then insert the new node as a left node with color red
  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 color of the parent node of the new node
  6. If it is colored black or NULL then make the suitable rotation and recolor it
  7. IF it is colored 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 recolor and rotation followed by recoloring to make the resultant tree an RBTree
Last updated on by vishal devxo