Red-Black Tree

...

• Every node is either red or black
• The root is always black
• Every leaf (null) is black
• If a node is red, then both children are black
• the children of a red node are black. Hence possible parent of red node is a black node.
• All paths from a node to leaves have the same number of black nodes

These properties ensure:

• Balanced tree
• O(log n) time for operations

Most of the BST operations (e.g., search, max, min, insert, delete.. etc.) take O(h) time where h is the height of the BST. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree. 

It is impossible to color a tree using both black and red colors without breaking the terms. However, if a tree can be colored without violating the terms, it is guaranteed to have a depth of at most , where represents the number of nodes in the tree.

Black height is the number of black nodes on a path from the root to a leaf. Leaf nodes are also counted black nodes. From the above properties 3 and 4, we can derive, a Red-Black Tree of height h has black-height >= h/2. 

Number of nodes from a node to its farthest descendant leaf is no more than twice as the number of nodes to the nearest descendant leaf.

Every Red Black Tree with n nodes has height <= 2Log2(n+1) 
This can be proved using the following facts:

1. For a general Binary Tree, let k be the minimum number of nodes on all root to NULL paths, then (Ex. If k is 3, then n is at least 7). This expression can also be written as .
2. From property 4 of Red-Black trees and above claim, we can say in a Red-Black Tree with n nodes, there is a root to leaf path with at-most black nodes.
3. From properties 3 and 5 of Red-Black trees, we can claim that the number of black nodes in a Red-Black tree is at least where n is the total number of nodes.

From the above points, we can conclude the fact that Red Black Tree with n nodes has a height less than or equal to .

In a binary search tree (BST), rotations are operations that modify the structure of the tree by moving nodes around. These rotations help maintain the balance and order of the BST, ensuring efficient search and insertion operations.

GFG

1. Perform a standard binary search tree insertion, treating the new node as a regular BST node.
2. Color the newly inserted node red.
3. If the parent of the newly inserted node is also red, and its parent's sibling (uncle) is also red, perform recoloring and restructuring operations to maintain the Red-Black Tree properties.
   • Recolor the parent and the uncle to black.
   • Recolor the grandparent to red.
   • Repeat the process for the grandparent (starting from step 3) if its parent is also red.
4. If the parent of the newly inserted node is red and its sibling is black (or null), perform a rotation and recoloring to maintain the properties.
   • If the newly inserted node is the left child of its parent and the parent is the left child of the grandparent, perform a right rotation on the grandparent.
   • If the newly inserted node is the right child of its parent and the parent is the left child of the grandparent, perform a left-right rotation (left rotation on the parent, followed by a right rotation on the grandparent).
   • If the newly inserted node is the right child of its parent and the parent is the right child of the grandparent, perform a left rotation on the grandparent.
   • If the newly inserted node is the left child of its parent and the parent is the right child of the grandparent, perform a right-left rotation (right rotation on the parent, followed by a left rotation on the grandparent).
   • Recolor the parent to black and the grandparent to red.
5. If the root of the tree becomes red after the insertion (due to recoloring in step 3), recolor it to black to satisfy the Red-Black Tree property that the root is always black.