Introduction To RedBlack Trees
Introduction:
A redblack tree is a form of selfbalancing binary seek tree in which each node has a further bit, and that bit is regularly interpreted because of the colouration (crimson or black). Those colours are used to make sure that the tree remains balanced, all through insertions and deletions. Even though the balance of the tree isn't always best, it is ideal to reduce the looking time and hold it round o(log n) time, where n is the total quantity of factors in the tree. This tree was invented in 1972 with the aid of Rudolf Bayer.
As each node requires the handiest one little bit of area to store the colouration records, these kinds of bushes show an equal reminiscence footprint to the conventional (uncoloured) binary seek tree.
Rules for RedBlack Tree:
 A node can have Either Red colour or Black Colour.
 Root nodes always have Black Colour.
 No two Red nodes can be adjacent to each other.
 The path from any Node to any descendants null node has the same count of black nodes.
Why do we Use Red Black Trees?
Most of the best operations (e.G., max, min, insert, delete.. Etc) take o(h) time in which (h) is the height of the Bst. The cost of these operations may also emerge as o(n) for a skewed binary tree. If we are sure that the height of the binary tree stays o(log n) after each insertion and deletion, then we can guarantee an upper certain of o(log n) for all these operations. The height of a redblack tree is constantly o(log n), wherein n is the number of nodes inside the tree.
No  Algorithm  Time complexity 
1  search  o(log(n)) 
2  delete  o(log(n)) 
3  insert  o(log(n)) 
Here “n” represents the total no of the element that is present in the red Black Tree.
Comparision B/w Red Black tree and AVL tree:
The AVL tree is more balanced than the Redblack tree, but when the deletion of insertion operation is performed, the AVL tree requires more number of rotations. So when an operation requires frequent insertion and deletion then a Redblack tree is preferred more than the AVL tree to reduce time complexity.
How does a RedBlack Tree ensure balance?
The following is not a RedBlack tree because the chain of threenodes is not possible.
The following is a redblack tree with three keys.
Facts about RedBlack tree:
 The black height of the tree is the total count of black nodes on a path from the base node to a leaf node. Leaf nodes also are counted as black nodes. So, the redblack tree of height (h) has the black height >= h/2.
 The height of a redblack tree with n nodes is h<= 2 log2(n + 1)
 All bottom leaf nodes are black.
 The redBlack tree is the remarkable variety of the Binary Tree.
 No of Black Nodes is defined as the no of black nodes from the nodes to the given node that was no of an ancestor.
Black Height of RedBlack Tree:
The count of nodes from a node to its farthest descendant leaf is not quite twice because of the number of nodes to the closest descendant leaf.
Height h of redblack Tree is >=h/2;
Note: RedBlack Tree which has a height h and nodes count(n) has height<= 2Log2(n+1);
Searching in Red Black Tree:
Since the redblack tree is a special case of the binary tree, searching is similar to binary tree searching.
Algorithm:
search_element_in_tree(tree, value):
// If current is the target element. If tree > data = value OR tree = NULL : Return tree Else : // If the target element is in the left subtree. If value < data : Return search_element_in_tree (tree > left, value) // If the target element is in the left subtree. Else : Return search_element_in_tree (tree > right, value) [ End of if ] [ End of if ]

For more refer coding ninjas tree article.
Example
Search 11 in the given Tree
Solutions:
 Start from the root.
 Compare the element with the root element if root value> our value then recurse the left else if it is less than recuse the right half.
 If the root value is equal to our value then return true.
Application:
 It is used in CPU scheduling in an operating system like Linux.
 Mysql also uses the RedBlack Tree for storing the indexes of tables.
 They are also used in the kmeans clustering algorithm for reducing complexity.
Frequently Asked Questions:
1: What is RedBlack Tree?
> RedBlack Tree is a variety of Binary Trees in which the last node of the Tree is Null.
2: Why do we use the Redblack Tree over the AVL tree?
> In every case, the time complexity of the Redblack Tree is Less than the AVL tree.
3: What is the Time complexity of the RedBlack Tree for insertion, deletion and searching?
> Time complexity for every case is o(log(n));
4: How searching takes place in RedBlack Tree?
> Searching in the redblack Tree is similar to searching in the AVL tree.
5: What are the applications of the RedBlack Tree?
> It is mainly used in Linux OS and MySql software.
Key Takeaways:
This article covered the introduction of redblack, and side by side we have covered a comparison between redblack tree and AVL trees.
Comments
No comments yet
Be the first to share what you think