Red Black Tree Insertion in Java

Red Black Tree is a binary search tree. With extra property with each node having color either RED or BLACK.

It has following properties:

1. Every node is either RED or BLACK
2. Root element will have BLACK color.
3. Every RED node has BLACK children.
4. Every path from root to leaf will have same number of BLACK nodes.

We have few theorems over RB tree:

Note: Height of RB tree is θ(logn).

---

Insertion:
Insertion in RB tree is little tricky as compared to BST, we have following cases to insert a node in RB tree:

1. When tree is null just insert the node and it will be root, color will be BLACK.
2. To insert an element first find its position:
1. if key <= node.key then move to left
2. else move to right
3. Once we find the correct place to insert, we insert the node with color RED.
4. But if the parent of the node just inserted has color RED then it will violate 3 property.
5. So we have to fix this issue. We call it double RED problem, we resolve it using following few cases.

DOUBLE RED PROBLEM:

Few naming conventions used are parent, grandparent and uncle. And these conventions are inspired from real life.

Case 1: When uncle has red color

We will make the changes as shown in the figures:

When node x is in left side of parent and uncle is in right side of grand parent of x, second image is solution:

 When node x is in right side of parent and uncle is in left side of grand parent of x, second image is solution of problem shown in first image:

Note 1: After solving the problem it could happen that at new X double red problem could occur, so we will call our function at new X again.
Note 2: Triangles shown under X are null nodes and when problem propagates they could be trees also. But under Uncle the triangles could be null nodes or trees.

Case 2: When uncle has black color (Zig-Zag Rotation)

When x is in right side of its parent and uncle is in right side of x's grandparent.

After Zig-Zag Rotation

When x is in left side of its parent and uncle is in left side of x's grandparent.

After Zig-Zag Rotation

Case 3: When uncle and sibling both have black color (Zig-Zig Rotation)

When x is in left side of its parent and uncle is in right side of x's grandparent.

After Zig-Zig Rotation

When x is in right side of its parent and uncle is in left side of x's grandparent.

After Zig-Zig Rotation

---

Java Code for Insertion:

There are two classes and one interface:

1. RBTreeFunctions - interface
2. RBTree - class with functions
3. RBTreeTest class - testing(Driver) class

Code: click here