CODEWITHSUNDEEP
red-black-tree
rbgodbeepboop
rbgodbeepboop

Reputation: 1

Inserting into Red-Black Tree

purely conceptually, how would I insert 21 into this red-black tree?

Tree

Upvotes: 0

Views: 150

Answers (1)

SJHowe
SJHowe

Reputation: 776

  1. You find the point of insertion. Starting with root
Compare 21 with 25 => it is less => follow to left child
Compare 21 with 15 => it is more => follow to right child
Compare 21 with 22 => it is less => follow to left child
Compare 21 with 20 => it is more => there is no right child so you insert.
  1. Insert the node as a RED node. Now there is a Red Child-Red Parent violation Parent is 20. Grandparent is 22, Uncle is 24. When Parent and Uncle are both RED you fix the violation by flipping the colours of Parent, Grandparent & Uncle. Now consider the Grandparent as the new node to fix (22). It's Parent is 15, also RED, a new violation.
  2. For new violation: Node is 22, Parent is 15, Grandparent is 15, Uncle is 35. When Parent is RED and Uncle is BLACK, you fix by rotation. You see if the Node is on the inside of the tree and rotate outwardly about the parent 15, leftwards. 22 becomes the new left child of 25, colours don't change.
  3. Now a rotation rightwards at the root of tree 25, plus swapping the colours of the root and its right child fixes the tree.

You should have

New Red black Tree

Upvotes: 1

Related Questions