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:
- Insert the new node as one would in a regular binary search tree.
- 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
androtate_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.
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