## Red-black trees (part 5)

###### published: Sat, 26-Apr-2008   |   updated: Sat, 3-Nov-2018

In our previous installment, we'd introduced the principles behind red-black trees as well as an appreciation of why they would produce more balanced binary search trees than pure randomness by using a process called a rotation. Then we got stuck when actually inserting a node. Obviously this is one algorithm we are going to have to crack in order to be able to build a red-black tree that we can search.

To recap, we determined that it was best to attach a new node as a red node — since making it a black node would automatically and immediately violate rule 4: "For every node in the tree, each path starting at that node to an external node has the same number of black nodes." But, having said that, we then determined that we could sometimes violate rule 3: "If a node is red, both its children are black" if the parent of the new node happened to be red too.

Our brief observations last time showed us that there were two main cases to fix up. These two cases have mirror images, making four possible cases in all. Let's call them A and A' (A-prime), and B and B'.

With A we have the new node attached as a left child of a red parent that is itself a left child, and its mirror image A' having the new node as a right child of a parent that is a right child. This is the easy case we solved last time: we merely rotate the parent about its parent and recolor them both. We noted that the sibling of the parent had to be black for this to work.

The other two mirrored cases, B and B', gave us pause, but in reality are as simple to solve as the first two cases. We merely have to do two rotations instead of one. (Authors usually call this a zig-zag rotation since we rotate first in one direction and then in the other direction.) The B case here is the new node is the right child of a parent that is a left child; with the mirror case, B', having the new node as a left child of a right facing parent.

Taking case B (a right child of a left parent), we initially rotate the parent left (anticlockwise), bringing the new node up. If you look at this intermediate stage you can see that it is exactly our first case A. And we know how to fix that: rotate the new node with its new parent and recolor. Score!