Implementing Red-Black Trees In Python

Introduction

Red-Black Trees are a type of self-balancing binary search trees where each node contains an extra bit for denoting the color of the node, either red or black. A Red-Black tree follows these important rules:

1. Every node is either red or black.
2. The root is always black.
3. If a node is red, then its children are always black.
4. Every path from a node to its descendent null nodes contains the same number of black nodes.

In this blog post, we will be implementing a Red-Black Tree in Python from scratch.

Implementation

The Node Class

The Node class will consist of a constructor that initializes the value, color, parent, right, and left variables.

class Node:
    def __init__(self, value=None, color=None, parent=None, right=None, left=None):
        self.value = value
        self.color = color
        self.right = right
        self.left = left

The Red-Black Tree Class

The Red-Black Tree class has an initializer that initializes the root and points to the NIL (Leaf) node.

class RedBlackTree:
    def __init__(self):
        self.NIL = Node()
        self.root = self.NIL

Insertion

For insertion, we will first add the node to the tree like a standard binary search tree. Then, we will opt to balance the tree following Red-Black Tree rules.

def insert(self, value):
    if not self.root.value:
        self.root = Node(value, 'black')
        return
    self.__insert(Node(value))

...

def __insert(self, node):
    current = self.root
    while current is not None:
        potential_parent = current
        if node.value < current.value:
            current = current.left
        else:
            current = current.right

    node.parent = potential_parent
    if node.value < potential_parent.value:
        potential_parent.left = node
    else:
        potential_parent.right = node

    node.left = self.NIL
    node.right = self.NIL

    self.balance_insert(node)

---

This is just a basic implementation of a Red-Black Tree; the intricacies of Red-Black Trees lie in their balancing methods (like rotation and color flipping) which needs a deeper understanding of the subject. Please explore and build upon this initial foundation. Happy Coding!