Red Black Tree in Data Structure Explained

Introduction

The Red-Black Tree data structure is a very important data structure that one must familiarize yourself with when learning data structures and algorithms (DSA), since it forms the basis of efficient searching, insertion, and deletion functions in many applications that have turned out to be critical including those of databases and file system.

What does Red Black Tree mean?

The Red-Black Tree is a kind of data structure which is employed in computer science to maintain the data that is simple to manage. It is some sort of binary search tree, i.e. every node has no more than two children and the tree is maintained in a balanced form to speed up search.

Rules in Red Black Tree

Every node in a Red-Black Tree is red or black. To balance the tree, it indeed goes by some rules:

∆ The node, which is the root (top) , is always black.

∆ A red node cannot contain red children (the nodes of the same color cannot be adjacent).

∆ Any one of the edges going out of the root to one of the leaves contains the same number of black nodes.

∆ With these rules the tree is kept balanced and this ensures that the height (longest path through the tree, between a leaf and the root) of the tree is as small as possible.

These rules make the tree maintained and this implies that searching, inserting, and deleting data can be performed swiftly. This plays an important role in computer science since it assists in the speed and efficiency of programs to run.

RedBlack Tree Properties

Red-Black Trees have certain properties to keep it in a balanced state:

° Node Colors

Nodes of Red-Black Tree are either red or black. This tint assists to balance the tree.

° Root Property

The tree root (the most upper node) will always be black. This property dictates that the tree will be in a balanced state as an initial feature.

° Red Property

A red node is invalid when it has red children. That is, a red node should have both of its children to be black. This does not allow successive red nodes across any path in the tree, and this is useful in ensuring balance.

° Black Property

The number of black nodes in each of the paths starting at a node, and ending at a descendant of the node (leaves (null nodes)) must be the same. This property makes sure that the tree is steadily balanced and that no path is very long compared with the others.

° Depth Property

Every leaf (null node) is regarded as black. This is a technicality that would make implementation easy and make the other properties be applied in a consistent manner.

Red-Black Tree operations

In data structure, Red-Black Tree facilitates different operations that include insertion, deletion and searching.

1. Insertion

Algorithm:

Insert the new node as in the case of a normal Binary Search Tree (BST) and mark it red.

Correct the infringements of the Red-Black Tree properties by doing rotations and recoloring.

Steps:

° Insert the node just like BST.

° Label the new vertex with red.

° In case the parent of the new node is black the tree is valid.

° When the parent is red, then the tree must be re-balanced with the following cases:

Case 1: Uncle? Red (recoloring).

Case 2: the uncle is black and the new node is a right child(left rotation).

Case 3: The new node is the left child of the uncle who is black (right rotation).

2. Deletion

Algorithm:

• Remove the node as you make in a normal Binary Search Tree (BST).
• Correct the infringements of the Red-Black Tree properties by doing rotations and recoloring.

Steps:

° Do normal deletion using BST.

° Repair any violation of Red-Black Tree properties:

Case 1: The sibling is a red (recoloring and rotations).

Case 2 The sibling is black; black children (recoloring).

Case 3: the sibling is black one red child (rotations and recoloring).

3. Searching

Algorithm:

The search can start at the root node.

Compare the key with the keys in the node that the pointer current is pointing at:

∆ When the key is less, then go to the left child.

∆ Otherwise, in case the key is larger, head on to the right child.

∆ In case of equality of the key, the search is successful.

Keep on repeating till the key is located or a leaf node is arrived.

Rotations of Red-Black Tree

Rotations in Red-Black Tree data structure exist in two kinds, namely the left rotation and the right rotation.

1. Left Rotation

Algorithm:

Assume node x to be the point where the imbalance is to appear and node y is the right child of node x.

Perform Rotation:

And, choose y as the new subtree root.

Swap the left child of y and make it the right child of x.

set the parent of y left child to x.

Adjust pointers to parents.

Steps:

° Make y = right child of x.

° Make the left subtree of y the right subtree of x.

° set the parent of y left child to x.

° Connect x parent to y.

° Assign x to y left child.

° Take x to have y as its parent.

2. Right Rotation

Algorithm:

Suppose the node where the imbalance takes place is node x with node y being the left child of x.

Perform Rotation:

And, choose y as the new subtree root.

Left child of x is the right child of move.

Set the parent of y right child to x.

Adjust pointers to parents.

Steps:

° Assign y to the left child of x.

° Make y the right subtree become the left subtree of x.

° Set the parent of the right child to x.

° Connect x parent to y.

° Make the right child of y to be x.

° Take x to have y as its parent.

Tree Traversals in Red Black Trees

To traverse a Red-Black Tree is to move through all the nodes in some particular sequence. As in other general binary search trees, the principal traversal algorithms of Red-Black Trees are in-order, pre-order and post-order traversal.

1. In-order Traversal

In-order traversal traverses a tree in an ascending order. In the case of a binary search tree this implies traversing the left subtree, the root node, and then the right subtree.

Algorithm:

° Enter the left subtree.

° Make the root node visit.

° Go to the correct subtree.

2. Pre-order Traversal

Pre- order traversing has the visit to the root node, after the left subtree and lastly the right subtree.

Algorithm:

° Make the root node visit.

° Enter the left subtree.

° Go to the correct subtree.

3. Post-order Traversal

In post-order traversal, the left subtree is being traversed first then the right subtree and then the root node.

Algorithm:

° Enter the left subtree.

° Go to the correct subtree.

° Make the root node visit.

Uncodemy Learning Data Structures

Angel-eyed learning There are also a number of courses offered at Uncodemy on how to learn more about data structures, including Red-Black Trees. Uncodemy offers training on Data Structure and Algorithms even in cities such as Delhi and Noida. These programs are focused on practical training involving the most innovative tools and technologies to develop the competence of its participants. Uncodemy boasts of disciplined and qualified trainers with good experience to head the C With Data Structure certification program. Although particular courses on Red-Black Trees may not be singled out, the data structure and the algorithms courses will certainly provide concepts that are important to learning and applying such sophisticated tree structures.