red black tree insertion violation cases

case 1: red aunt violation

• swap colors of parent, aunt, and grandparent
• check for violations higher up in the tree
• if there are no more violations, insertion is complete!

case 2: black aunt violation (in line)

• swap parent and grandparent colors
• rotate parent and grandparent
• insertion is complete!

case 2.5: black line aunt violation

• rotate parent and child
• solve using case 1 or 2

for more information on red black trees click here