Red-Black Tree
Overview
The previous section about AVL tree revelead the concept of a self-balancing binary search tree. Red-Black Tree is similar in that regards - it's another type of a self-balancing binary search tree that uses rotation.
The key difference between AVL tree and Red-Black tree is the way they achieve that balance. In AVL tree it was Balance Factor, for Red-Black - it's colors (as obvious by its name).
There are a few properties of a Red-Black tree:
-
Color (as we already mentioned) - each node should be either black or red color
-
Root property - the root node should always be black
-
Leaf property - the leaf nodes are specific NIL nodes that do NOT contain data. Those are sometimes implicit (as in the animation, they are not visible) but imagine that every node at the end had 2 leaf black nodes attached to it without any values.
-
Red property - Nodes that are red should not have red children (both its children should be black). This helps in maintaining tree balance and spread the red colored nodes.
-
Black property - every path from the root to any nil leaf node should contain the same number of black nodes
After reading these properties, you may be wondering which nodes then should be colored red? Well, each new inserted node should be considered red by default. Then, based on the above properties, we decide if we should paint it black or let it stay red.
These properties ensure similar to AVL tree time complexity of O(log n) for search, insert and delete. But the main difference to the AVL tree is that Red-Black tree has a 'looser' and more 'forgiving' balance. This means that Red-Black tree requires less balancing rotations which makes it a better choice for use cases with more frequent (or unknown expectations of) modifications.
In short - Red-Black tree is a more 'modern' and loose version of a self-balancing binary search tree while AVL tree is an older, stricter version.
Code
RED = "red"
BLACK = "black"
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.parent = None
self.color = RED # New nodes are always inserted as red
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = self.create_node(value)
if not self.root:
new_node.color = BLACK
self.root = new_node
else:
current_node = self.root
while current_node:
if value < current_node.value:
if not current_node.left:
self.set_parent(new_node, current_node)
current_node.left = new_node
break
current_node = current_node.left
elif value > current_node.value:
if not current_node.right:
self.set_parent(new_node, current_node)
current_node.right = new_node
break
current_node = current_node.right
else:
return # Node with the same value already exists, ignore duplicates
self.adjust_after_insertion(new_node)
def create_node(self, value):
return Node(value)
def set_parent(self, child, parent):
child.parent = parent
def adjust_after_insertion(self, new_node):
while new_node != self.root and new_node.parent.color == RED and new_node.color == RED:
parent = new_node.parent
grandparent = parent.parent
if parent == grandparent.left:
uncle = grandparent.right
if uncle and uncle.color == RED:
# Case 1: Recoloring
parent.color = BLACK
uncle.color = BLACK
grandparent.color = RED
new_node = grandparent
else:
if new_node == parent.right:
# Case 2: Left rotation
new_node = parent
self.left_rotate(new_node)
# Case 3: Right rotation
parent.color = BLACK
grandparent.color = RED
self.right_rotate(grandparent)
else:
uncle = grandparent.left
if uncle and uncle.color == RED:
# Case 1: Recoloring
parent.color = BLACK
uncle.color = BLACK
grandparent.color = RED
new_node = grandparent
else:
if new_node == parent.left:
# Case 2: Right rotation
new_node = parent
self.right_rotate(new_node)
# Case 3: Left rotation
parent.color = BLACK
grandparent.color = RED
self.left_rotate(grandparent)
# Ensure the root node is always black
self.root.color = BLACK
def left_rotate(self, node):
right_child = node.right
node.right = right_child.left
if right_child.left:
right_child.left.parent = node
right_child.parent = node.parent
if not node.parent:
self.root = right_child
elif node == node.parent.left:
node.parent.left = right_child
else:
node.parent.right = right_child
right_child.left = node
node.parent = right_child
def right_rotate(self, node):
left_child = node.left
node.left = left_child.right
if left_child.right:
left_child.right.parent = node
left_child.parent = node.parent
if not node.parent:
self.root = left_child
elif node == node.parent.right:
node.parent.right = left_child
else:
node.parent.left = left_child
left_child.right = node
node.parent = left_child
# Test the Red-Black Tree with the given input from the animation
input_values = [1, 2, 3, 4, 5, 6, 7, 8]
rb_tree = RedBlackTree()
for value in input_values:
rb_tree.insert(value)
# You can explore the tree by printing different properties of the root like - 'left', 'right', 'value', 'color', etc
print(rb_tree.root)
const RED = "red";
const BLACK = "black";
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
this.color = RED; // New nodes are always inserted as red
}
}
class RedBlackTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = this.createNode(value);
if (!this.root) {
newNode.color = BLACK;
this.root = newNode;
} else {
let currentNode = this.root;
while (currentNode) {
if (value < currentNode.value) {
if (!currentNode.left) {
this.setParent(newNode, currentNode);
currentNode.left = newNode;
break;
}
currentNode = currentNode.left;
} else if (value > currentNode.value) {
if (!currentNode.right) {
this.setParent(newNode, currentNode);
currentNode.right = newNode;
break;
}
currentNode = currentNode.right;
} else {
return; // Node with the same value already exists, ignore duplicates
}
}
this.adjustAfterInsertion(newNode);
}
}
createNode(value) {
return new Node(value);
}
setParent(child, parent) {
child.parent = parent;
}
adjustAfterInsertion(newNode) {
while (
newNode !== this.root &&
newNode.parent.color === RED &&
newNode.color === RED
) {
const parent = newNode.parent;
const grandparent = parent.parent;
if (parent === grandparent.left) {
const uncle = grandparent.right;
if (uncle && uncle.color === RED) {
// Case 1: Recoloring
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
newNode = grandparent;
} else {
if (newNode === parent.right) {
// Case 2: Left rotation
newNode = parent;
this.leftRotate(newNode);
}
// Case 3: Right rotation
parent.color = BLACK;
grandparent.color = RED;
this.rightRotate(grandparent);
}
} else {
const uncle = grandparent.left;
if (uncle && uncle.color === RED) {
// Case 1: Recoloring
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
newNode = grandparent;
} else {
if (newNode === parent.left) {
// Case 2: Right rotation
newNode = parent;
this.rightRotate(newNode);
}
// Case 3: Left rotation
parent.color = BLACK;
grandparent.color = RED;
this.leftRotate(grandparent);
}
}
}
// Ensure the root node is always black
this.root.color = BLACK;
}
leftRotate(node) {
const rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (!node.parent) {
this.root = rightChild;
} else if (node === node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
}
rightRotate(node) {
const leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (!node.parent) {
this.root = leftChild;
} else if (node === node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
}
// Test the Red-Black Tree with the given input from the animation
const inputValues = [1, 2, 3, 4, 5, 6, 7, 8];
const rbTree = new RedBlackTree();
for (const value of inputValues) {
rbTree.insert(value);
}
console.log(rbTree.root);
public class RedBlackTree {
private static final String RED = "red";
private static final String BLACK = "black";
private static class Node {
int value;
Node left;
Node right;
Node parent;
String color;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
this.color = RED; // New nodes are always inserted as red
}
}
private Node root;
public void insert(int value) {
Node newNode = createNode(value);
if (root == null) {
newNode.color = BLACK;
root = newNode;
} else {
Node currentNode = root;
while (currentNode != null) {
if (value < currentNode.value) {
if (currentNode.left == null) {
setParent(newNode, currentNode);
currentNode.left = newNode;
break;
}
currentNode = currentNode.left;
} else if (value > currentNode.value) {
if (currentNode.right == null) {
setParent(newNode, currentNode);
currentNode.right = newNode;
break;
}
currentNode = currentNode.right;
} else {
return; // Node with the same value already exists, ignore duplicates
}
}
adjustAfterInsertion(newNode);
}
}
private Node createNode(int value) {
return new Node(value);
}
private void setParent(Node child, Node parent) {
child.parent = parent;
}
private void adjustAfterInsertion(Node newNode) {
while (newNode != root && newNode.parent.color.equals(RED) && newNode.color.equals(RED)) {
Node parent = newNode.parent;
Node grandparent = parent.parent;
if (parent == grandparent.left) {
Node uncle = grandparent.right;
if (uncle != null && uncle.color.equals(RED)) {
// Case 1: Recoloring
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
newNode = grandparent;
} else {
if (newNode == parent.right) {
// Case 2: Left rotation
newNode = parent;
leftRotate(newNode);
}
// Case 3: Right rotation
parent.color = BLACK;
grandparent.color = RED;
rightRotate(grandparent);
}
} else {
Node uncle = grandparent.left;
if (uncle != null && uncle.color.equals(RED)) {
// Case 1: Recoloring
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
newNode = grandparent;
} else {
if (newNode == parent.left) {
// Case 2: Right rotation
newNode = parent;
rightRotate(newNode);
}
// Case 3: Left rotation
parent.color = BLACK;
grandparent.color = RED;
leftRotate(grandparent);
}
}
}
// Ensure the root node is always black
root.color = BLACK;
}
private void leftRotate(Node node) {
Node rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left != null) {
rightChild.left.parent = node;
}
rightChild.parent = node.parent;
if (node.parent == null) {
root = rightChild;
} else if (node == node.parent.left) {
node.parent.left = rightChild;
} else {
node.parent.right = rightChild;
}
rightChild.left = node;
node.parent = rightChild;
}
private void rightRotate(Node node) {
Node leftChild = node.left;
node.left = leftChild.right;
if (leftChild.right != null) {
leftChild.right.parent = node;
}
leftChild.parent = node.parent;
if (node.parent == null) {
root = leftChild;
} else if (node == node.parent.right) {
node.parent.right = leftChild;
} else {
node.parent.left = leftChild;
}
leftChild.right = node;
node.parent = leftChild;
}
// Test the Red-Black Tree with the given input
public static void main(String[] args) {
int[] inputValues = {1, 2, 3, 4, 5, 6, 7, 8};
RedBlackTree rbTree = new RedBlackTree();
for (int value : inputValues) {
rbTree.insert(value);
}
// The Red-Black Tree is now constructed, and the root node is available.
System.out.println(rbTree.root);
}
}
const RED = 'red';
const BLACK = 'black';
class Node {
public $value;
public $left;
public $right;
public $parent;
public $color; // red = 'red', black = 'black'
public function __construct($value) {
$this->value = $value;
$this->left = null;
$this->right = null;
$this->parent = null;
$this->color = RED; // New nodes are always inserted as red
}
}
class RedBlackTree {
public $root = null;
public function insert($value) {
$newNode = $this->createNode($value);
if ($this->root === null) {
$newNode->color = BLACK;
$this->root = $newNode;
} else {
$currentNode = $this->root;
while ($currentNode !== null) {
if ($value < $currentNode->value) {
if ($currentNode->left === null) {
$this->setParent($newNode, $currentNode);
$currentNode->left = $newNode;
break;
}
$currentNode = $currentNode->left;
} else if ($value > $currentNode->value) {
if ($currentNode->right === null) {
$this->setParent($newNode, $currentNode);
$currentNode->right = $newNode;
break;
}
$currentNode = $currentNode->right;
} else {
// Node with the same value already exists, ignore duplicates
return;
}
}
$this->adjustAfterInsertion($newNode);
}
}
private function createNode($value) {
return new Node($value);
}
private function setParent($child, $parent) {
$child->parent = $parent;
}
private function adjustAfterInsertion($newNode) {
while ($newNode !== $this->root && $newNode->parent->color === RED && $newNode->color === RED) {
$parent = $newNode->parent;
$grandparent = $parent->parent;
if ($parent === $grandparent->left) {
$uncle = $grandparent->right;
if ($uncle !== null && $uncle->color === RED) {
// Case 1: Recoloring
$parent->color = BLACK;
$uncle->color = BLACK;
$grandparent->color = RED;
$newNode = $grandparent;
} else {
if ($newNode === $parent->right) {
// Case 2: Left rotation
$newNode = $parent;
$this->leftRotate($newNode);
}
// Case 3: Right rotation
$parent->color = BLACK;
$grandparent->color = RED;
$this->rightRotate($grandparent);
}
} else {
$uncle = $grandparent->left;
if ($uncle !== null && $uncle->color === RED) {
// Case 1: Recoloring
$parent->color = BLACK;
$uncle->color = BLACK;
$grandparent->color = RED;
$newNode = $grandparent;
} else {
if ($newNode === $parent->left) {
// Case 2: Right rotation
$newNode = $parent;
$this->rightRotate($newNode);
}
// Case 3: Left rotation
$parent->color = BLACK;
$grandparent->color = RED;
$this->leftRotate($grandparent);
}
}
}
// Ensure the root node is always black
$this->root->color = BLACK;
}
private function leftRotate($node) {
$rightChild = $node->right;
$node->right = $rightChild->left;
if ($rightChild->left !== null) {
$rightChild->left->parent = $node;
}
$rightChild->parent = $node->parent;
if ($node->parent === null) {
// Node was the root
$this->root = $rightChild;
} else if ($node === $node->parent->left) {
$node->parent->left = $rightChild;
} else {
$node->parent->right = $rightChild;
}
$rightChild->left = $node;
$node->parent = $rightChild;
}
private function rightRotate($node) {
$leftChild = $node->left;
$node->left = $leftChild->right;
if ($leftChild->right !== null) {
$leftChild->right->parent = $node;
}
$leftChild->parent = $node->parent;
if ($node->parent === null) {
// Node was the root
$this->root = $leftChild;
} else if ($node === $node->parent->right) {
$node->parent->right = $leftChild;
} else {
$node->parent->left = $leftChild;
}
$leftChild->right = $node;
$node->parent = $leftChild;
}
// Function to print the Red-Black Tree in-order
public function inorderTraversal($node) {
if ($node !== null) {
$this->inorderTraversal($node->left);
echo $node->value . ' ';
$this->inorderTraversal($node->right);
}
}
}
// Test the Red-Black Tree with the given input
$inputValues = [1, 2, 3, 4, 5, 6, 7, 8];
$rbTree = new RedBlackTree();
foreach ($inputValues as $value) {
$rbTree->insert($value);
}
// The Red-Black Tree is now constructed, and the root node is available.
print_r($rbTree->root);
?>