Red-Black Tree
Here's the Python implementation of a Red-Black Tree:
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.color = None
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, val):
node = Node(val)
node.color = 'RED'
if self.root is None:
self.root = node
node.color = 'BLACK'
return
curr = self.root
parent = None
while curr is not None:
parent = curr
if val < curr.val:
curr = curr.left
else:
curr = curr.right
if val < parent.val:
parent.left = node
else:
parent.right = node
self._fix_violations(node)
def _fix_violations(self, node):
while node != self.root and node.color != 'BLACK' and node.parent.color == 'RED':
parent = node.parent
grandparent = parent.parent
if parent == grandparent.left:
uncle = grandparent.right
if uncle is not None and uncle.color == 'RED':
grandparent.color = 'RED'
parent.color = 'BLACK'
uncle.color = 'BLACK'
node = grandparent
else:
if node == parent.right:
self._left_rotate(parent)
node = parent
parent = node.parent
self._right_rotate(grandparent)
parent.color = 'BLACK'
grandparent.color = 'RED'
node = parent
else:
uncle = grandparent.left
if uncle is not None and uncle.color == 'RED':
grandparent.color = 'RED'
parent.color = 'BLACK'
uncle.color = 'BLACK'
node = grandparent
else:
if node == parent.left:
self._right_rotate(parent)
node = parent
parent = node.parent
self._left_rotate(grandparent)
parent.color = 'BLACK'
grandparent.color = 'RED'
node = parent
self.root.color = 'BLACK'
def _left_rotate(self, x):
y = x.right
x.right = y.left
if y.left is not None:
y.left.parent = x
y.parent = x.parent
if x.parent is 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 is not None:
y.right.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.right = x
x.parent = y
def inorder_traversal(self, node):
if node is None:
return
self.inorder_traversal(node.left)
print(node.val, end=' ')
self.inorder_traversal(node.right)
# Create a Red-Black Tree
rb_tree = RedBlackTree()
# Insert nodes into the tree
rb_tree.insert(7)
rb_tree.insert(3)
rb_tree.insert(18)
rb_tree.insert(10)
rb_tree.insert(22)
rb_tree.insert(8)
rb_tree.insert(11)
rb_tree.insert(26)
# Perform inorder traversal to print the tree
print("Red-Black Tree (Inorder Traversal):")
rb_tree.inorder_traversal(rb_tree.root)
In this example, we define a Node class to represent the nodes of the Red-Black Tree and a RedBlackTree class to implement the tree operations. The insert method inserts a new node into the tree while maintaining the Red-Black Tree properties. The _fix_violations
method is responsible for fixing any violations that may occur during
the insertion. It performs rotations and color adjustments as needed to
ensure that the tree remains balanced. The _left_rotate and _right_rotate methods perform left and right rotations, respectively. The inorder_traversal
method performs an inorder traversal of the tree to print its contents.
We create a Red-Black Tree, insert nodes into it, and print the tree
using inorder traversal.
Now, let's solve a problem using the Red-Black Tree concept. One example problem related to Red-Black Trees is "Count of Smaller Numbers After Self" .
Problem: Given an array nums, return the count of numbers that are smaller than each number in the array after it.
Example: Input: nums = [5, 2, 6, 1] Output: [2, 1, 1, 0]
class Node:
def __init__(self, val, count):
self.val = val
self.count = count
self.left = None
self.right = None
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, val):
node = Node(val, 0)
self.root = self._insert_helper(self.root, node)
def _insert_helper(self, root, node):
if root is None:
return node
if node.val < root.val:
root.left = self._insert_helper(root.left, node)
root.count += 1
else:
root.right = self._insert_helper(root.right, node)
return root
def count_smaller(self, num):
count = 0
curr = self.root
while curr:
if num == curr.val:
return count + curr.count
elif num < curr.val:
curr = curr.left
else:
count += curr.count + 1
curr = curr.right
return count
def countSmaller(nums):
n = len(nums)
result = []
rbt = RedBlackTree()
for i in range(n - 1, -1, -1):
result.append(rbt.count_smaller(nums[i]))
rbt.insert(nums[i])
return result
Explanation:
- We define a modified version of the
Nodeclass with an additional attributecount, which represents the number of smaller elements to the left of the current node. - The
RedBlackTreeclass is modified to update thecountattribute while performing insertions. - The
count_smallermethod in theRedBlackTreeclass calculates the count of smaller elements for a given number by traversing the tree. - The
countSmallerfunction takes an arraynumsas input and returns a list of counts of smaller elements for each number in the array. - We create a
RedBlackTreeobjectrbtand iterate over thenumsarray from right to left. - For each number, we append the count of smaller elements to the
resultlist and insert the number into the Red-Black Tree. - Finally, we return the
resultlist, which contains the counts of smaller elements for each number.
The time complexity of this solution is O(nlogn) since we perform n insertions into the Red-Black Tree, and each insertion takes O(logn) time on average. The space complexity is O(n) to store the resulting list.