Explain Red Black Trees also discuss the properties of Red Black tree.

Red Black Trees

A Red Black Tree is a type of self-balancing binary search tree, a data structure used in computer science to organize pieces of comparable data, such as numbers. Each node in a binary search tree has at most two children, referred to as the left child and the right child. Self-balancing means that the tree automatically ensures that it remains balanced after operations such as insertions and deletions, which helps to maintain its operations in O(log n) time complexity, where n is the number of nodes in the tree.

Properties of Red Black Trees

A Red Black Tree has the following five important properties which are crucial for maintaining the balance of the tree:

1. Node Color: Every node is either red or black.
2. Root Property: The root of the tree is always black.
3. Red Node Property: Red nodes cannot have red children (i.e., no two red nodes can be adjacent).
4. Black Height Property: Every path from a node to any of its descendant NULL nodes has the same number of black nodes. This number is called the black height of the node.
5. Path Property: For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

These properties ensure that the longest path from the root to a leaf is no more than twice as long as the shortest path from the root to a leaf. This is what keeps the tree approximately balanced, ensuring the O(log n) time complexity for insertions, deletions, and lookups.

Operations on Red Black Trees

The basic operations that can be performed on a Red Black Tree are insertion, deletion, and searching, similar to a regular binary search tree. However, after every insertion and deletion, the tree must be corrected in case any of the Red Black Tree properties have been violated.

Insertion

When a new node is inserted into a Red Black Tree, it is initially inserted as a red node. After insertion, the tree is adjusted to maintain the Red Black Tree properties. The adjustment is done through a series of rotations and color changes. The steps are as follows:

1. Insert the new node: Insert the new node as a red node in the correct location in the tree, following the binary search tree insert operation.
2. Correct the tree: If the new node's parent is black, then the tree is still valid. If the parent is red, then we may have to perform rotations and color flips to fix the tree.

Deletion

Deletion in a Red Black Tree is more complex than insertion because it may result in more violations of the Red Black Tree properties that need to be fixed. The steps are as follows:

1. Delete the node: Remove the node using the binary search tree delete operation. If the node to be deleted has two children, it is replaced with its in-order successor or predecessor (which will have at most one child), and then that node is deleted instead.
2. Correct the tree: If the deleted node was red, there's nothing to fix. If it was black, then we need to perform a series of rotations and color changes to redistribute the black height throughout the tree.

Example

Let's consider an example of inserting a node into a Red Black Tree:

Suppose we have the following Red Black Tree and we want to insert the number 18:

       11(B)
       /   \
    2(R)   14(B)
    / \      \
 1(B) 7(B)   15(R)

Here's how we would insert the number 18:

1. Insert 18: We insert 18 as a red node, following the binary search tree rules.

       11(B)
       /   \
    2(R)   14(B)
    / \      \
 1(B) 7(B)   15(R)
                \
                18(R)

1. Correct the tree: Since the new node's parent (15) is red, we have a violation of the Red Node Property. We need to perform rotations and color changes to fix this.

After performing the necessary rotations and color changes, the tree might look like this:

       11(B)
       /   \
    2(R)   15(B)
    / \    /  \
 1(B) 7(B)14(R)18(R)

Now the tree satisfies all the Red Black Tree properties.

In summary, Red Black Trees are a form of self-balancing binary search trees that maintain their balance through a set of properties and corrective rotations and color changes after insertions and deletions. This balance ensures that the operations on the tree remain efficient even as the number of elements grows.