How to insert a node in a red-black tree

A red-black tree is a type of self-balancing binary tree. We'll learn how to make an insertion in a red-black tree using Python.

Note: If you want to learn more about a red-black tree, click here.

Algorithm

Insertion in a red-black tree is similar to a BST except for one additional step. The tree has to be recolored or rotated after inserting the node. A new node is always colored red initially.

First, we check if the root is None. If it is, insert the new node and recolor it to black.
If the root is not None, go through the tree in such a way that if the value of a node is less than the value of the new node, move to its left child. Otherwise, move to its right child.
Once we reach a leaf node, insert the new node there.
Now check to see if any properties of the red-black tree are violated. If they are, make the necessary adjustments by balancing the tree, such as recoloring or rotating.

Let's start with an empty tree and use an illustration to specify how insertion works.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None
        self.color = RED
class RedBlackTree:
    def __init__(self):
        self.root = None
    
    def _insert(self, node, new_node):
        if node.value > new_node.value:
            if not node.left:
                node.left = new_node
                new_node.parent = node
            else:
                self._insert(node.left, new_node)
        else:
            if not node.right:
                node.right = new_node
                new_node.parent = node
            else:
                self._insert(node.right, new_node)
    
    def insert(self, new_val):
        new_node = Node(new_val)
        if not self.root:
            self.root = new_node
            self.root.color = BLACK
        else:
            self._insert(self.root, new_node)
            self.balance(new_node)
    
    def balance(self, new_node):
        while new_node.parent and new_node.parent.color != BLACK:
            if new_node == self.root:
                break
            parent = new_node.parent
            grandparent = parent.parent
            if parent == grandparent.left:
                uncle = grandparent.right
                if uncle and uncle.color == RED:
                    uncle.color = BLACK
                    parent.color = BLACK
                    grandparent.color = RED
                    new_node = grandparent
                else:
                    if new_node == parent.right:
                        new_node = parent
                        self.leftRotate(new_node)
                    new_node.parent.color = BLACK
                    new_node.parent.parent.color = RED
                    self.rightRotate(new_node.parent.parent)
            else:
                uncle = grandparent.left
                if uncle and uncle.color == RED:
                    uncle.color = BLACK
                    parent.color = BLACK
                    grandparent.color = RED
                    new_node = grandparent
                else:
                    if new_node == parent.left:
                        new_node = parent
                        self.rightRotate(new_node)
                    new_node.parent.color = BLACK
                    new_node.parent.parent.color = RED
                    self.leftRotate(new_node.parent.parent)
        self.root.color = BLACK
                
    def leftRotate(self, node):
        right_child = node.right
        node.right = right_child.left
        if right_child.left:
            right_child.left.parent = node
        if not node.parent:
            self.root = right_child
        elif node.parent.left == node:
            node.parent.left = right_child
        else:
            node.parent.right = right_child
        
        right_child.parent = node.parent
        right_child.left = node
        node.parent = right_child
    
    def rightRotate(self, node):
        left_child = node.left
        node.left = left_child.right
        if left_child.right:
            left_child.right.parent = node
        
        if not node.parent:
            self.root = left_child
        elif node.parent.left == node:
            node.parent.left = left_child
        else:
            node.parent.right = left_child
        
        left_child.parent = node.parent
        left_child.right = node
        node.parent = left_child
tree = RedBlackTree()
tree.insert(7)
tree.insert(13)
tree.insert(20)
tree.insert(31)
tree.insert(3)
tree.insert(33)
print("         ", tree.root.value, tree.root.color)
print("         /        \\")
print("    ", tree.root.left.value, tree.root.left.color, "  ", tree.root.right.value, tree.root.right.color)
print("    /          /        \\")
print("", tree.root.left.left.value, tree.root.left.left.color, "   ", tree.root.right.left.value, tree.root.right.left.color, "   ", tree.root.right.right.value, tree.root.right.right.color)

Explanation

Lines 1–7: We define a class Node that stores a single red-black tree node.
Lines 13–17: We define a private function , _insert(), that inserts a new_node in the tree. It is similar to insertion in a BST.
Lines 36–72: We define the balance function. It checks if there are two consecutive red nodes. If the uncle of the RED node is BLACK or None, then it rotates the tree. If the uncle node is RED, it changes the color of the parent and uncle nodes to BLACK and then changes the color of the grandparent to RED. This process is repeated until there are no two consecutive red nodes or we reach the tree's root.
Lines 74–106: We define the leftRotate() and rightRotate() functions that rotate a node left and right in a tree, respectively. It follows the same algorithm as rotation in an AVL.
Lines 108–119: We create a tree, and print the resulting red-black tree.

Free Resources

How to insert a node in a red-black tree

Algorithm

Code

Explanation