Skip to main content

Red Black Tree insertion

Red-Black Trees are a type of self-balancing binary search tree that ensures efficient operations while maintaining a balanced structure. This article focuses on the process of inserting nodes into a Red-Black Tree, providing a detailed explanation, step-by-step algorithm, and accompanying code examples.

Problem Statement and Description

The challenge here is to implement the insertion operation for a Red-Black Tree. The insertion process must maintain the properties of a Red-Black Tree, including the coloring of nodes and the rotations required to balance the tree.

Example

We'll use the following example Red-Black Tree to demonstrate the insertion process:

            9(B)
           /    \ 
          /      \
        5(R)    18(R)
       /  \     /    \
    1(B)  6(B) 11(B) 30(B)
           \         /   \
           7(R)    21(R)  40(R)

We'll perform insertions while maintaining the Red-Black Tree properties.

Idea to Solve

To insert a new node into a Red-Black Tree, we'll follow these key steps:

  1. Insert the new node as one would in a regular binary search tree.
  2. Fix any violations of Red-Black Tree properties by performing rotations and color adjustments.

Pseudocode

struct Node:
        int data
        int color
        Node left, right, parent
    
    Node create_node(data):
        new_node = allocate memory for Node
        set new_node.data = data
        set new_node.color = RED
        set new_node.left = NULL
        set new_node.right = NULL
        set new_node.parent = NULL
        return new_node
    
    Node insert_node(root, node):
        if root is NULL:
            return node
        if node.data < root.data:
            root.left = insert_node(root.left, node)
            root.left.parent = root
        else if node.data > root.data:
            root.right = insert_node(root.right, node)
            root.right.parent = root
        return root
    
    rotate_left(root, node):
        ...
    
    rotate_right(root, node):
        ...
    
    fix_node(root, node):
        ...
    
    insert(root, data):
        node = create_node(data)
        root = insert_node(root, node)
        fix_node(root, node)
        root.color = BLACK

Algorithm Explanation

  • The algorithm is implemented using structures and methods.
  • The insert_node function adds the node to the tree and maintains parent-child relationships.
  • The rotate_left and rotate_right functions perform left and right rotations, respectively.
  • The fix_node function handles Red-Black Tree property violations and adjusts the tree as needed.
  • The insert function combines the insertion and fixing steps while setting the root color to black.

Code Solution

// C program 
// Red-Black Tree insertion
#include <stdio.h>

#include <stdlib.h>

//Color 0 , 1
enum NodeColor
{
	RED , BLACK
};
//Red black tree node
struct Node
{
	//Node data 
	int data;
	//Node color
	int color;
	struct Node *left, *right, *parent;
};
//Create a new node of Red-Black tree
struct Node *create_node(int data)
{
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set Red black tree node value
		new_node->data = data;
		new_node->left = NULL;
		new_node->right = NULL;
		new_node->parent = NULL;
		new_node->color = RED;
	}
	else
	{
		printf("\n Memory Overflow ");
	}
	return new_node;
}
// Add new node in given red black tree 
// This is similar to insert node in binary search tree
struct Node *insert_node(struct Node *root, struct Node *node)
{
	if (root == NULL)
	{
		//When get a null node
		//return tree node
		return node;
	}
	if (node->data < root->data)
	{
		// Add node in left side
		root->left = insert_node(root->left, node);
		// Modify the parent node value
		root->left->parent = root;
	}
	else if (node->data > root->data)
	{
		// Add node in right side
		root->right = insert_node(root->right, node);
		// Modify the parent node value 
		root->right->parent = root;
	}
	return root;
}
//Perform left rotation operation
void rotate_left(struct Node **root, struct Node *node)
{
	//Get right node
	struct Node *node_right = node->right;
	//Change the right subtree in given node
	node->right = node_right->left;
	if (node->right != NULL)
	{
		// When node right subtree exists then change its parent value
		node->right->parent = node;
	}
	//Change the value of previously get right-node parent 
	node_right->parent = node->parent;
	if (node->parent == NULL)
	{
		//In case no parent of given node
		//Then make new root of Red-Black tree
		*root = node_right;
	}
	else if (node == node->parent->left)
	{
		node->parent->left = node_right;
	}
	else
	{
		node->parent->right = node_right;
	}
	//final rotation
	node_right->left = node;
	node->parent = node_right;
}
//Perform right rotation operation
void rotate_right(struct Node **root, struct Node *node)
{
	//Get left node
	struct Node *node_left = node->left;
	node->left = node_left->right;
	if (node->left != NULL)
	{
		node->left->parent = node;
	}
	node_left->parent = node->parent;
	if (node->parent == NULL)
	{
		//In case no parent of given node
		//Then make new root of Red-Black tree
		*root = node_left;
	}
	else if (node == node->parent->left)
	{
		node->parent->left = node_left;
	}
	else
	{
		node->parent->right = node_left;
	}
	//final rotation
	node_left->right = node;
	node->parent = node_left;
}
// Transform node in valid Red-Black tree
void fix_node(struct Node **root, struct Node **node)
{
	//Define some useful auxiliary variables
	struct Node *parent = NULL;
	struct Node *grand_parent = NULL;
	struct Node *uncle_node = NULL;
	int temp = 0;
	while (( *node != *root) && (( *node)->color != BLACK) && (( *node)->parent->color == RED))
	{
		parent = ( *node)->parent;
		grand_parent = ( *node)->parent->parent;
		// When parent of node is equal to left-child of Grandparents
		if (parent == grand_parent->left)
		{
			uncle_node = grand_parent->right;
			// When uncle node is red node 
			if (uncle_node != NULL && uncle_node->color == RED)
			{
				// Modified color
				grand_parent->color = RED;
				parent->color = BLACK;
				uncle_node->color = BLACK;
				( *node) = grand_parent;
			}
			else
			{
				if (( *node) == parent->right)
				{
					//Left-rotation required
					rotate_left(root, parent);
					( *node) = parent;
					parent = ( *node)->parent;
				}
				//Right-rotation required
				rotate_right(root, grand_parent);
				//swapping the value of node color
				temp = parent->color;
				parent->color = grand_parent->color;
				grand_parent->color = temp;
				//Change node parent 
				( *node) = parent;
			}
		}
		/*When parent of node is equal to right-child of Grandparents*/
		else
		{
			uncle_node = grand_parent->left;
			// When uncle node is red node 
			if ((uncle_node != NULL) && (uncle_node->color == RED))
			{
				grand_parent->color = RED;
				parent->color = BLACK;
				uncle_node->color = BLACK;
				//Change node parent
				( *node) = grand_parent;
			}
			else
			{
				if (( *node) == parent->left)
				{
					//Right-rotation required 
					rotate_right(root, parent);
					( *node) = parent;
					parent = ( *node)->parent;
				}
				// Left-rotation required
				rotate_left(root, grand_parent);
				// Swapping the value of node color
				temp = parent->color;
				parent->color = grand_parent->color;
				grand_parent->color = temp;
				( *node) = parent;
			}
		}
	}
}
//Print tree elements in preorder traversal
void preorder(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	printf("  %d", root->data);
	preorder(root->left);
	preorder(root->right);
}
//Print tree elements in inorder traversal
void inorder(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	inorder(root->left);
	printf("  %d", root->data);
	inorder(root->right);
}
//Print tree elements in preorder traversal
void postprder(struct Node *root)
{
	if (root == NULL)
	{
		return;
	}
	postprder(root->left);
	postprder(root->right);
	printf("  %d", root->data);
}
// Handle the request of add new node into given Red-Black tree
void insert(struct Node **root, int data)
{
	//Create a new node
	struct Node *node = create_node(data);
	//Add node into given tree
	*root = insert_node( *root, node);
	//Fix Red Black Tree violations 
	fix_node(root, & node);
	//Change root node color
	( *root)->color = BLACK;
}
int main()
{
	struct Node *root = NULL;
	//Add tree element
	insert( & root, 18);
	insert( & root, 5);
	insert( & root, 1);
	insert( & root, 11);
	insert( & root, 21);
	insert( & root, 6);
	insert( & root, 9);
	insert( & root, 7);
	insert( & root, 30);
	insert( & root, 40);
	/*
	  Constructed Red-Black Tree

	            9
	         /     \
	        5       18
	       / \     /   \  
	      1   6   11   30
	           \      /   \
	            7    21    40
	*/
	printf("Inorder\n");
	inorder(root);
	printf("\nPreorder\n");
	preorder(root);
	printf("\nPostprder\n");
	postprder(root);
	return 0;
}

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
// Java program
// Red-Black Tree insertion
//Red-Black tree node
class Node
{
	public int key;
	public Node left;
	public Node right;
	public Node parent;
  
	//Node color {false = Red} or {true = Black}
  
	public boolean color;
	public Node(int key)
	{
		//Set node value of Red-Black Tree
		this.key = key;
		this.left = null;
		this.right = null;
		this.parent = null;
		//here false are indicates red node
		this.color = false;
	}
}
class RedBlackTree
{
	public Node root;
	public RedBlackTree()
	{
		this.root = null;
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	public Node insert_node(Node root, Node node)
	{
		if (root == null)
		{
			//When get a null node
			return node;
		}
		if (node.key < root.key)
		{
			// Add node in left side
			root.left = insert_node(root.left, node);
			// Modify the parent node value
			root.left.parent = root;
		}
		else if (node.key > root.key)
		{
			// Add node in right side
			root.right = insert_node(root.right, node);
			// Modify the parent node value 
			root.right.parent = root;
		}
		return root;
	}
	//Perform left rotation operation
	public void rotate_left(Node node)
	{
		//Get right node
		Node node_right = node.right;
		//Change the right subtree in given node
		node.right = node_right.left;
		if (node.right != null)
		{
			// When node right subtree exists then change its parent value
			node.right.parent = node;
		}
		//Change the value of previously get right-node parent 
		node_right.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_right;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_right;
		}
		else
		{
			node.parent.right = node_right;
		}
		//final rotation
		node_right.left = node;
		node.parent = node_right;
	}
	//Perform right rotation operation
	public void rotate_right(Node node)
	{
		//Get left node
		Node node_left = node.left;
		node.left = node_left.right;
		if (node.left != null)
		{
			node.left.parent = node;
		}
		node_left.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_left;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_left;
		}
		else
		{
			node.parent.right = node_left;
		}
		//final rotation
		node_left.right = node;
		node.parent = node_left;
	}
	// Transform node in valid Red-Black tree
	public void fix_node(Node new_node)
	{
		//Define some useful auxiliary variables
		Node parent = null;
		Node grand_parent = null;
		Node uncle_node = null;
		boolean temp = false;
		Node node = new_node;
		while ((node != this.root) && (node.color != true) && (node.parent.color == false))
		{
			parent = node.parent;
			grand_parent = node.parent.parent;
			// When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent.left)
			{
				uncle_node = grand_parent.right;
				// When uncle node is red node 
				if (uncle_node != null && uncle_node.color == false)
				{
					// Modified color
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					node = grand_parent;
				}
				else
				{
					if (node == parent.right)
					{
						//Left-rotation required
						rotate_left(parent);
						node = parent;
						parent = node.parent;
					}
					//Right-rotation required
					rotate_right(grand_parent);
					//swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					//Change node parent 
					node = parent;
				}
			}
			else
			{
				uncle_node = grand_parent.left;
				// When uncle node is red node 
				if ((uncle_node != null) && (uncle_node.color == false))
				{
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					//Change node parent
					node = grand_parent;
				}
				else
				{
					if ((node) == parent.left)
					{
						//Right-rotation required 
						rotate_right(parent);
						(node) = parent;
						parent = node.parent;
					}
					// Left-rotation required
					rotate_left(grand_parent);
					// Swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					node = parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	public void preorder(Node root)
	{
		if (root == null)
		{
			return;
		}
		System.out.print("  " + root.key);
		preorder(root.left);
		preorder(root.right);
	}
	//Print tree elements in inorder traversal
	public void inorder(Node root)
	{
		if (root == null)
		{
			return;
		}
		inorder(root.left);
		System.out.print("  " + root.key);
		inorder(root.right);
	}
	//Print tree elements in preorder traversal
	public void postprder(Node root)
	{
		if (root == null)
		{
			return;
		}
		postprder(root.left);
		postprder(root.right);
		System.out.print("  " + root.key);
	}
	// Handle the request of add new node into given Red-Black tree
	public void insert(int data)
	{
		//Create a new node
		Node node = new Node(data);
		//Add node into given tree
		this.root = insert_node(this.root, node);
		//Fix Red Black Tree violations 
		fix_node(node);
		//Change root node color
		this.root.color = true;
	}
	public static void main(String[] args)
	{
		RedBlackTree obj = new RedBlackTree();
		//Add tree element
		obj.insert(18);
		obj.insert(5);
		obj.insert(1);
		obj.insert(11);
		obj.insert(21);
		obj.insert(6);
		obj.insert(9);
		obj.insert(7);
		obj.insert(30);
		obj.insert(40);
		/*
		Constructed Red-Black Tree

		          9
		       /     \
		      5       18
		     / \     /   \  
		    1   6   11   30
		         \      /   \
		          7    21    40
		*/
		System.out.print("Inorder\n");
		obj.inorder(obj.root);
		System.out.print("\nPreorder\n");
		obj.preorder(obj.root);
		System.out.print("\nPostprder\n");
		obj.postprder(obj.root);
	}
}

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
//Include header file
#include <iostream>
using namespace std;

// C++ program
// Red-Black Tree insertion

//Red-Black tree node
class Node
{
	public: 
    int key;
	Node * left;
	Node * right;
	Node * parent;
	//Node color {false = Red} or {true = Black}
	bool color;
	Node(int key)
	{
		//Set node value of Red-Black Tree
		this->key = key;
		this->left = NULL;
		this->right = NULL;
		this->parent = NULL;
		//here false are indicates red node
		this->color = false;
	}
};
class RedBlackTree
{
	public:
    Node * root;
	RedBlackTree()
	{
		this->root = NULL;
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	Node * insert_node(Node * root, Node * node)
	{
		if (root == NULL)
		{
			//When get a null node
			return node;
		}
		if (node->key < root->key)
		{
			// Add node in left side
			root->left = this->insert_node(root->left, node);
			// Modify the parent node value
			root->left->parent = root;
		}
		else if (node->key > root->key)
		{
			// Add node in right side
			root->right = this->insert_node(root->right, node);
			// Modify the parent node value 
			root->right->parent = root;
		}
		return root;
	}
	//Perform left rotation operation
	void rotate_left(Node * node)
	{
		//Get right node
		Node * node_right = node->right;
		//Change the right subtree in given node
		node->right = node_right->left;
		if (node->right != NULL)
		{
			// When node right subtree exists then change its parent value
			node->right->parent = node;
		}
		//Change the value of previously get right-node parent 
		node_right->parent = node->parent;
		if (node->parent == NULL)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this->root = node_right;
		}
		else if (node == node->parent->left)
		{
			node->parent->left = node_right;
		}
		else
		{
			node->parent->right = node_right;
		}
		//final rotation
		node_right->left = node;
		node->parent = node_right;
	}
	//Perform right rotation operation
	void rotate_right(Node * node)
	{
		//Get left node
		Node * node_left = node->left;
		node->left = node_left->right;
		if (node->left != NULL)
		{
			node->left->parent = node;
		}
		node_left->parent = node->parent;
		if (node->parent == NULL)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this->root = node_left;
		}
		else if (node == node->parent->left)
		{
			node->parent->left = node_left;
		}
		else
		{
			node->parent->right = node_left;
		}
		//final rotation
		node_left->right = node;
		node->parent = node_left;
	}
	// Transform node in valid Red-Black tree
	void fix_node(Node * new_node)
	{
		//Define some useful auxiliary variables
		Node * parent = NULL;
		Node * grand_parent = NULL;
		Node * uncle_node = NULL;
		bool temp = false;
		Node * node = new_node;
		while ((node != this->root) && (node->color != true) && (node->parent->color == false))
		{
			parent = node->parent;
			grand_parent = node->parent->parent;
			// When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent->left)
			{
				uncle_node = grand_parent->right;
				// When uncle node is red node 
				if (uncle_node != NULL && uncle_node->color == false)
				{
					// Modified color
					grand_parent->color = false;
					parent->color = true;
					uncle_node->color = true;
					node = grand_parent;
				}
				else
				{
					if (node == parent->right)
					{
						//Left-rotation required
						this->rotate_left(parent);
						node = parent;
						parent = node->parent;
					}
					//Right-rotation required
					this->rotate_right(grand_parent);
					//swapping the value of node color
					temp = parent->color;
					parent->color = grand_parent->color;
					grand_parent->color = temp;
					//Change node parent 
					node = parent;
				}
			}
			else
			{
				uncle_node = grand_parent->left;
				// When uncle node is red node 
				if ((uncle_node != NULL) && (uncle_node->color == false))
				{
					grand_parent->color = false;
					parent->color = true;
					uncle_node->color = true;
					//Change node parent
					node = grand_parent;
				}
				else
				{
					if (node == (parent->left))
					{
						//Right-rotation required 
						this->rotate_right(parent);
						node = parent;
						parent = node->parent;
					}
					// Left-rotation required
					this->rotate_left(grand_parent);
					// Swapping the value of node color
					temp = parent->color;
					parent->color = grand_parent->color;
					grand_parent->color = temp;
					node = parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	void preorder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}
		cout << "  " << root->key;
		this->preorder(root->left);
		this->preorder(root->right);
	}
	//Print tree elements in inorder traversal
	void inorder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}
		this->inorder(root->left);
		cout << "  " << root->key;
		this->inorder(root->right);
	}
	//Print tree elements in preorder traversal
	void postprder(Node * root)
	{
		if (root == NULL)
		{
			return;
		}
		this->postprder(root->left);
		this->postprder(root->right);
		cout << "  " << root->key;
	}
	// Handle the request of add new node into given Red-Black tree
	void insert(int data)
	{
		//Create a new node
		Node * node = new Node(data);
		//Add node into given tree
		this->root = this->insert_node(this->root, node);
		//Fix Red Black Tree violations 
		this->fix_node(node);
		//Change root node color
		this->root->color = true;
	}
};
int main()
{
	RedBlackTree obj = RedBlackTree();
	//Add tree element
	obj.insert(18);
	obj.insert(5);
	obj.insert(1);
	obj.insert(11);
	obj.insert(21);
	obj.insert(6);
	obj.insert(9);
	obj.insert(7);
	obj.insert(30);
	obj.insert(40);
	/*
			Constructed Red-Black Tree

			          9
			       /     \
			      5       18
			     / \     /   \  
			    1   6   11   30
			         \      /   \
			          7    21    40
			*/
	cout << "Inorder\n";
	obj.inorder(obj.root);
	cout << "\nPreorder\n";
	obj.preorder(obj.root);
	cout << "\nPostprder\n";
	obj.postprder(obj.root);
	return 0;
}

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
//Include namespace system
using System;

// C# program
// Red-Black Tree insertion

//Red-Black tree node
class Node
{
	public int key;
	public Node left;
	public Node right;
	public Node parent;
	//Node color {false = Red} or {true = Black}
	public Boolean color;
	public Node(int key)
	{
		//Set node value of Red-Black Tree
		this.key = key;
		this.left = null;
		this.right = null;
		this.parent = null;
		//here false are indicates red node
		this.color = false;
	}
}
class RedBlackTree
{
	public Node root;
	public RedBlackTree()
	{
		this.root = null;
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	public Node insert_node(Node root, Node node)
	{
		if (root == null)
		{
			//When get a null node
			return node;
		}
		if (node.key < root.key)
		{
			// Add node in left side
			root.left = insert_node(root.left, node);
			// Modify the parent node value
			root.left.parent = root;
		}
		else if (node.key > root.key)
		{
			// Add node in right side
			root.right = insert_node(root.right, node);
			// Modify the parent node value 
			root.right.parent = root;
		}
		return root;
	}
	//Perform left rotation operation
	public void rotate_left(Node node)
	{
		//Get right node
		Node node_right = node.right;
		//Change the right subtree in given node
		node.right = node_right.left;
		if (node.right != null)
		{
			// When node right subtree exists then change its parent value
			node.right.parent = node;
		}
		//Change the value of previously get right-node parent 
		node_right.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_right;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_right;
		}
		else
		{
			node.parent.right = node_right;
		}
		//final rotation
		node_right.left = node;
		node.parent = node_right;
	}
	//Perform right rotation operation
	public void rotate_right(Node node)
	{
		//Get left node
		Node node_left = node.left;
		node.left = node_left.right;
		if (node.left != null)
		{
			node.left.parent = node;
		}
		node_left.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_left;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_left;
		}
		else
		{
			node.parent.right = node_left;
		}
		//final rotation
		node_left.right = node;
		node.parent = node_left;
	}
	// Transform node in valid Red-Black tree
	public void fix_node(Node new_node)
	{
		//Define some useful auxiliary variables
		Node parent = null;
		Node grand_parent = null;
		Node uncle_node = null;
		Boolean temp = false;
		Node node = new_node;
		while ((node != this.root) && (node.color != true) && (node.parent.color == false))
		{
			parent = node.parent;
			grand_parent = node.parent.parent;
			// When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent.left)
			{
				uncle_node = grand_parent.right;
				// When uncle node is red node 
				if (uncle_node != null && uncle_node.color == false)
				{
					// Modified color
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					node = grand_parent;
				}
				else
				{
					if (node == parent.right)
					{
						//Left-rotation required
						rotate_left(parent);
						node = parent;
						parent = node.parent;
					}
					//Right-rotation required
					rotate_right(grand_parent);
					//swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					//Change node parent 
					node = parent;
				}
			}
			else
			{
				uncle_node = grand_parent.left;
				// When uncle node is red node 
				if ((uncle_node != null) && (uncle_node.color == false))
				{
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					//Change node parent
					node = grand_parent;
				}
				else
				{
					if (node == (parent.left))
					{
						//Right-rotation required 
						rotate_right(parent);
						node = parent;
						parent = node.parent;
					}
					// Left-rotation required
					rotate_left(grand_parent);
					// Swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					node = parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	public void preorder(Node root)
	{
		if (root == null)
		{
			return;
		}
		Console.Write("  " + root.key);
		preorder(root.left);
		preorder(root.right);
	}
	//Print tree elements in inorder traversal
	public void inorder(Node root)
	{
		if (root == null)
		{
			return;
		}
		inorder(root.left);
		Console.Write("  " + root.key);
		inorder(root.right);
	}
	//Print tree elements in preorder traversal
	public void postprder(Node root)
	{
		if (root == null)
		{
			return;
		}
		postprder(root.left);
		postprder(root.right);
		Console.Write("  " + root.key);
	}
	// Handle the request of add new node into given Red-Black tree
	public void insert(int data)
	{
		//Create a new node
		Node node = new Node(data);
		//Add node into given tree
		this.root = insert_node(this.root, node);
		//Fix Red Black Tree violations 
		fix_node(node);
		//Change root node color
		this.root.color = true;
	}
	public static void Main(String[] args)
	{
		RedBlackTree obj = new RedBlackTree();
		//Add tree element
		obj.insert(18);
		obj.insert(5);
		obj.insert(1);
		obj.insert(11);
		obj.insert(21);
		obj.insert(6);
		obj.insert(9);
		obj.insert(7);
		obj.insert(30);
		obj.insert(40);
		/*
				Constructed Red-Black Tree

				          9
				       /     \
				      5       18
				     / \     /   \  
				    1   6   11   30
				         \      /   \
				          7    21    40
				*/
		Console.Write("Inorder\n");
		obj.inorder(obj.root);
		Console.Write("\nPreorder\n");
		obj.preorder(obj.root);
		Console.Write("\nPostprder\n");
		obj.postprder(obj.root);
	}
}

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
<?php
// Php program
// Red-Black Tree insertion

//Red-Black tree node
class Node
{
	public $key;
	public $left;
	public $right;
	public $parent;
	//Node color {false = Red} or {true = Black}
	public $color;

	function __construct($key)
	{
		//Set node value of Red-Black Tree
		$this->key = $key;
		$this->left = null;
		$this->right = null;
		$this->parent = null;
		//here false are indicates red node
		$this->color = false;
	}
}
class RedBlackTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	public	function insert_node($root, $node)
	{
		if ($root == null)
		{
			//When get a null node
			return $node;
		}
		if ($node->key < $root->key)
		{
			// Add node in left side
			$root->left = $this->insert_node($root->left, $node);
			// Modify the parent node value
			$root->left->parent = $root;
		}
		else if ($node->key > $root->key)
		{
			// Add node in right side
			$root->right = $this->insert_node($root->right, $node);
			// Modify the parent node value 
			$root->right->parent = $root;
		}
		return $root;
	}
	//Perform left rotation operation
	public	function rotate_left($node)
	{
		//Get right node
		$node_right = $node->right;
		//Change the right subtree in given node
		$node->right = $node_right->left;
		if ($node->right != null)
		{
			// When node right subtree exists then change its parent value
			$node->right->parent = $node;
		}
		//Change the value of previously get right-node parent 
		$node_right->parent = $node->parent;
		if ($node->parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			$this->root = $node_right;
		}
		else if ($node == $node->parent->left)
		{
			$node->parent->left = $node_right;
		}
		else
		{
			$node->parent->right = $node_right;
		}
		//final rotation
		$node_right->left = $node;
		$node->parent = $node_right;
	}
	//Perform right rotation operation
	public	function rotate_right($node)
	{
		//Get left node
		$node_left = $node->left;
		$node->left = $node_left->right;
		if ($node->left != null)
		{
			$node->left->parent = $node;
		}
		$node_left->parent = $node->parent;
		if ($node->parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			$this->root = $node_left;
		}
		else if ($node == $node->parent->left)
		{
			$node->parent->left = $node_left;
		}
		else
		{
			$node->parent->right = $node_left;
		}
		//final rotation
		$node_left->right = $node;
		$node->parent = $node_left;
	}
	// Transform node in valid Red-Black tree
	public	function fix_node($new_node)
	{
		//Define some useful auxiliary variables
		$parent = null;
		$grand_parent = null;
		$uncle_node = null;
		$temp = false;
		$node = $new_node;
		while (($node != $this->root) && ($node->color != true) && ($node->parent->color == false))
		{
			$parent = $node->parent;
			$grand_parent = $node->parent->parent;
			// When parent of node is equal to left-child of Grandparents
			if ($parent == $grand_parent->left)
			{
				$uncle_node = $grand_parent->right;
				// When uncle node is red node 
				if ($uncle_node != null && $uncle_node->color == false)
				{
					// Modified color
					$grand_parent->color = false;
					$parent->color = true;
					$uncle_node->color = true;
					$node = $grand_parent;
				}
				else
				{
					if ($node == $parent->right)
					{
						//Left-rotation required
						$this->rotate_left($parent);
						$node = $parent;
						$parent = $node->parent;
					}
					//Right-rotation required
					$this->rotate_right($grand_parent);
					//swapping the value of node color
					$temp = $parent->color;
					$parent->color = $grand_parent->color;
					$grand_parent->color = $temp;
					//Change node parent 
					$node = $parent;
				}
			}
			else
			{
				$uncle_node = $grand_parent->left;
				// When uncle node is red node 
				if (($uncle_node != null) && ($uncle_node->color == false))
				{
					$grand_parent->color = false;
					$parent->color = true;
					$uncle_node->color = true;
					//Change node parent
					$node = $grand_parent;
				}
				else
				{
					if ($node == ($parent->left))
					{
						//Right-rotation required 
						$this->rotate_right($parent);
						$node = $parent;
						$parent = $node->parent;
					}
					// Left-rotation required
					$this->rotate_left($grand_parent);
					// Swapping the value of node color
					$temp = $parent->color;
					$parent->color = $grand_parent->color;
					$grand_parent->color = $temp;
					$node = $parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	public	function preorder($root)
	{
		if ($root == null)
		{
			return;
		}
		echo "  ". $root->key;
		$this->preorder($root->left);
		$this->preorder($root->right);
	}
	//Print tree elements in inorder traversal
	public	function inorder($root)
	{
		if ($root == null)
		{
			return;
		}
		$this->inorder($root->left);
		echo "  ". $root->key;
		$this->inorder($root->right);
	}
	//Print tree elements in preorder traversal
	public	function postprder($root)
	{
		if ($root == null)
		{
			return;
		}
		$this->postprder($root->left);
		$this->postprder($root->right);
		echo "  ". $root->key;
	}
	// Handle the request of add new node into given Red-Black tree
	public	function insert($data)
	{
		//Create a new node
		$node = new Node($data);
		//Add node into given tree
		$this->root = $this->insert_node($this->root, $node);
		//Fix Red Black Tree violations 
		$this->fix_node($node);
		//Change root node color
		$this->root->color = true;
	}
}

function main()
{
	$obj = new RedBlackTree();
	//Add tree element
	$obj->insert(18);
	$obj->insert(5);
	$obj->insert(1);
	$obj->insert(11);
	$obj->insert(21);
	$obj->insert(6);
	$obj->insert(9);
	$obj->insert(7);
	$obj->insert(30);
	$obj->insert(40);
	/*
			Constructed Red-Black Tree

			          9
			       /     \
			      5       18
			     / \     /   \  
			    1   6   11   30
			         \      /   \
			          7    21    40
			*/
	echo "Inorder\n";
	$obj->inorder($obj->root);
	echo "\nPreorder\n";
	$obj->preorder($obj->root);
	echo "\nPostprder\n";
	$obj->postprder($obj->root);
}
main();

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
// Node Js program
// Red-Black Tree insertion

//Red-Black tree node
class Node
{
	//Node color {false = Red} or {true = Black}
	constructor(key)
	{
		//Set node value of Red-Black Tree
		this.key = key;
		this.left = null;
		this.right = null;
		this.parent = null;
		//here false are indicates red node
		this.color = false;
	}
}
class RedBlackTree
{
	constructor()
	{
		this.root = null;
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	insert_node(root, node)
	{
		if (root == null)
		{
			//When get a null node
			return node;
		}
		if (node.key < root.key)
		{
			// Add node in left side
			root.left = this.insert_node(root.left, node);
			// Modify the parent node value
			root.left.parent = root;
		}
		else if (node.key > root.key)
		{
			// Add node in right side
			root.right = this.insert_node(root.right, node);
			// Modify the parent node value 
			root.right.parent = root;
		}
		return root;
	}
	//Perform left rotation operation
	rotate_left(node)
	{
		//Get right node
		var node_right = node.right;
		//Change the right subtree in given node
		node.right = node_right.left;
		if (node.right != null)
		{
			// When node right subtree exists then change its parent value
			node.right.parent = node;
		}
		//Change the value of previously get right-node parent 
		node_right.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_right;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_right;
		}
		else
		{
			node.parent.right = node_right;
		}
		//final rotation
		node_right.left = node;
		node.parent = node_right;
	}
	//Perform right rotation operation
	rotate_right(node)
	{
		//Get left node
		var node_left = node.left;
		node.left = node_left.right;
		if (node.left != null)
		{
			node.left.parent = node;
		}
		node_left.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_left;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_left;
		}
		else
		{
			node.parent.right = node_left;
		}
		//final rotation
		node_left.right = node;
		node.parent = node_left;
	}
	// Transform node in valid Red-Black tree
	fix_node(new_node)
	{
		//Define some useful auxiliary variables
		var parent = null;
		var grand_parent = null;
		var uncle_node = null;
		var temp = false;
		var node = new_node;
		while ((node != this.root) && (node.color != true) && (node.parent.color == false))
		{
			parent = node.parent;
			grand_parent = node.parent.parent;
			// When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent.left)
			{
				uncle_node = grand_parent.right;
				// When uncle node is red node 
				if (uncle_node != null && uncle_node.color == false)
				{
					// Modified color
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					node = grand_parent;
				}
				else
				{
					if (node == parent.right)
					{
						//Left-rotation required
						this.rotate_left(parent);
						node = parent;
						parent = node.parent;
					}
					//Right-rotation required
					this.rotate_right(grand_parent);
					//swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					//Change node parent 
					node = parent;
				}
			}
			else
			{
				uncle_node = grand_parent.left;
				// When uncle node is red node 
				if ((uncle_node != null) && (uncle_node.color == false))
				{
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					//Change node parent
					node = grand_parent;
				}
				else
				{
					if (node == (parent.left))
					{
						//Right-rotation required 
						this.rotate_right(parent);
						node = parent;
						parent = node.parent;
					}
					// Left-rotation required
					this.rotate_left(grand_parent);
					// Swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					node = parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	preorder(root)
	{
		if (root == null)
		{
			return;
		}
		process.stdout.write("  " + root.key);
		this.preorder(root.left);
		this.preorder(root.right);
	}
	//Print tree elements in inorder traversal
	inorder(root)
	{
		if (root == null)
		{
			return;
		}
		this.inorder(root.left);
		process.stdout.write("  " + root.key);
		this.inorder(root.right);
	}
	//Print tree elements in preorder traversal
	postprder(root)
	{
		if (root == null)
		{
			return;
		}
		this.postprder(root.left);
		this.postprder(root.right);
		process.stdout.write("  " + root.key);
	}
	// Handle the request of add new node into given Red-Black tree
	insert(data)
	{
		//Create a new node
		var node = new Node(data);
		//Add node into given tree
		this.root = this.insert_node(this.root, node);
		//Fix Red Black Tree violations 
		this.fix_node(node);
		//Change root node color
		this.root.color = true;
	}
}

function main()
{
	var obj = new RedBlackTree();
	//Add tree element
	obj.insert(18);
	obj.insert(5);
	obj.insert(1);
	obj.insert(11);
	obj.insert(21);
	obj.insert(6);
	obj.insert(9);
	obj.insert(7);
	obj.insert(30);
	obj.insert(40);
	/*
			Constructed Red-Black Tree

			          9
			       /     \
			      5       18
			     / \     /   \  
			    1   6   11   30
			         \      /   \
			          7    21    40
			*/
	process.stdout.write("Inorder\n");
	obj.inorder(obj.root);
	process.stdout.write("\nPreorder\n");
	obj.preorder(obj.root);
	process.stdout.write("\nPostprder\n");
	obj.postprder(obj.root);
}
main();

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
#  Python 3 program
#  Red-Black Tree insertion

# Red-Black tree node
class Node :
	
	# Node color :false = Red or :true = Black
	
	def __init__(self, key) :
		# Set node value of Red-Black Tree
		self.key = key
		self.left = None
		self.right = None
		self.parent = None
		# here false are indicates red node
		self.color = False
	

class RedBlackTree :
	
	def __init__(self) :
		self.root = None
	
	#  Add new node in given red black tree 
	#  This is similar to insert node in binary search tree
	def insert_node(self, root, node) :
		if (root == None) :
			# When get a null node
			return node
		
		if (node.key < root.key) :
			#  Add node in left side
			root.left = self.insert_node(root.left, node)
			#  Modify the parent node value
			root.left.parent = root
		
		elif(node.key > root.key) :
			#  Add node in right side
			root.right = self.insert_node(root.right, node)
			#  Modify the parent node value 
			root.right.parent = root
		
		return root
	
	# Perform left rotation operation
	def rotate_left(self, node) :
		# Get right node
		node_right = node.right
		# Change the right subtree in given node
		node.right = node_right.left
		if (node.right != None) :
			#  When node right subtree exists then change its parent value
			node.right.parent = node
		
		# Change the value of previously get right-node parent 
		node_right.parent = node.parent
		if (node.parent == None) :
			# In case no parent of given node
			# Then make new root of Red-Black tree
			self.root = node_right
		
		elif(node == node.parent.left) :
			node.parent.left = node_right
		else :
			node.parent.right = node_right
		
		# final rotation
		node_right.left = node
		node.parent = node_right
	
	# Perform right rotation operation
	def rotate_right(self, node) :
		# Get left node
		node_left = node.left
		node.left = node_left.right
		if (node.left != None) :
			node.left.parent = node
		
		node_left.parent = node.parent
		if (node.parent == None) :
			# In case no parent of given node
			# Then make new root of Red-Black tree
			self.root = node_left
		
		elif(node == node.parent.left) :
			node.parent.left = node_left
		else :
			node.parent.right = node_left
		
		# final rotation
		node_left.right = node
		node.parent = node_left
	
	#  Transform node in valid Red-Black tree
	def fix_node(self, new_node) :
		# Define some useful auxiliary variables
		parent = None
		grand_parent = None
		uncle_node = None
		temp = False
		node = new_node
		while ((node != self.root) and(node.color != True) and(node.parent.color == False)) :
			parent = node.parent
			grand_parent = node.parent.parent
			#  When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent.left) :
				uncle_node = grand_parent.right
				#  When uncle node is red node 
				if (uncle_node != None and uncle_node.color == False) :
					#  Modified color
					grand_parent.color = False
					parent.color = True
					uncle_node.color = True
					node = grand_parent
				else :
					if (node == parent.right) :
						# Left-rotation required
						self.rotate_left(parent)
						node = parent
						parent = node.parent
					
					# Right-rotation required
					self.rotate_right(grand_parent)
					# swapping the value of node color
					temp = parent.color
					parent.color = grand_parent.color
					grand_parent.color = temp
					# Change node parent 
					node = parent
				
			else :
				uncle_node = grand_parent.left
				#  When uncle node is red node 
				if ((uncle_node != None) and(uncle_node.color == False)) :
					grand_parent.color = False
					parent.color = True
					uncle_node.color = True
					# Change node parent
					node = grand_parent
				else :
					if (node == (parent.left)) :
						# Right-rotation required 
						self.rotate_right(parent)
						node = parent
						parent = node.parent
					
					#  Left-rotation required
					self.rotate_left(grand_parent)
					#  Swapping the value of node color
					temp = parent.color
					parent.color = grand_parent.color
					grand_parent.color = temp
					node = parent
				
			
		
	
	# Print tree elements in preorder traversal
	def preorder(self, root) :
		if (root == None) :
			return
		
		print("  ", root.key, end = "")
		self.preorder(root.left)
		self.preorder(root.right)
	
	# Print tree elements in inorder traversal
	def inorder(self, root) :
		if (root == None) :
			return
		
		self.inorder(root.left)
		print("  ", root.key, end = "")
		self.inorder(root.right)
	
	# Print tree elements in preorder traversal
	def postprder(self, root) :
		if (root == None) :
			return
		
		self.postprder(root.left)
		self.postprder(root.right)
		print("  ", root.key, end = "")
	
	#  Handle the request of add new node into given Red-Black tree
	def insert(self, data) :
		# Create a new node
		node = Node(data)
		# Add node into given tree
		self.root = self.insert_node(self.root, node)
		# Fix Red Black Tree violations 
		self.fix_node(node)
		# Change root node color
		self.root.color = True
	

def main() :
	obj = RedBlackTree()
	# Add tree element
	obj.insert(18)
	obj.insert(5)
	obj.insert(1)
	obj.insert(11)
	obj.insert(21)
	obj.insert(6)
	obj.insert(9)
	obj.insert(7)
	obj.insert(30)
	obj.insert(40)
	# 
	# 		Constructed Red-Black Tree
	# 		          9
	# 		       /     \
	# 		      5       18
	# 		     / \     /   \  
	# 		    1   6   11   30
	# 		         \      /   \
	# 		          7    21    40
	# 		
	
	print("Inorder\n", end = "")
	obj.inorder(obj.root)
	print("\nPreorder\n", end = "")
	obj.preorder(obj.root)
	print("\nPostprder\n", end = "")
	obj.postprder(obj.root)

if __name__ == "__main__": main()

Output

Inorder
   1   5   6   7   9   11   18   21   30   40
Preorder
   9   5   1   6   7   18   11   30   21   40
Postprder
   1   7   6   5   11   21   40   30   18   9
#  Ruby program
#  Red-Black Tree insertion

# Red-Black tree node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :key, :left, :right, :parent, :color
	attr_accessor :key, :left, :right, :parent, :color


	
	# Node color false = Redend or true = Blackend
	
	def initialize(key)
	
		# Set node value of Red-Black Tree
		self.key = key
		self.left = nil
		self.right = nil
		self.parent = nil
		# here false are indicates red node
		self.color = false
	end
end
class RedBlackTree 

	# Define the accessor and reader of class RedBlackTree  
	attr_reader :root
	attr_accessor :root


	
	def initialize()
	
		self.root = nil
	end
	#  Add new node in given red black tree 
	#  This is similar to insert node in binary search tree
	def insert_node(root, node)
	
		if (root == nil)
		
			# When get a null node
			return node
		end
		if (node.key < root.key)
		
			#  Add node in left side
			root.left = self.insert_node(root.left, node)
			#  Modify the parent node value
			root.left.parent = root
		elsif(node.key > root.key)
		
			#  Add node in right side
			root.right = self.insert_node(root.right, node)
			#  Modify the parent node value 
			root.right.parent = root
		end
		return root
	end
	# Perform left rotation operation
	def rotate_left(node)
	
		# Get right node
		node_right = node.right
		# Change the right subtree in given node
		node.right = node_right.left
		if (node.right != nil)
		
			#  When node right subtree exists then change its parent value
			node.right.parent = node
		end
		# Change the value of previously get right-node parent 
		node_right.parent = node.parent
		if (node.parent == nil)
		
			# In case no parent of given node
			# Then make new root of Red-Black tree
			self.root = node_right
		elsif(node == node.parent.left)
		
			node.parent.left = node_right
		else
		
			node.parent.right = node_right
		end
		# final rotation
		node_right.left = node
		node.parent = node_right
	end
	# Perform right rotation operation
	def rotate_right(node)
	
		# Get left node
		node_left = node.left
		node.left = node_left.right
		if (node.left != nil)
		
			node.left.parent = node
		end
		node_left.parent = node.parent
		if (node.parent == nil)
		
			# In case no parent of given node
			# Then make new root of Red-Black tree
			self.root = node_left
		elsif(node == node.parent.left)
		
			node.parent.left = node_left
		else
		
			node.parent.right = node_left
		end
		# final rotation
		node_left.right = node
		node.parent = node_left
	end
	#  Transform node in valid Red-Black tree
	def fix_node(new_node)
	
		# Define some useful auxiliary variables
		parent = nil
		grand_parent = nil
		uncle_node = nil
		temp = false
		node = new_node
		while ((node != self.root) && (node.color != true) && (node.parent.color == false))
		
			parent = node.parent
			grand_parent = node.parent.parent
			#  When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent.left)
			
				uncle_node = grand_parent.right
				#  When uncle node is red node 
				if (uncle_node != nil && uncle_node.color == false)
				
					#  Modified color
					grand_parent.color = false
					parent.color = true
					uncle_node.color = true
					node = grand_parent
				else
				
					if (node == parent.right)
					
						# Left-rotation required
						self.rotate_left(parent)
						node = parent
						parent = node.parent
					end
					# Right-rotation required
					self.rotate_right(grand_parent)
					# swapping the value of node color
					temp = parent.color
					parent.color = grand_parent.color
					grand_parent.color = temp
					# Change node parent 
					node = parent
				end
			else
			
				uncle_node = grand_parent.left
				#  When uncle node is red node 
				if ((uncle_node != nil) && (uncle_node.color == false))
				
					grand_parent.color = false
					parent.color = true
					uncle_node.color = true
					# Change node parent
					node = grand_parent
				else
				
					if (node == (parent.left))
					
						# Right-rotation required 
						self.rotate_right(parent)
						node = parent
						parent = node.parent
					end
					#  Left-rotation required
					self.rotate_left(grand_parent)
					#  Swapping the value of node color
					temp = parent.color
					parent.color = grand_parent.color
					grand_parent.color = temp
					node = parent
				end
			end
		end
	end
	# Print tree elements in preorder traversal
	def preorder(root)
	
		if (root == nil)
		
			return
		end
		print("  ", root.key)
		self.preorder(root.left)
		self.preorder(root.right)
	end
	# Print tree elements in inorder traversal
	def inorder(root)
	
		if (root == nil)
		
			return
		end
		self.inorder(root.left)
		print("  ", root.key)
		self.inorder(root.right)
	end
	# Print tree elements in preorder traversal
	def postprder(root)
	
		if (root == nil)
		
			return
		end
		self.postprder(root.left)
		self.postprder(root.right)
		print("  ", root.key)
	end
	#  Handle the request of add new node into given Red-Black tree
	def insert(data)
	
		# Create a new node
		node = Node.new(data)
		# Add node into given tree
		self.root = self.insert_node(self.root, node)
		# Fix Red Black Tree violations 
		self.fix_node(node)
		# Change root node color
		self.root.color = true
	end
end
def main()

	obj = RedBlackTree.new()
	# Add tree element
	obj.insert(18)
	obj.insert(5)
	obj.insert(1)
	obj.insert(11)
	obj.insert(21)
	obj.insert(6)
	obj.insert(9)
	obj.insert(7)
	obj.insert(30)
	obj.insert(40)
	# 
	# 		Constructed Red-Black Tree
	# 		          9
	# 		       /     \
	# 		      5       18
	# 		     / \     /   \  
	# 		    1   6   11   30
	# 		         \      /   \
	# 		          7    21    40
	# 		
	
	print("Inorder\n")
	obj.inorder(obj.root)
	print("\nPreorder\n")
	obj.preorder(obj.root)
	print("\nPostprder\n")
	obj.postprder(obj.root)
end
main()

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
// Scala program
// Red-Black Tree insertion
//Red-Black tree node
class Node(var key: Int,
	var left: Node,
		var right: Node,
			var parent: Node,
				var color: Boolean)
{
	def this(key: Int)
	{
		this(key, null, null, null, false);
	}
}
class RedBlackTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	def insert_node(root: Node, node: Node): Node = {
		if (root == null)
		{
			//When get a null node
			return node;
		}
		if (node.key < root.key)
		{
			// Add node in left side
			root.left = insert_node(root.left, node);
			// Modify the parent node value
			root.left.parent = root;
		}
		else if (node.key > root.key)
		{
			// Add node in right side
			root.right = insert_node(root.right, node);
			// Modify the parent node value 
			root.right.parent = root;
		}
		return root;
	}
	//Perform left rotation operation
	def rotate_left(node: Node): Unit = {
		//Get right node
		var node_right: Node = node.right;
		//Change the right subtree in given node
		node.right = node_right.left;
		if (node.right != null)
		{
			// When node right subtree exists then change its parent value
			node.right.parent = node;
		}
		//Change the value of previously get right-node parent 
		node_right.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_right;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_right;
		}
		else
		{
			node.parent.right = node_right;
		}
		//final rotation
		node_right.left = node;
		node.parent = node_right;
	}
	//Perform right rotation operation
	def rotate_right(node: Node): Unit = {
		//Get left node
		var node_left: Node = node.left;
		node.left = node_left.right;
		if (node.left != null)
		{
			node.left.parent = node;
		}
		node_left.parent = node.parent;
		if (node.parent == null)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			this.root = node_left;
		}
		else if (node == node.parent.left)
		{
			node.parent.left = node_left;
		}
		else
		{
			node.parent.right = node_left;
		}
		//final rotation
		node_left.right = node;
		node.parent = node_left;
	}
	// Transform node in valid Red-Black tree
	def fix_node(new_node: Node): Unit = {
		//Define some useful auxiliary variables
		var parent: Node = null;
		var grand_parent: Node = null;
		var uncle_node: Node = null;
		var temp: Boolean = false;
		var node: Node = new_node;
		while ((node != this.root) && (node.color != true) && (node.parent.color == false))
		{
			parent = node.parent;
			grand_parent = node.parent.parent;
			// When parent of node is equal to left-child of Grandparents
			if (parent == grand_parent.left)
			{
				uncle_node = grand_parent.right;
				// When uncle node is red node 
				if (uncle_node != null && uncle_node.color == false)
				{
					// Modified color
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					node = grand_parent;
				}
				else
				{
					if (node == parent.right)
					{
						//Left-rotation required
						rotate_left(parent);
						node = parent;
						parent = node.parent;
					}
					//Right-rotation required
					rotate_right(grand_parent);
					//swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					//Change node parent 
					node = parent;
				}
			}
			else
			{
				uncle_node = grand_parent.left;
				// When uncle node is red node 
				if ((uncle_node != null) && (uncle_node.color == false))
				{
					grand_parent.color = false;
					parent.color = true;
					uncle_node.color = true;
					//Change node parent
					node = grand_parent;
				}
				else
				{
					if (node == (parent.left))
					{
						//Right-rotation required 
						rotate_right(parent);
						node = parent;
						parent = node.parent;
					}
					// Left-rotation required
					rotate_left(grand_parent);
					// Swapping the value of node color
					temp = parent.color;
					parent.color = grand_parent.color;
					grand_parent.color = temp;
					node = parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	def preorder(root: Node): Unit = {
		if (root == null)
		{
			return;
		}
		print("  " + root.key);
		preorder(root.left);
		preorder(root.right);
	}
	//Print tree elements in inorder traversal
	def inorder(root: Node): Unit = {
		if (root == null)
		{
			return;
		}
		inorder(root.left);
		print("  " + root.key);
		inorder(root.right);
	}
	//Print tree elements in preorder traversal
	def postprder(root: Node): Unit = {
		if (root == null)
		{
			return;
		}
		postprder(root.left);
		postprder(root.right);
		print("  " + root.key);
	}
	// Handle the request of add new node into given Red-Black tree
	def insert(data: Int): Unit = {
		//Create a new node
		var node: Node = new Node(data);
		//Add node into given tree
		this.root = insert_node(this.root, node);
		//Fix Red Black Tree violations 
		fix_node(node);
		//Change root node color
		this.root.color = true;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: RedBlackTree = new RedBlackTree();
		//Add tree element
		obj.insert(18);
		obj.insert(5);
		obj.insert(1);
		obj.insert(11);
		obj.insert(21);
		obj.insert(6);
		obj.insert(9);
		obj.insert(7);
		obj.insert(30);
		obj.insert(40);
		/*
				Constructed Red-Black Tree

				          9
				       /     \
				      5       18
				     / \     /   \  
				    1   6   11   30
				         \      /   \
				          7    21    40
				*/
		print("Inorder\n");
		obj.inorder(obj.root);
		print("\nPreorder\n");
		obj.preorder(obj.root);
		print("\nPostprder\n");
		obj.postprder(obj.root);
	}
}

Output

Inorder
  1  5  6  7  9  11  18  21  30  40
Preorder
  9  5  1  6  7  18  11  30  21  40
Postprder
  1  7  6  5  11  21  40  30  18  9
// Swift program
// Red-Black Tree insertion

//Red-Black tree node
class Node
{
	var key: Int;
	var left: Node? ;
	var right: Node? ;
	var parent: Node? ;
	//Node color {false = Red} or {true = Black}
	var color: Bool;
	init(_ key: Int)
	{
		//Set node value of Red-Black Tree
		self.key = key;
		self.left = nil;
		self.right = nil;
		self.parent = nil;
		//here false are indicates red node
		self.color = false;
	}
}
class RedBlackTree
{
	var root: Node? ;
	init()
	{
		self.root = nil;
	}
	// Add new node in given red black tree 
	// This is similar to insert node in binary search tree
	func insert_node(_ root: Node? , _ node : Node? ) -> Node?
	{
		if (root == nil)
		{
			//When get a null node
			return node;
		}
		if (node!.key < root!.key)
		{
			// Add node in left side
			root!.left = self.insert_node(root!.left, node);
			// Modify the parent node value
			root!.left!.parent = root;
		}
		else if (node!.key > root!.key)
		{
			// Add node in right side
			root!.right = self.insert_node(root!.right, node);
			// Modify the parent node value 
			root!.right!.parent = root;
		}
		return root;
	}
	//Perform left rotation operation
	func rotate_left(_ node: Node? )
	{
		//Get right node
		let node_right: Node? = node!.right;
		//Change the right subtree in given node
		node!.right = node_right!.left;
		if (node!.right != nil)
		{
			// When node right subtree exists then change its parent value
			node!.right!.parent = node;
		}
		//Change the value of previously get right-node parent 
		node_right!.parent = node!.parent;
		if (node!.parent == nil)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			self.root = node_right;
		}
		else if (node === node!.parent!.left)
		{
			node!.parent!.left = node_right;
		}
		else
		{
			node!.parent!.right = node_right;
		}
		//final rotation
		node_right!.left = node;
		node!.parent = node_right;
	}
	//Perform right rotation operation
	func rotate_right(_ node: Node? )
	{
		//Get left node
		let node_left: Node? = node!.left;
		node!.left = node_left!.right;
		if (node!.left != nil)
		{
			node!.left!.parent = node;
		}
		node_left!.parent = node!.parent;
		if (node!.parent == nil)
		{
			//In case no parent of given node
			//Then make new root of Red-Black tree
			self.root = node_left;
		}
		else if (node === node!.parent!.left)
		{
			node!.parent!.left = node_left;
		}
		else
		{
			node!.parent!.right = node_left;
		}
		//final rotation
		node_left!.right = node;
		node!.parent = node_left;
	}
	// Transform node in valid Red-Black tree
	func fix_node(_ new_node: Node? )
	{
		//Define some useful auxiliary variables
		var parent: Node? = nil;
		var grand_parent: Node? = nil;
		var uncle_node: Node? = nil;
		var temp: Bool = false;
		var node: Node? = new_node;
		while (!(node === self.root) && (node!.color != true) && (node!.parent!.color == false))
		{
			parent = node!.parent;
			grand_parent = node!.parent!.parent;
			// When parent of node is equal to left-child of Grandparents
			if (parent === grand_parent!.left)
			{
				uncle_node = grand_parent!.right;
				// When uncle node is red node 
				if (uncle_node != nil && uncle_node!.color == false)
				{
					// Modified color
					grand_parent!.color = false;
					parent!.color = true;
					uncle_node!.color = true;
					node = grand_parent;
				}
				else
				{
					if (node === parent!.right)
					{
						//Left-rotation required
						self.rotate_left(parent);
						node = parent;
						parent = node!.parent;
					}
					//Right-rotation required
					self.rotate_right(grand_parent);
					//swapping the value of node color
					temp = parent!.color;
					parent!.color = grand_parent!.color;
					grand_parent!.color = temp;
					//Change node parent 
					node = parent;
				}
			}
			else
			{
				uncle_node = grand_parent!.left;
				// When uncle node is red node 
				if ((uncle_node != nil) && (uncle_node!.color == false))
				{
					grand_parent!.color = false;
					parent!.color = true;
					uncle_node!.color = true;
					//Change node parent
					node = grand_parent;
				}
				else
				{
					if (node === (parent!.left))
					{
						//Right-rotation required 
						self.rotate_right(parent);
						node = parent;
						parent = node!.parent;
					}
					// Left-rotation required
					self.rotate_left(grand_parent);
					// Swapping the value of node color
					temp = parent!.color;
					parent!.color = grand_parent!.color;
					grand_parent!.color = temp;
					node = parent;
				}
			}
		}
	}
	//Print tree elements in preorder traversal
	func preorder(_ root: Node? )
	{
		if (root == nil)
		{
			return;
		}
		print("  ", root!.key, terminator: "");
		self.preorder(root!.left);
		self.preorder(root!.right);
	}
	//Print tree elements in inorder traversal
	func inorder(_ root: Node? )
	{
		if (root == nil)
		{
			return;
		}
		self.inorder(root!.left);
		print("  ", root!.key, terminator: "");
		self.inorder(root!.right);
	}
	//Print tree elements in preorder traversal
	func postprder(_ root: Node? )
	{
		if (root == nil)
		{
			return;
		}
		self.postprder(root!.left);
		self.postprder(root!.right);
		print("  ", root!.key, terminator: "");
	}
	// Handle the request of add new node into given Red-Black tree
	func insert(_ data: Int)
	{
		//Create a new node
		let node: Node? = Node(data);
		//Add node into given tree
		self.root = self.insert_node(self.root, node);
		//Fix Red Black Tree violations 
		self.fix_node(node);
		//Change root node color
		self.root!.color = true;
	}
}
func main()
{
	let obj: RedBlackTree = RedBlackTree();
	//Add tree element
	obj.insert(18);
	obj.insert(5);
	obj.insert(1);
	obj.insert(11);
	obj.insert(21);
	obj.insert(6);
	obj.insert(9);
	obj.insert(7);
	obj.insert(30);
	obj.insert(40);
	/*
			Constructed Red-Black Tree

			          9
			       /     \
			      5       18
			     / \     /   \  
			    1   6   11   30
			         \      /   \
			          7    21    40
			*/
	print("Inorder\n", terminator: "");
	obj.inorder(obj.root);
	print("\nPreorder\n", terminator: "");
	obj.preorder(obj.root);
	print("\nPostprder\n", terminator: "");
	obj.postprder(obj.root);
}
main();

Output

Inorder
   1   5   6   7   9   11   18   21   30   40
Preorder
   9   5   1   6   7   18   11   30   21   40
Postprder
   1   7   6   5   11   21   40   30   18   9

Time Complexity

The time complexity of insertion in a Red-Black Tree is O(log n), which ensures efficient and balanced operations even after inserting multiple nodes.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment