Red Black Tree: Properties and Advantages

Red-Black Tree

A Red Black Tree could be a sort of self-balancing binary search tree, during which each node is colored with a red or black. The red black tree satisfies all the properties of the binary search tree however their square measure some further properties that were supplemental during a Red-Black Tree. the peak of a Red-Black tree is O(Logn) wherever (n is that the variety of nodes within the tree).

Properties of Red-Black Tree

• The root node must always be black in color.
• Every null kid of a node is black in a red-black tree.
• The children of a red node square measure black. It is often attainable that parent of the red node is a black node.
• All the leaves have a similar black depth.
• Every straightforward path from the basis node to the (downward) leaf node contains a similar variety of black nodes.

Red Black Tree Illustration
While representing the red-black tree color of every node ought to be shown. during this tree leaf nodes square measure merely termed as null nodes which imply they're not physical nodes. It is often checked simply within the above-given tree there square measure 2 styles of a node during which one among them is red and another one is black in color. The above-given tree follows all the properties of a red-black tree that square measure

It is a binary search tree.
The root node is black.
The children’s of red node square measure black.
All the basis to external node methods contains the same variety of black nodes.
Example: think about path 75-90-80-88-null and 75-40-30-null in each these methods three black nodes square measure there.

Advantages of Red-Black Tree

• Red black tree square measure helpful after we want insertion and deletion comparatively frequent.
• Red-black trees square measure self-balancing thus these operations square measure absolute to be O(long).
• They have comparatively low constants during a wide range of eventualities.

Insertion in Red Black Tree

• Every node that must be inserted ought to be marked as read.
• Not each insertion causes imbalance however if imbalancing happens then it is often removed, relying upon the configuration of the tree before the new insertion is formed.
• In Red black tree if imbalancing happens then for removing it 2 strategies square measure used that are: 1) Recoloring and 2) Rotation