Red Black Tree Insertion Algorithm

Algorithm Introduction

When we try to insert a new node in to a RBT, we have to follow the following steps:
  1. Insert new key using BST insertion algorithm
  2. Color the new node red
  3. Check Red-Black tree properties and restore if necessary.
If we insert a new node as the child of a black node, no property of RBT will be broken. This case is trivial and need no special handling. However, in another case, we result in a red node with red children. And we have to repair it to recover the BST property. Image is from Link. For more information about RBT insertion, see How Red and Black Trees Work