Red-Black Tree

A Red-Black Tree is a self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black. The tree is balanced through rotations and color changes during insertion and deletion operations.
Space Complexity: O(n)
Time Complexity: O(log n) for search, insert, and delete operations
Best Case: Ω(log n)
Average Case: Θ(log n)
Worst Case: O(log n)

class Color:
    RED = 0
    BLACK = 1

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

class RedBlackTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        new_node = Node(data)
        if not self.root:
            self.root = new_node
            self.root.color = Color.BLACK
        else:
            self._insert(self.root, new_node)
            self._fix_violation(new_node)

    def _insert(self, root, node):
        if not root:
            return node

        if node.data < root.data:
            root.left = self._insert(root.left, node)
            root.left.parent = root
        elif node.data > root.data:
            root.right = self._insert(root.right, node)
            root.right.parent = root

        return root

    def _rotate_left(self, node):
        temp_right = node.right
        node.right = temp_right.left
        if node.right:
            node.right.parent = node

        temp_right.parent = node.parent
        if not node.parent:
            self.root = temp_right
        elif node == node.parent.left:
            node.parent.left = temp_right
        else:
            node.parent.right = temp_right

        temp_right.left = node
        node.parent = temp_right

    def _rotate_right(self, node):
        temp_left = node.left
        node.left = temp_left.right
        if node.left:
            node.left.parent = node

        temp_left.parent = node.parent
        if not node.parent:
            self.root = temp_left
        elif node == node.parent.left:
            node.parent.left = temp_left
        else:
            node.parent.right = temp_left

        temp_left.right = node
        node.parent = temp_left

    def _fix_violation(self, node):
        while node != self.root and node.parent and node.parent.color == Color.RED:
            if node.parent.parent:
                if node.parent == node.parent.parent.left:
                    uncle = node.parent.parent.right
                    if uncle and uncle.color == Color.RED:
                        node.parent.color = Color.BLACK
                        uncle.color = Color.BLACK
                        node.parent.parent.color = Color.RED
                        node = node.parent.parent
                    else:
                        if node == node.parent.right:
                            node = node.parent
                            self._rotate_left(node)
                        node.parent.color = Color.BLACK
                        if node.parent.parent:
                            node.parent.parent.color = Color.RED
                            self._rotate_right(node.parent.parent)
                else:
                    uncle = node.parent.parent.left
                    if uncle and uncle.color == Color.RED:
                        node.parent.color = Color.BLACK
                        uncle.color = Color.BLACK
                        node.parent.parent.color = Color.RED
                        node = node.parent.parent
                    else:
                        if node == node.parent.left:
                            node = node.parent
                            self._rotate_right(node)
                        node.parent.color = Color.BLACK
                        if node.parent.parent:
                            node.parent.parent.color = Color.RED
                            self._rotate_left(node.parent.parent)
        if self.root:
            self.root.color = Color.BLACK

    def inorder(self, node):
        result = []
        if node:
            result = self.inorder(node.left)
            result.append(node.data)
            result = result + self.inorder(node.right)
        return result

    def preorder(self, node):
        result = []
        if node:
            result.append(node.data)
            result = result + self.preorder(node.left)
            result = result + self.preorder(node.right)
        return result

    def postorder(self, node):
        result = []
        if node:
            result = self.postorder(node.left)
            result = result + self.postorder(node.right)
            result.append(node.data)
        return result

    def display_traversal(self, traversal_type):
        if traversal_type == 'inorder':
            return ' -> '.join(map(str, self.inorder(self.root)))
        elif traversal_type == 'preorder':
            return ' -> '.join(map(str, self.preorder(self.root)))
        elif traversal_type == 'postorder':
            return ' -> '.join(map(str, self.postorder(self.root)))

# Example Usage
rb_tree = RedBlackTree()
for i in range(20):
    rb_tree.insert(random.randint(0, 100))

print("Inorder:", rb_tree.display_traversal('inorder'))
print("Preorder:", rb_tree.display_traversal('preorder'))
print("Postorder:", rb_tree.display_traversal('postorder'))