Red Black Tree Insertion Algorithm

Introduction

Red Black Tree insertion is an algorithm that adds new nodes
using standard Binary Search tree operations. Once the node has been added,
the tree must be checked for RBT property violations.

for more info about Red Black Tree properties, please visit RBT properties

Insertion into a Red Black Tree:

1. insert a new value using BST insertion algorithm


2. color the newly inserted node red


3. check the RBT properties and restore the tree if necessary

properties that need to be checked:

• the root node is a black node
• no red nodes have red nodes as children

If there is a RBT property violation

• if the node being checked is a root node, flip the node color to black


• in any other scenario, the node causing a property violation will have an aunt node.
  In order to know what repair to perform, it is important to know the color of the aunt node:


• if the node causing the violation has a red aunt node, the colors of the violating node's
  aunt, parent, and grandparent must be flipped. Then, nodes higher in the tree must be checked
  to make sure the color flips didn't cause another property violation


• if the node causing the violation has a black aunt node, the nodes must be rotated. First,
  check if the violating node, parent node, and grandparent node are aligned. If they aren't, rotate
  the violating node and its parent. Then, regardless of alignment, rotate the parent and the grandparent.
x

Example Insertions

Insert 10

• a new red node 10 is inserted
• the root node must be a black node,
  so the tree needs a repair. To do this,
  flip the color of the root node

Insert 5, 20

• new nodes 20 and 5 are inserted
• these insertions do not violate either
  property we need to check for insertions,
  so we can move on

Insert 2

• new node 2 is inserted
• a red parent cannot have a red child,
  so the tree needs a repair. To do this, follow
  the protocol for when the newly inserted node
  has a red aunt node.
• hint: you will need to resolve (check for violations>
  higher up in the tree

Insert 3

• new node 3 is inserted
• a red parent cannot have a red child,
  so the tree needs a repair. To do this, follow
  the protocol for when the newly inserted node
  has a black/null aunt node
• hint: there are two rotations for this instance

Insert 7

• new node 7 is inserted
• a red parent cannot have a red child,
  so the tree needs a repair. To do this, follow
  the protocol for when the newly inserted node
  has a red aunt node

Insert 8

• new node 8 is inserted
• a red parent cannot have a red child,
  so the tree needs a repair. To do this, follow
  the protocol for when the newly inserted node
  has a black/null aunt node

Final Red Black Tree