Red Black tree insertion - Python Code | DSA in Tamil | DSA with Python

Описание

Red-black tree is a self-balancing binary search tree, where each node has an extra color attribute that can be either red or black. The color of a node is used to ensure that the tree remains balanced even after insertion or deletion of nodes.

The process of inserting a node into a red-black tree can be divided into several steps:

Perform a standard BST insertion: Find the correct position for the new node in the tree according to its value, and insert it as a leaf node.
Color the new node red: Since the new node is always inserted as a leaf, it has no children and coloring it red does not violate any of the red-black tree properties.
Fix any violations of the red-black tree properties that may have been introduced by the insertion: There are several cases to consider depending on the color of the new node's parent, uncle, and grandparent. The following steps outline the general approach to fixing the violations:
If the new node's parent is black, then the tree is still a valid red-black tree, and we do not need to do anything else.
If the new node's parent is red and its uncle is also red, then we need to recolor the parent, uncle, and grandparent to maintain the black height property.
If the new node's parent is red and its uncle is black or absent, then we need to perform one or more rotations and/or recolorings to balance the tree and maintain the red-black tree properties.
The exact steps to fix the violations depend on the specific case, but the overall goal is to ensure that the tree satisfies the following properties:

Every node is either red or black.
The root is black.
Every leaf (nil) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes (i.e., the black height is the same for all nodes).
The time complexity of inserting a node into a red-black tree is O(log n), where n is the number of nodes in the tree. This is because the height of a red-black tree is always O(log n) due to the balancing properties.