In this article, you will learn-
Red-Black Tree Insertion
In this tutorial, you will learn how a new node can be inserted into a red-black tree is. Additionally, you will discover working instances of insertions performed on a red-black tree in C, C++, Java, and Python.
What is a Red-Black Tree?
Red-Black Tree is a Self-balanced binary search tree with one additional piece of storage per node: it’s color which can be either Red or Black.
Each node of the tree contains the attributes color, key, left pointer, right pointer, and parent(except root node).
On the off chance that a child of a node doesn’t exist, the comparing pointer property of the node contains the value NIL.
A red-Black tree is a self-balancing binary search tree in which every node contains an additional piece for signifying the color of the node, either red or black.
Before reading this article, please refer to the article on red-dark tree.
While inserting a new node, the new node is constantly inserted as a RED node. After insertion of another node, on the off chance that the tree is violating the properties of the red-black tree, we do the accompanying operations.
- Recolor
- Rotation
Algorithm to Insert a New Node
Following steps are followed for inserting a new element into a red-black tree:
- The newNode be:
2. Let y by the leaf (ie. NIL) and x be the root of the tree. The new node is inserted in the accompanying tree.
3. Check if the tree is unfilled (ie. whether x is NIL). In the event that yes, insert newNode as a root node and color it black.
4. Else, repeat steps following steps until leaf (NIL) is reached.
a. Compare newKey with rootKey.
b. If newKey is greater than rootKey, traverse through the right subtree.
c. Else traverse through the left subtree.
5. Assign the parent of the leaf as parent of newNode.
6. In the event that leafKey is greater than newKey, make newNode as rightChild.
7. Else, make newNode as leftChild.
8. Assign NULL to the left and rightChild of newNode.
9. Assign RED color to newNode.
10. Call InsertFix-algorithm to maintain the property of the red-black tree if violated.
Why newly inserted nodes are always red in a red-black tree?
This is on the grounds that inserting a red node doesn’t violate the depth property of a red-black tree.
In the event that you connect a red node to a red node, the standard is violated yet it is simpler to fix this issue than the issue presented by violating the depth property.
Algorithm to Maintain Red-Black Property After Insertion
This algorithm is used for keeping up the property of a red-black tree if the insertion of a newNode violates this property.
- Do the accompanying until the parent of newNode p is RED.
2. In the event that p is the left child of grandParent gP of newNode, do the accompanying.
Case-I:
a. On the off chance that the color of the right child of gP of newNode is RED, set the color of both the children of gP as BLACK and the color of gP as RED.
b. Assign gP to newNode.
Case-II:
c. (Before to proceeding onward to this progression, while loop is checked. In the event that conditions are not satisfied, it the loop is broken.)
Else in the event that newNode is the right child of p, appoint p to newNode.
d. Left-Rotate newNode.
Case-III:
e. (Before proceeding onward to this progression, while the loop is checked. On the off chance that conditions are not satisfied, the loop is broken.)
Set color of p as BLACK and color of gP as RED.
f. Right-Rotate gP.
3. Else, do the accompanying.
a. In the event that the color of the left child of gP of z is RED, set the color of both the children of gP as BLACK and the shade of gP as RED.
b. Assign gP to newNode.
c. Else in the event that newNode is the left child of p, allocate p to newNode and Right-Rotate newNode.
d. Set color of p as BLACK and color of gP as RED.
e. Left-Rotate gP.
4. (This progression is performed in the wake of coming out the while loop.)
Set the root of the tree as BLACK.
The final tree look like this:
Python, Java, and C/C++ Examples
Python
# Implementing Red-Black Tree in Python import sys # Node creation class Node(): def __init__(self, item): self.item = item self.parent = None self.left = None self.right = None self.color = 1 class RedBlackTree(): def __init__(self): self.TNULL = Node(0) self.TNULL.color = 0 self.TNULL.left = None self.TNULL.right = None self.root = self.TNULL # Preorder def pre_order_helper(self, node): if node != TNULL: sys.stdout.write(node.item + " ") self.pre_order_helper(node.left) self.pre_order_helper(node.right) # Inorder def in_order_helper(self, node): if node != TNULL: self.in_order_helper(node.left) sys.stdout.write(node.item + " ") self.in_order_helper(node.right) # Postorder def post_order_helper(self, node): if node != TNULL: self.post_order_helper(node.left) self.post_order_helper(node.right) sys.stdout.write(node.item + " ") # Search the tree def search_tree_helper(self, node, key): if node == TNULL or key == node.item: return node if key < node.item: return self.search_tree_helper(node.left, key) return self.search_tree_helper(node.right, key) # Balance the tree after insertion def fix_insert(self, k): while k.parent.color == 1: if k.parent == k.parent.parent.right: u = k.parent.parent.left if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.left: k = k.parent self.right_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.left_rotate(k.parent.parent) else: u = k.parent.parent.right if u.color == 1: u.color = 0 k.parent.color = 0 k.parent.parent.color = 1 k = k.parent.parent else: if k == k.parent.right: k = k.parent self.left_rotate(k) k.parent.color = 0 k.parent.parent.color = 1 self.right_rotate(k.parent.parent) if k == self.root: break self.root.color = 0 # Printing the tree def __print_helper(self, node, indent, last): if node != self.TNULL: sys.stdout.write(indent) if last: sys.stdout.write("R----") indent += " " else: sys.stdout.write("L----") indent += "| " s_color = "RED" if node.color == 1 else "BLACK" print(str(node.item) + "(" + s_color + ")") self.__print_helper(node.left, indent, False) self.__print_helper(node.right, indent, True) def preorder(self): self.pre_order_helper(self.root) def inorder(self): self.in_order_helper(self.root) def postorder(self): self.post_order_helper(self.root) def searchTree(self, k): return self.search_tree_helper(self.root, k) def minimum(self, node): while node.left != self.TNULL: node = node.left return node def maximum(self, node): while node.right != self.TNULL: node = node.right return node def successor(self, x): if x.right != self.TNULL: return self.minimum(x.right) y = x.parent while y != self.TNULL and x == y.right: x = y y = y.parent return y def predecessor(self, x): if (x.left != self.TNULL): return self.maximum(x.left) y = x.parent while y != self.TNULL and x == y.left: x = y y = y.parent return y def left_rotate(self, x): y = x.right x.right = y.left if y.left != self.TNULL: y.left.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y def right_rotate(self, x): y = x.left x.left = y.right if y.right != self.TNULL: y.right.parent = x y.parent = x.parent if x.parent == None: self.root = y elif x == x.parent.right: x.parent.right = y else: x.parent.left = y y.right = x x.parent = y def insert(self, key): node = Node(key) node.parent = None node.item = key node.left = self.TNULL node.right = self.TNULL node.color = 1 y = None x = self.root while x != self.TNULL: y = x if node.item < x.item: x = x.left else: x = x.right node.parent = y if y == None: self.root = node elif node.item < y.item: y.left = node else: y.right = node if node.parent == None: node.color = 0 return if node.parent.parent == None: return self.fix_insert(node) def get_root(self): return self.root def print_tree(self): self.__print_helper(self.root, "", True) if __name__ == "__main__": bst = RedBlackTree() bst.insert(55) bst.insert(40) bst.insert(65) bst.insert(60) bst.insert(75) bst.insert(57) bst.print_tree()
Java
// Implementing Red-Black Tree in Java class Node { int data; Node parent; Node left; Node right; int color; } public class RedBlackTree { private Node root; private Node TNULL; // Preorder private void preOrderHelper(Node node) { if (node != TNULL) { System.out.print(node.data + " "); preOrderHelper(node.left); preOrderHelper(node.right); } } // Inorder private void inOrderHelper(Node node) { if (node != TNULL) { inOrderHelper(node.left); System.out.print(node.data + " "); inOrderHelper(node.right); } } // Post order private void postOrderHelper(Node node) { if (node != TNULL) { postOrderHelper(node.left); postOrderHelper(node.right); System.out.print(node.data + " "); } } // Search the tree private Node searchTreeHelper(Node node, int key) { if (node == TNULL || key == node.data) { return node; } if (key < node.data) { return searchTreeHelper(node.left, key); } return searchTreeHelper(node.right, key); } // Balance the tree after deletion of a node private void fixDelete(Node x) { Node s; while (x != root && x.color == 0) { if (x == x.parent.left) { s = x.parent.right; if (s.color == 1) { s.color = 0; x.parent.color = 1; leftRotate(x.parent); s = x.parent.right; } if (s.left.color == 0 && s.right.color == 0) { s.color = 1; x = x.parent; } else { if (s.right.color == 0) { s.left.color = 0; s.color = 1; rightRotate(s); s = x.parent.right; } s.color = x.parent.color; x.parent.color = 0; s.right.color = 0; leftRotate(x.parent); x = root; } } else { s = x.parent.left; if (s.color == 1) { s.color = 0; x.parent.color = 1; rightRotate(x.parent); s = x.parent.left; } if (s.right.color == 0 && s.right.color == 0) { s.color = 1; x = x.parent; } else { if (s.left.color == 0) { s.right.color = 0; s.color = 1; leftRotate(s); s = x.parent.left; } s.color = x.parent.color; x.parent.color = 0; s.left.color = 0; rightRotate(x.parent); x = root; } } } x.color = 0; } private void rbTransplant(Node u, Node v) { if (u.parent == null) { root = v; } else if (u == u.parent.left) { u.parent.left = v; } else { u.parent.right = v; } v.parent = u.parent; } // Balance the node after insertion private void fixInsert(Node k) { Node u; while (k.parent.color == 1) { if (k.parent == k.parent.parent.right) { u = k.parent.parent.left; if (u.color == 1) { u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; } else { if (k == k.parent.left) { k = k.parent; rightRotate(k); } k.parent.color = 0; k.parent.parent.color = 1; leftRotate(k.parent.parent); } } else { u = k.parent.parent.right; if (u.color == 1) { u.color = 0; k.parent.color = 0; k.parent.parent.color = 1; k = k.parent.parent; } else { if (k == k.parent.right) { k = k.parent; leftRotate(k); } k.parent.color = 0; k.parent.parent.color = 1; rightRotate(k.parent.parent); } } if (k == root) { break; } } root.color = 0; } private void printHelper(Node root, String indent, boolean last) { if (root != TNULL) { System.out.print(indent); if (last) { System.out.print("R----"); indent += " "; } else { System.out.print("L----"); indent += "| "; } String sColor = root.color == 1 ? "RED" : "BLACK"; System.out.println(root.data + "(" + sColor + ")"); printHelper(root.left, indent, false); printHelper(root.right, indent, true); } } public RedBlackTree() { TNULL = new Node(); TNULL.color = 0; TNULL.left = null; TNULL.right = null; root = TNULL; } public void preorder() { preOrderHelper(this.root); } public void inorder() { inOrderHelper(this.root); } public void postorder() { postOrderHelper(this.root); } public Node searchTree(int k) { return searchTreeHelper(this.root, k); } public Node minimum(Node node) { while (node.left != TNULL) { node = node.left; } return node; } public Node maximum(Node node) { while (node.right != TNULL) { node = node.right; } return node; } public Node successor(Node x) { if (x.right != TNULL) { return minimum(x.right); } Node y = x.parent; while (y != TNULL && x == y.right) { x = y; y = y.parent; } return y; } public Node predecessor(Node x) { if (x.left != TNULL) { return maximum(x.left); } Node y = x.parent; while (y != TNULL && x == y.left) { x = y; y = y.parent; } return y; } public void leftRotate(Node x) { Node y = x.right; x.right = y.left; if (y.left != TNULL) { y.left.parent = x; } y.parent = x.parent; if (x.parent == null) { this.root = y; } else if (x == x.parent.left) { x.parent.left = y; } else { x.parent.right = y; } y.left = x; x.parent = y; } public void rightRotate(Node x) { Node y = x.left; x.left = y.right; if (y.right != TNULL) { y.right.parent = x; } y.parent = x.parent; if (x.parent == null) { this.root = y; } else if (x == x.parent.right) { x.parent.right = y; } else { x.parent.left = y; } y.right = x; x.parent = y; } public void insert(int key) { Node node = new Node(); node.parent = null; node.data = key; node.left = TNULL; node.right = TNULL; node.color = 1; Node y = null; Node x = this.root; while (x != TNULL) { y = x; if (node.data < x.data) { x = x.left; } else { x = x.right; } } node.parent = y; if (y == null) { root = node; } else if (node.data < y.data) { y.left = node; } else { y.right = node; } if (node.parent == null) { node.color = 0; return; } if (node.parent.parent == null) { return; } fixInsert(node); } public Node getRoot() { return this.root; } public void printTree() { printHelper(this.root, "", true); } public static void main(String[] args) { RedBlackTree bst = new RedBlackTree(); bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); } }
C
// Implementing Red-Black Tree in C #include <stdio.h> #include <stdlib.h> enum nodeColor { RED, BLACK }; struct rbNode { int data, color; struct rbNode *link[2]; }; struct rbNode *root = NULL; // Create a red-black tree struct rbNode *createNode(int data) { struct rbNode *newnode; newnode = (struct rbNode *)malloc(sizeof(struct rbNode)); newnode->data = data; newnode->color = RED; newnode->link[0] = newnode->link[1] = NULL; return newnode; } // Insert an node void insertion(int data) { struct rbNode *stack[98], *ptr, *newnode, *xPtr, *yPtr; int dir[98], ht = 0, index; ptr = root; if (!root) { root = createNode(data); return; } stack[ht] = root; dir[ht++] = 0; while (ptr != NULL) { if (ptr->data == data) { printf("Duplicates Not Allowed!!\n"); return; } index = (data - ptr->data) > 0 ? 1 : 0; stack[ht] = ptr; ptr = ptr->link[index]; dir[ht++] = index; } stack[ht - 1]->link[index] = newnode = createNode(data); while ((ht >= 3) && (stack[ht - 1]->color == RED)) { if (dir[ht - 2] == 0) { yPtr = stack[ht - 2]->link[1]; if (yPtr != NULL && yPtr->color == RED) { stack[ht - 2]->color = RED; stack[ht - 1]->color = yPtr->color = BLACK; ht = ht - 2; } else { if (dir[ht - 1] == 0) { yPtr = stack[ht - 1]; } else { xPtr = stack[ht - 1]; yPtr = xPtr->link[1]; xPtr->link[1] = yPtr->link[0]; yPtr->link[0] = xPtr; stack[ht - 2]->link[0] = yPtr; } xPtr = stack[ht - 2]; xPtr->color = RED; yPtr->color = BLACK; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = xPtr; if (xPtr == root) { root = yPtr; } else { stack[ht - 3]->link[dir[ht - 3]] = yPtr; } break; } } else { yPtr = stack[ht - 2]->link[0]; if ((yPtr != NULL) && (yPtr->color == RED)) { stack[ht - 2]->color = RED; stack[ht - 1]->color = yPtr->color = BLACK; ht = ht - 2; } else { if (dir[ht - 1] == 1) { yPtr = stack[ht - 1]; } else { xPtr = stack[ht - 1]; yPtr = xPtr->link[0]; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = xPtr; stack[ht - 2]->link[1] = yPtr; } xPtr = stack[ht - 2]; yPtr->color = BLACK; xPtr->color = RED; xPtr->link[1] = yPtr->link[0]; yPtr->link[0] = xPtr; if (xPtr == root) { root = yPtr; } else { stack[ht - 3]->link[dir[ht - 3]] = yPtr; } break; } } } root->color = BLACK; } // Delete a node void deletion(int data) { struct rbNode *stack[98], *ptr, *xPtr, *yPtr; struct rbNode *pPtr, *qPtr, *rPtr; int dir[98], ht = 0, diff, i; enum nodeColor color; if (!root) { printf("Tree not available\n"); return; } ptr = root; while (ptr != NULL) { if ((data - ptr->data) == 0) break; diff = (data - ptr->data) > 0 ? 1 : 0; stack[ht] = ptr; dir[ht++] = diff; ptr = ptr->link[diff]; } if (ptr->link[1] == NULL) { if ((ptr == root) && (ptr->link[0] == NULL)) { free(ptr); root = NULL; } else if (ptr == root) { root = ptr->link[0]; free(ptr); } else { stack[ht - 1]->link[dir[ht - 1]] = ptr->link[0]; } } else { xPtr = ptr->link[1]; if (xPtr->link[0] == NULL) { xPtr->link[0] = ptr->link[0]; color = xPtr->color; xPtr->color = ptr->color; ptr->color = color; if (ptr == root) { root = xPtr; } else { stack[ht - 1]->link[dir[ht - 1]] = xPtr; } dir[ht] = 1; stack[ht++] = xPtr; } else { i = ht++; while (1) { dir[ht] = 0; stack[ht++] = xPtr; yPtr = xPtr->link[0]; if (!yPtr->link[0]) break; xPtr = yPtr; } dir[i] = 1; stack[i] = yPtr; if (i > 0) stack[i - 1]->link[dir[i - 1]] = yPtr; yPtr->link[0] = ptr->link[0]; xPtr->link[0] = yPtr->link[1]; yPtr->link[1] = ptr->link[1]; if (ptr == root) { root = yPtr; } color = yPtr->color; yPtr->color = ptr->color; ptr->color = color; } } if (ht < 1) return; if (ptr->color == BLACK) { while (1) { pPtr = stack[ht - 1]->link[dir[ht - 1]]; if (pPtr && pPtr->color == RED) { pPtr->color = BLACK; break; } if (ht < 2) break; if (dir[ht - 2] == 0) { rPtr = stack[ht - 1]->link[1]; if (!rPtr) break; if (rPtr->color == RED) { stack[ht - 1]->color = RED; rPtr->color = BLACK; stack[ht - 1]->link[1] = rPtr->link[0]; rPtr->link[0] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } dir[ht] = 0; stack[ht] = stack[ht - 1]; stack[ht - 1] = rPtr; ht++; rPtr = stack[ht - 1]->link[1]; } if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) { rPtr->color = RED; } else { if (!rPtr->link[1] || rPtr->link[1]->color == BLACK) { qPtr = rPtr->link[0]; rPtr->color = RED; qPtr->color = BLACK; rPtr->link[0] = qPtr->link[1]; qPtr->link[1] = rPtr; rPtr = stack[ht - 1]->link[1] = qPtr; } rPtr->color = stack[ht - 1]->color; stack[ht - 1]->color = BLACK; rPtr->link[1]->color = BLACK; stack[ht - 1]->link[1] = rPtr->link[0]; rPtr->link[0] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } break; } } else { rPtr = stack[ht - 1]->link[0]; if (!rPtr) break; if (rPtr->color == RED) { stack[ht - 1]->color = RED; rPtr->color = BLACK; stack[ht - 1]->link[0] = rPtr->link[1]; rPtr->link[1] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } dir[ht] = 1; stack[ht] = stack[ht - 1]; stack[ht - 1] = rPtr; ht++; rPtr = stack[ht - 1]->link[0]; } if ((!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) { rPtr->color = RED; } else { if (!rPtr->link[0] || rPtr->link[0]->color == BLACK) { qPtr = rPtr->link[1]; rPtr->color = RED; qPtr->color = BLACK; rPtr->link[1] = qPtr->link[0]; qPtr->link[0] = rPtr; rPtr = stack[ht - 1]->link[0] = qPtr; } rPtr->color = stack[ht - 1]->color; stack[ht - 1]->color = BLACK; rPtr->link[0]->color = BLACK; stack[ht - 1]->link[0] = rPtr->link[1]; rPtr->link[1] = stack[ht - 1]; if (stack[ht - 1] == root) { root = rPtr; } else { stack[ht - 2]->link[dir[ht - 2]] = rPtr; } break; } } ht--; } } } // Print the inorder traversal of the tree void inorderTraversal(struct rbNode *node) { if (node) { inorderTraversal(node->link[0]); printf("%d ", node->data); inorderTraversal(node->link[1]); } return; } // Driver code int main() { int ch, data; while (1) { printf("1. Insertion\t2. Deletion\n"); printf("3. Traverse\t4. Exit"); printf("\nEnter your choice:"); scanf("%d", &ch); switch (ch) { case 1: printf("Enter the element to insert:"); scanf("%d", &data); insertion(data); break; case 2: printf("Enter the element to delete:"); scanf("%d", &data); deletion(data); break; case 3: inorderTraversal(root); printf("\n"); break; case 4: exit(0); default: printf("Not available\n"); break; } printf("\n"); } return 0; }
C++
// Implementing Red-Black Tree in C++ #include <iostream> using namespace std; struct Node { int data; Node *parent; Node *left; Node *right; int color; }; typedef Node *NodePtr; class RedBlackTree { private: NodePtr root; NodePtr TNULL; void initializeNULLNode(NodePtr node, NodePtr parent) { node->data = 0; node->parent = parent; node->left = nullptr; node->right = nullptr; node->color = 0; } // Preorder void preOrderHelper(NodePtr node) { if (node != TNULL) { cout << node->data << " "; preOrderHelper(node->left); preOrderHelper(node->right); } } // Inorder void inOrderHelper(NodePtr node) { if (node != TNULL) { inOrderHelper(node->left); cout << node->data << " "; inOrderHelper(node->right); } } // Post order void postOrderHelper(NodePtr node) { if (node != TNULL) { postOrderHelper(node->left); postOrderHelper(node->right); cout << node->data << " "; } } NodePtr searchTreeHelper(NodePtr node, int key) { if (node == TNULL || key == node->data) { return node; } if (key < node->data) { return searchTreeHelper(node->left, key); } return searchTreeHelper(node->right, key); } // For balancing the tree after deletion void deleteFix(NodePtr x) { NodePtr s; while (x != root && x->color == 0) { if (x == x->parent->left) { s = x->parent->right; if (s->color == 1) { s->color = 0; x->parent->color = 1; leftRotate(x->parent); s = x->parent->right; } if (s->left->color == 0 && s->right->color == 0) { s->color = 1; x = x->parent; } else { if (s->right->color == 0) { s->left->color = 0; s->color = 1; rightRotate(s); s = x->parent->right; } s->color = x->parent->color; x->parent->color = 0; s->right->color = 0; leftRotate(x->parent); x = root; } } else { s = x->parent->left; if (s->color == 1) { s->color = 0; x->parent->color = 1; rightRotate(x->parent); s = x->parent->left; } if (s->right->color == 0 && s->right->color == 0) { s->color = 1; x = x->parent; } else { if (s->left->color == 0) { s->right->color = 0; s->color = 1; leftRotate(s); s = x->parent->left; } s->color = x->parent->color; x->parent->color = 0; s->left->color = 0; rightRotate(x->parent); x = root; } } } x->color = 0; } void rbTransplant(NodePtr u, NodePtr v) { if (u->parent == nullptr) { root = v; } else if (u == u->parent->left) { u->parent->left = v; } else { u->parent->right = v; } v->parent = u->parent; } void deleteNodeHelper(NodePtr node, int key) { NodePtr z = TNULL; NodePtr x, y; while (node != TNULL) { if (node->data == key) { z = node; } if (node->data <= key) { node = node->right; } else { node = node->left; } } if (z == TNULL) { cout << "Key not found in the tree" << endl; return; } y = z; int y_original_color = y->color; if (z->left == TNULL) { x = z->right; rbTransplant(z, z->right); } else if (z->right == TNULL) { x = z->left; rbTransplant(z, z->left); } else { y = minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) { x->parent = y; } else { rbTransplant(y, y->right); y->right = z->right; y->right->parent = y; } rbTransplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } delete z; if (y_original_color == 0) { deleteFix(x); } } // For balancing the tree after insertion void insertFix(NodePtr k) { NodePtr u; while (k->parent->color == 1) { if (k->parent == k->parent->parent->right) { u = k->parent->parent->left; if (u->color == 1) { u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; } else { if (k == k->parent->left) { k = k->parent; rightRotate(k); } k->parent->color = 0; k->parent->parent->color = 1; leftRotate(k->parent->parent); } } else { u = k->parent->parent->right; if (u->color == 1) { u->color = 0; k->parent->color = 0; k->parent->parent->color = 1; k = k->parent->parent; } else { if (k == k->parent->right) { k = k->parent; leftRotate(k); } k->parent->color = 0; k->parent->parent->color = 1; rightRotate(k->parent->parent); } } if (k == root) { break; } } root->color = 0; } void printHelper(NodePtr root, string indent, bool last) { if (root != TNULL) { cout << indent; if (last) { cout << "R----"; indent += " "; } else { cout << "L----"; indent += "| "; } string sColor = root->color ? "RED" : "BLACK"; cout << root->data << "(" << sColor << ")" << endl; printHelper(root->left, indent, false); printHelper(root->right, indent, true); } } public: RedBlackTree() { TNULL = new Node; TNULL->color = 0; TNULL->left = nullptr; TNULL->right = nullptr; root = TNULL; } void preorder() { preOrderHelper(this->root); } void inorder() { inOrderHelper(this->root); } void postorder() { postOrderHelper(this->root); } NodePtr searchTree(int k) { return searchTreeHelper(this->root, k); } NodePtr minimum(NodePtr node) { while (node->left != TNULL) { node = node->left; } return node; } NodePtr maximum(NodePtr node) { while (node->right != TNULL) { node = node->right; } return node; } NodePtr successor(NodePtr x) { if (x->right != TNULL) { return minimum(x->right); } NodePtr y = x->parent; while (y != TNULL && x == y->right) { x = y; y = y->parent; } return y; } NodePtr predecessor(NodePtr x) { if (x->left != TNULL) { return maximum(x->left); } NodePtr y = x->parent; while (y != TNULL && x == y->left) { x = y; y = y->parent; } return y; } void leftRotate(NodePtr x) { NodePtr y = x->right; x->right = y->left; if (y->left != TNULL) { y->left->parent = x; } y->parent = x->parent; if (x->parent == nullptr) { this->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rightRotate(NodePtr x) { NodePtr y = x->left; x->left = y->right; if (y->right != TNULL) { y->right->parent = x; } y->parent = x->parent; if (x->parent == nullptr) { this->root = y; } else if (x == x->parent->right) { x->parent->right = y; } else { x->parent->left = y; } y->right = x; x->parent = y; } // Inserting a node void insert(int key) { NodePtr node = new Node; node->parent = nullptr; node->data = key; node->left = TNULL; node->right = TNULL; node->color = 1; NodePtr y = nullptr; NodePtr x = this->root; while (x != TNULL) { y = x; if (node->data < x->data) { x = x->left; } else { x = x->right; } } node->parent = y; if (y == nullptr) { root = node; } else if (node->data < y->data) { y->left = node; } else { y->right = node; } if (node->parent == nullptr) { node->color = 0; return; } if (node->parent->parent == nullptr) { return; } insertFix(node); } NodePtr getRoot() { return this->root; } void deleteNode(int data) { deleteNodeHelper(this->root, data); } void printTree() { if (root) { printHelper(this->root, "", true); } } }; int main() { RedBlackTree bst; bst.insert(55); bst.insert(40); bst.insert(65); bst.insert(60); bst.insert(75); bst.insert(57); bst.printTree(); cout << endl << "After deleting" << endl; bst.deleteNode(40); bst.printTree(); }
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.