1. Introduction

A Red-Black Tree is a binary search tree that satisfies the following red-black properties:

1. Every node is colored, either red or black.

2. The root node is black.

3. Every leaf (NIL) is black.

4. If a red node has children then, the children are always black.

5. Every simple path from a node to its descendant leaves has the same black height (the number of black nodes).

Red-Black Trees are used to maintain balanced trees with operations running in O(log n) time. They are commonly used in many data structures like TreeMap and TreeSet in Java.

2. Program Steps

1. Define the Node class, representing individual elements of the Red-Black Tree.

2. Create a RedBlackTree class that includes methods for insertion and in-order traversal.

3. Implement rotations, color-flipping, and balancing after insertions.

4. Test the RedBlackTree with several insertion operations and perform an in-order traversal.

3. Code Program

enum Color {
    RED, BLACK;
}

class Node {
    int data;
    Color color;
    Node left, right, parent;

    Node(int data) {
        this.data = data;
        this.color = Color.RED; // New nodes are always inserted as RED
        left = right = parent = null;
    }
}

class RedBlackTree {
    private Node root;
    private Node TNULL;

    // Preorder
    private void preOrderHelper(Node node) {
        if (node != TNULL) {
            System.out.print(node.data + " ");
            preOrderHelper(node.left);
            preOrderHelper(node.right);
        }
    }

    // In-order
    private void inOrderHelper(Node node) {
        if (node != TNULL) {
            inOrderHelper(node.left);
            System.out.print(node.data + " ");
            inOrderHelper(node.right);
        }
    }

    // Balance the tree after insertion
    private void balanceInsert(Node k) {
        Node u;
        while (k.parent.color == Color.RED) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == Color.RED) {
                    u.color = Color.BLACK;
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rotateRight(k);
                    }
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    rotateLeft(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;
                if (u.color == Color.RED) {
                    u.color = Color.BLACK;
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        rotateLeft(k);
                    }
                    k.parent.color = Color.BLACK;
                    k.parent.parent.color = Color.RED;
                    rotateRight(k.parent.parent);
                }
            }
            if (k == root) break;
        }
        root.color = Color.BLACK;
    }

    private void rotateLeft(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    private void rotateRight(Node x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    // Insert a node
    public void insert(int key) {
        Node node = new Node(key);
        Node y = null;
        Node x = this.root;

        while (x != TNULL) {
            y = x;
            if (node.data < x.data) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.data < y.data) {
            y.left = node;
        } else {
            y.right = node;
        }

        node.left = TNULL;
        node.right = TNULL;
        node.color = Color.RED;

        balanceInsert(node);
    }

    public void printInOrder() {
        this.inOrderHelper(this.root);
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();

        tree.insert(8);
        tree.insert(18);
        tree.insert(5);
        tree.insert(15);
        tree.insert(17);
        tree.insert(25);
        tree.insert(40);
        tree.insert(80);

        tree.printInOrder();
    }
}

Output:

5 8 15 17 18 25 40 80

4. Step By Step Explanation

1. Red-Black Tree is a balanced binary search tree where every node has a color either red or black.

2. The program first defines a Node class with properties like data, color, left child, right child, and parent. New nodes are always inserted with red color.

3. The RedBlackTree class handles the functionality of the tree like insertions, rotations, and tree balancing.

4. The rotateLeft and rotateRight methods perform rotations to balance the tree during insertions.

5. balanceInsert manages the coloring and balancing after an insertion to maintain the Red-Black properties.

6. The Main class demonstrates the working of the tree by inserting some integers and printing the tree using in-order traversal.

7. The output is the in-order traversal of the tree showing the nodes in ascending order.