Red Black Trees

Red-Black Trees are another type of Balanced Binary Search Trees with two
coloured nodes: Red and Black. It is a self-balancing binary search tree that
makes use of these colours to maintain the balance factor during the insertion
and deletion operations. Hence, during the Red-Black Tree operations, the
memory uses 1 bit of storage to accommodate the colour information of each
node
In Red-Black trees, also known as RB trees, there are different conditions to
follow while assigning the colours to the nodes.
 The root node is always black in colour.
 No two adjacent nodes must be red in colour.
 Every path in the tree (from the root node to the leaf node) must have the
same amount of black coloured nodes.
Even though AVL trees are more balanced than RB trees, with the balancing
algorithm in AVL trees being stricter than that of RB trees, multiple and faster
insertion and deletion operations are made more efficient through RB trees.

Fig: RB trees
Basic Operations of Red-Black Trees
The operations on Red-Black Trees include all the basic operations usually
performed on a Binary Search Tree. Some of the basic operations of an RB Tree
include −
 Insertion
  Deletion
 Search
Insertion operation
Insertion operation of a Red-Black tree follows the same insertion algorithm of
a binary search tree. The elements are inserted following the binary search
property and as an addition, the nodes are color coded as red and black to
balance the tree according to the red-black tree properties.
Follow the procedure given below to insert an element into a red-black tree by
maintaining both binary search tree and red black tree properties.
Case 1 − Check whether the tree is empty; make the current node as the root
and color the node black if it is empty.
Case 2 − But if the tree is not empty, we create a new node and color it red.
Here we face two different cases −
 If the parent of the new node is a black colored node, we exit the
operation and tree is left as it is.
 If the parent of this new node is red and the color of the parent's sibling is
either black or if it does not exist, we apply a suitable rotation and recolor
accordingly.
 If the parent of this new node is red and color of the parent's sibling is
red, recolor the parent, the sibling and grandparent nodes to black. The
grandparent is recolored only if it is not the root node; if it is the root
node recolor only the parent and the sibling.
Example
Let us construct an RB Tree for the first 7 integer numbers to understand the
insertion operation in detail −
The tree is checked to be empty so the first node added is a root and is colored
black.
Now, the tree is not empty so we create a new node and add the next integer
with color red,

The nodes do not violate the binary search tree and RB tree properties, hence
we move ahead to add another node.
The tree is not empty; we create a new red node with the next integer to it. But
the parent of the new node is not a black colored node,
The tree right now violates both the binary search tree and RB tree properties;
since parent's sibling is NULL, we apply a suitable rotation and recolor the
nodes.

Now that the RB Tree property is restored, we add another node to the tree −

The tree once again violates the RB Tree balance property, so we check for the
parent's sibling node color, red in this case, so we just recolor the parent and the
sibling.
We next insert the element 5, which makes the tree violate the RB Tree balance
property once again.

And since the sibling is NULL, we apply suitable rotation and recolor.
Now, we insert element 6, but the RB Tree property is violated and one of the
insertion cases need to be applied −

The parent's sibling is red, so we recolor the parent, parent's sibling and the
grandparent nodes since the grandparent is not the root node.
Now, we add the last element, 7, but the parent node of this new node is red.

Since the parent's sibling is NULL, we apply suitable rotations (RR rotation)
The final RB Tree is achieved.

Deletion operation
The deletion operation on red black tree must be performed in such a way that it
must restore all the properties of a binary search tree and a red black tree.
Follow the steps below to perform the deletion operation on the red black tree −
Firstly, we perform deletion based on the binary search tree properties.
Case 1 − If either the node to be deleted or the node's parent is red, just delete
it.
Case 2 − If the node is a double black, just remove the double black (double
black occurs when the node to be deleted is a black colored leaf node, as it adds
up the NULL nodes which are considered black colored nodes too)
Case 3 − If the double black's sibling node is also a black node and its child
nodes are also black in color, follow the steps below −
 Remove double black
 Recolor its parent to black (if the parent is a red node, it becomes black; if
the parent is already a black node, it becomes double black)
  Recolor the parent's sibling with red
 If double black node still exists, we apply other cases.
Case 4 − If the double black node's sibling is red, we perform the following
steps −
 Swap the colors of the parent node and the parent's sibling node.
 Rotate parent node in the double black's direction
 Reapply other cases that are suitable.
Case 5 − If the double black's sibling is a black node but the sibling's child node
that is closest to the double black is red, follows the steps below −
 Swap the colors of double black's sibling and the sibling's child in
question
 Rotate the sibling node is the opposite direction of double black (i.e. if
the double black is a right child apply left rotations and vice versa)
 Apply case 6.
Case 6 − If the double black's sibling is a black node but the sibling's child node
that is farther to the double black is red, follows the steps below −
 Swap the colors of double black's parent and sibling nodes
 Rotate the parent in double black's direction (i.e. if the double black is a
right child apply right rotations and vice versa)
 Remove double black
 Change the color of red child node to black.
Example
Considering the same constructed Red-Black Tree above, let us delete few
elements from the tree.
Delete elements 4, 5, 3 from the tree.
To delete the element 4, let us perform the binary search deletion first.

After performing the binary search deletion, the RB Tree property is not
disturbed, therefore the tree is left as it is.
Then, we delete the element 5 using the binary search deletion
But the RB property is violated after performing the binary search deletion, i.e.,
all the paths in the tree do not hold same number of black nodes; so we swap the
colors to balance the tree.

Then, we delete the node 3 from the tree obtained −

Applying binary search deletion, we delete node 3 normally as it is a leaf node.
And we get a double node as 3 is a black colored node.

We apply case 3 deletion as double black's sibling node is black and its child
nodes are also black. Here, we remove the double black, recolor the double
black's parent and sibling.
All the desired nodes are deleted and the RB Tree property is maintained.
Search operation
The search operation in red-black tree follows the same algorithm as that of a
binary search tree. The tree is traversed and each node is compared with the key
element to be searched; if found it returns a successful search. Otherwise, it
returns an unsuccessful search.
 Binomial Heap
The main application of Binary Heap is to implement a priority queue. Binomial
Heap is an extension of Binary Heap that provides faster union or merge
operation with other operations provided by Binary Heap.
A Binomial Heap is a collection of Binomial Trees
What is a Binomial Tree?
A Binomial Tree of order 0 has 1 node. A Binomial Tree of order k can be
constructed by taking two binomial trees of order k-1 and making one the
leftmost child of the other.
A Binomial Tree of order k the has following properties.
 It has exactly 2k nodes.
 It has depth as k.
 There are exactly kaiCi nodes at depth i for i = 0, 1, . . . , k.
 The root has degree k and children of the root are themselves Binomial
Trees with order k-1, k-2,.. 0 from left to right.
k = 0 (Single Node)
o
k = 1 (2 nodes)
[We take two k = 0 order Binomial Trees, and
make one as a child of other]
o
/
o
k = 2 (4 nodes)
[We take two k = 1 order Binomial Trees, and
make one as a child of other]
o
/ \
o o
/
o
k = 3 (8 nodes)
[We take two k = 2 order Binomial Trees, and
make one as a child of other]
o
/ |\
 o o o
/\ |
o oo
/
o
The following diagram is referred to form the 2nd Edition of the CLRS book.

Binomial Heap:
A Binomial Heap is a set of Binomial Trees where each Binomial Tree follows
the Min Heap property. And there can be at most one Binomial Tree of any
degree.
Examples Binomial Heap:
12------------10--------------------20
/ \ / |\
15 50 70 50 40
| /| |
30 80 85 65
|
 100
A Binomial Heap with 13 nodes. It is a collection of 3
Binomial Trees of orders 0, 2, and 3 from left to right.
10--------------------20
/ \ / |\
15 50 70 50 40
| /| |
30 80 85 65
|
100
A Binomial Heap with 12 nodes. It is a collection of 2
Binomial Trees of orders 2 and 3 from left to right.
Binary Representation of a number and Binomial Heaps
A Binomial Heap with n nodes has the number of Binomial Trees equal to the
number of set bits in the binary representation of n. For example, let n be 13,
there are 3 set bits in the binary representation of n (00001101), hence 3
Binomial Trees. We can also relate the degree of these Binomial Trees with
positions of set bits. With this relation, we can conclude that there are O(Logn)
Binomial Trees in a Binomial Heap with ‘n’ nodes.
Operations of Binomial Heap:
The main operation in Binomial Heap is a union(), all other operations mainly
use this operation. The union() operation is to combine two Binomial Heaps into
one. Let us first discuss other operations, we will discuss union later.
1. insert(H, k): Inserts a key ‘k’ to Binomial Heap ‘H’. This operation first
creates a Binomial Heap with a single key ‘k’, then calls union on H and
the new Binomial heap.
2. getting(H): A simple way to get in() is to traverse the list of the roots of
Binomial Trees and return the minimum key. This implementation
requires O(Logn) time. It can be optimized to O(1) by maintaining a
pointer to the minimum key root.
3. extracting(H): This operation also uses a union(). We first call getMin() to
find the minimum key Binomial Tree, then we remove the node and
create a new Binomial Heap by connecting all subtrees of the removed
minimum node. Finally, we call union() on H and the newly created
Binomial Heap. This operation requires O(Logn) time.
4. delete(H): Like Binary Heap, the delete operation first reduces the key to
minus infinite, then calls extracting().
5. decrease key(H): decrease key() is also similar to Binary Heap. We
compare the decreased key with its parent and if the parent’s key is more,
we swap keys and recur for the parent. We stop when we either reach a
node whose parent has a smaller key or we hit the root node. The time
complexity of the decrease key() is O(Logn).
Union operation in Binomial Heap:
Given two Binomial Heaps H1 and H2, union(H1, H2) creates a single
Binomial Heap.
6. The first step is to simply merge the two Heaps in non-decreasing order
of degrees. In the following diagram, figure(b) shows the result after
merging.
7. After the simple merge, we need to make sure that there is at most one
Binomial Tree of any order. To do this, we need to combine Binomial
Trees of the same order. We traverse the list of merged roots, we keep
track of three-pointers, prev, x, and next-x. There can be the following 4
cases when we traverse the list of roots.
—–Case 1: Orders of x and next-x are not the same, we simply move
ahead.
In the following 3 cases, orders of x and next-x are the same.
—–Case 2: If the order of next-next-x is also the same, move ahead.
—–Case 3: If the key of x is smaller than or equal to the key of next-x,
then make next-x a child of x by linking it with x.
—–Case 4: If the key of x is greater, then make x the child of next.
The following diagram is taken from the 2nd Edition of the CLRS book.
Time Complexity Analysis:

Operations Binary Heap Binomial Heap Fibonacci Heap

Procedure Worst-case Worst-case Amortized

Making Heap Θ(1) Θ(1) Θ(1)

Inserting a node Θ(log(n)) O(log(n)) Θ(1)

Finding
Θ(1) O(log(n)) O(1)
Minimum key

Extract-
Θ(log(n)) Θ(log(n)) O(log(n))
Minimum key

Union or
Θ(n) O(log(n)) Θ(1)
merging

Decreasing a Key Θ(log(n)) Θ(log(n)) Θ(1)

Deleting a node Θ(log(n)) Θ(log(n)) O(log(n))

How to represent Binomial Heap?

A Binomial Heap is a set of Binomial Trees. A Binomial Tree must be
represented in a way that allows sequential access to all siblings, starting from
the leftmost sibling (We need this in and extracting() and delete()). The idea is
to represent Binomial Trees as the leftmost child and right-sibling
representation, i.e., every node stores two pointers, one to the leftmost child and
the other to the right sibling.

import math
class Node:
def __init__(self, value):
self.value = value
self.parent = None
self.children = []
self.degree = 0
self.marked = False

class BinomialHeap:
def __init__(self):
self.trees = []
self.min_node = None
self.count = 0

def is_empty(self):
return self.min_node is None

def insert(self, value):

node = Node(value)
self.merge(BinomialHeap(node))

def get_min(self):
return self.min_node.value

def extract_min(self):
min_node = self.min_node
self.trees.remove(min_node)
 self.merge(BinomialHeap(*min_node.children))
self._find_min()
self.count -= 1
return min_node.value

def merge(self, other_heap):

self.trees.extend(other_heap.trees)
self.count += other_heap.count
self._find_min()

def _find_min(self):
self.min_node = None
for tree in self.trees:
if self.min_node is None or tree.value < self.min_node.value:
self.min_node = tree

def decrease_key(self, node, new_value):

if new_value > node.value:
raise ValueError("New value is greater than current value")
node.value = new_value
self._bubble_up(node)

def delete(self, node):

self.decrease_key(node, float('-inf'))
self.extract_min()

def _bubble_up(self, node):

parent = node.parent
 while parent is not None and node.value < parent.value:
node.value, parent.value = parent.value, node.value
node, parent = parent, node

def _link(self, tree1, tree2):

if tree1.value > tree2.value:
tree1, tree2 = tree2, tree1
tree2.parent = tree1
tree1.children.append(tree2)
tree1.degree += 1

def _consolidate(self):
max_degree = int(math.log(self.count, 2))
degree_to_tree = [None] * (max_degree + 1)

while self.trees:
current = self.trees.pop(0)
degree = current.degree
while degree_to_tree[degree] is not None:
other = degree_to_tree[degree]
degree_to_tree[degree] = None
if current.value < other.value:
self._link(current, other)
else:
self._link(other, current)
degree += 1
degree_to_tree[degree] = current
 self.min_node = None
self.trees = [tree for tree in degree_to_tree if tree is not None]

def __len__(self):
return self.count