Hi, in the fourth part of my tree series, I want to talk about red-black trees. In the third part, we learned what an AVL tree is and what it does.
What is a Red-Black-Tree?
A red-black tree or RB tree or RB tree is a data structure that represents a self-balancing tree. It is a binary search tree. This tree, as the name suggests is colored red and black. Red and black trees guarantee logarithmic runtimes for the accesses . No tree can degenerate here. The color convention also guarantees that the tree with keys can never be higher than .
For example, a red and black tree looks like this:
Rules
The red and black tree has certain rules which must apply in order for this to be a valid red and black tree.
The rules are:
- Each node is either red or black.
- The root nodes and all nulls are always black.
- New nodes are always red.
- No consecutive red nodes can exist.
- If a node is red, its children are black.
- Each path from the root node to a leaf has the same number of black nodes.
If you want to see a red-black tree as an interactive animation, you can go to this link here.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
In the upper picture we see that the tree is a red-black tree. Because here we have not violated rule 1. Rule 2 we have not violated either. Rule 3 is also valid, as well as rules 4 and 5. If we now visit each leaf from the root, we have the same number of weak nodes.
If one of the rules is violated, we must make corrections.
To do this, we determine the uncle. If the uncle is red, we do a color flip. This means that we change the colors.
But if the uncle is black, we have to rotate.
After that the whole thing must look like this:
A small example, suppose we insert the number sequence into the tree. then later we violate rules 4 and 5. the fixing looks like this:
Suppose we now insert the 4 into the tree. Then we break the 4th rule again. Here we make a colorflip from the parent of the new node. However, after that we break rule 2, which says that the root node, as well as all nulls, are black. This is also fixed shortly and the tree is valid again. A picture clarifies the procedure.
Implement the RB-Tree
Ok, let's implement this. We take the simple binary search tree from Part 1 as a basis. First we extend the class Node by the attribute red, which stores true or false. In addition a pair of getters and setters as well as state queries.
package com.strider.dev;
public class Node
{
private int key;
private boolean red = false;
private Node left = null;
private Node right = null;
private Node parent = null;
public Node(int key)
{
this.key = key;
}
public int getKey()
{
return key;
}
public void setKey(int key)
{
this.key = key;
}
public Node getLeft()
{
return left;
}
public void setLeft(Node left)
{
this.left = left;
}
public Node getRight()
{
return right;
}
public void setRight(Node right)
{
this.right = right;
}
public Node getParent()
{
return parent;
}
public void setParent(Node parent)
{
this.parent = parent;
}
public boolean isRed()
{
return this.red;
}
public void setBlack()
{
this.red = false;
}
public void setRed()
{
this.red = true;
}
public void setRed(boolean x)
{
this.red = x;
}
public void print()
{
System.out.println(this.key);
if(this.red)
System.out.println("RED");
else
System.out.println("BLACK");
System.out.println("----------------------------------------------------------------");
}
}
The class has now implemented the new attribute and the appropriate methods. New here is the method print, which outputs our node value as well as the node color. The method setRed and setBlack, color the node either red or black. The method isRed, tells us if the node is red or black. That's all that needs to be done with the Node class.
If we now extend our Tree class, we must first extend the add method. The root node must be blackened after the insertion. The nodes that come after the root node must all be colored red. Wait a minute, wouldn't that break all the rules? Yes, but we create a method that corrects these violations. We simply call this method fixTree.
The add method now looks like this.
public void add(int key)
{
System.out.println("Adding Node " + key);
if(this.root == null)
{
this.root = new Node(key);
this.root.setParent(null);
this.root.setBlack();
return;
}
add(this.root, key);
}
private void add(Node root, int key)
{
if(root == null)
return;
if(key < root.getKey())
{
if(root.getLeft() == null)
{
Node n = new Node(key);
root.setLeft(n);
n.setParent(root);
n.setRed();
fixTree(this.root, n);
return;
}
add(root.getLeft(), key);
}
else
{
if(root.getRight() == null)
{
Node n = new Node(key);
root.setRight(n);
n.setParent(root);
n.setRed();
fixTree(this.root, n);
return;
}
add(root.getRight(), key);
}
}
We see that in the recursive method fixTree is called each time. This method, gets once the root and the new node passed.
We must now change all methods, which are to output the nodes, so that the method print of the current node is called. The methods (e.g. Inorder) now look like this:
public void inorder()
{
if(this.root == null)
return;
inorder(this.root);
}
private void inorder(Node root)
{
if(root.getLeft() != null)
{
inorder(root.getLeft());
}
root.print();
if(root.getRight() != null)
{
inorder(root.getRight());
}
}
Now we still have to implement the rotations. These are implemented somewhat differently than in the AVL tree. Here we have only a left rotation and a right rotation.
private void rotateRight(Node _root, Node node)
{
Node left = node.getLeft(); //left child of current node
node.setLeft(left.getRight());
if(node.getLeft() != null) //Right subtree of left child
node.getLeft().setParent(node);
left.setParent(node.getParent());
if(node.getParent() == null)
{
_root = left;
}
else if(node == node.getParent().getRight())
{
node.getParent().setParent(left);
}
else
{
node.getParent().setLeft(left);
}
left.setLeft(node);
node.setParent(left);
if(node.getParent() == _root)
{
this.root = left;
}
}
private void rotateLeft(Node _root, Node node)
{
Node right = node.getRight();
node.setRight(right.getLeft());
if(node.getRight() != null) //left subtree of right child
node.getRight().setParent(node);
right.setParent(node.getParent());
if(node.getParent() == null)
{
_root = right;
}
else if(node == node.getParent().getLeft())
{
node.getParent().setLeft(right);
}
else
{
node.getParent().setRight(right);
}
right.setLeft(node);
node.setParent(right);
if (node.getParent() == _root)
{
this.root = right;
}
}
The only thing missing now is the fixTree method, which respects our rules and corrects the tree if necessary.
private void fixTree(Node _root, Node newNode)
{
Node parent = null;
Node grandparent = null;
while((newNode != _root) && (newNode.isRed()) && (newNode.getParent().isRed()))
{
parent = newNode.getParent();
grandparent = newNode.getParent().getParent();
//Case A: Parent of newNode is left Child od grandparent
if(parent == grandparent.getLeft())
{
Node uncle = grandparent.getRight();
if(uncle != null && uncle.isRed())
{
//Case 1: The uncle is also red ---> recoloring
System.out.println("Recoloring (newNode is left child of parent)");
grandparent.setRed();
parent.setBlack();
uncle.setBlack();
newNode = grandparent;
}
else
{
//Case 2: newNode is the right child of its parent. --> LEFT-RIGHT-ROTATION
System.out.println("LEFT-RIGHT-ROTATION (newNode is left child of parent)");
if(newNode == parent.getRight())
{
rotateLeft(_root, parent);
newNode = parent;
parent = newNode.getParent();
}
rotateRight(_root, grandparent);
boolean swap = parent.isRed();
parent.setRed(grandparent.isRed());
grandparent.setRed(swap);
newNode = parent;
}
}
else
{
//Case B: parent of newNode is right child of grandparent
Node uncle = grandparent.getLeft();
if(uncle != null && uncle.isRed())
{
//Case 1: uncle of newNode is also red ---> recolor
System.out.println("Recoloring (newNode is right child of parent)");
grandparent.setRed();
parent.setBlack();
uncle.setBlack();
newNode = grandparent;
}
else
{
//Case 2: newNode is left Child of is parent --> RIGHT-LEFT-ROTATION
System.out.println("RIGHT-LEFT-ROTATION (newNode is right child of parent)");
if(newNode == parent.getLeft())
{
rotateRight(_root, parent);
newNode = parent;
parent = newNode.getParent();
}
rotateLeft(_root, grandparent);
boolean swap = parent.isRed();
parent.setRed(grandparent.isRed());
grandparent.setRed(swap);
newNode = parent;
}
}
}
System.out.println("Set root to black");
this.root.setBlack(); // The root is always black
}
If we look at the code, we see that the first thing we do here is to create the parent and the grandparent as placeholders.
From here on we make corrections until our tree is a valid red-black tree. Here we first determine the parent and grandparent. Here 2 cases are distinguished, once left and right subtree, of the grandparent.
In the left subtree, we determine our Uncle, which we need to consider the correction cases.
If the uncle is red, we perform a color flip. Otherwise, we perform a left-right rotation. Then we swap the colors of the parent and grandparent.
We do the same in the right subtree. At the end, the root node is skinned each time.
Black height
This is the red-black tree as a whole. Suppose we still want to determine the black height. The black level is the number of black nodes on a path. Since the rule applies here that each path must have the same number, it is sufficient if we simply walk the left branch and count all black nodes.
As a method, it looks like this:
public int blackHeight()
{
if(this.root == null)
return 0;
return blackHeight(this.root);
}
private int blackHeight(Node node)
{
if(node == null)
return 0;
int h = blackHeight(node.getLeft());
if(!node.isRed())
return h + 1;
return h;
}
With this, we can now determine the black level.
Run the RB-Tree
Let's run the whole thing. Since I didn't feel like thinking up new numbers, I created a small For loop, which inserts 10 nodes.
package com.strider.dev;
public class Main {
public static void main(String[] args) {
Tree T = new Tree();
for(int i = 0; i < 10; i++)
T.add(i);
System.out.println("\nInorder");
T.inorder();
System.out.println("\nPreorder");
T.preorder();
System.out.println("\nPostorder ");
T.postorder();
System.out.println("\nSHOW");
T.show();
System.out.println("Height: " + T.height());
System.out.println("BlackHeight: " + T.blackHeight());
}
}
If we just run the whole thing now, we get the following output.
Adding Node 0
Adding Node 1
Set root to black
Adding Node 2
RIGHT-LEFT-ROTATION (newNode is right child of parent)
Set root to black
Adding Node 3
Recoloring (newNode is right child of parent)
Set root to black
Adding Node 4
RIGHT-LEFT-ROTATION (newNode is right child of parent)
Set root to black
Adding Node 5
Recoloring (newNode is right child of parent)
Set root to black
Adding Node 6
RIGHT-LEFT-ROTATION (newNode is right child of parent)
Set root to black
Adding Node 7
Recoloring (newNode is right child of parent)
RIGHT-LEFT-ROTATION (newNode is right child of parent)
Set root to black
Adding Node 8
RIGHT-LEFT-ROTATION (newNode is right child of parent)
Set root to black
Adding Node 9
Recoloring (newNode is right child of parent)
Recoloring (newNode is right child of parent)
Set root to black
Inorder
0
BLACK
----------------------------------------------------------------
1
BLACK
----------------------------------------------------------------
2
BLACK
----------------------------------------------------------------
3
BLACK
----------------------------------------------------------------
4
BLACK
----------------------------------------------------------------
5
BLACK
----------------------------------------------------------------
6
BLACK
----------------------------------------------------------------
7
RED
----------------------------------------------------------------
8
BLACK
----------------------------------------------------------------
9
RED
----------------------------------------------------------------
Preorder
3
BLACK
----------------------------------------------------------------
1
BLACK
----------------------------------------------------------------
0
BLACK
----------------------------------------------------------------
2
BLACK
----------------------------------------------------------------
5
BLACK
----------------------------------------------------------------
4
BLACK
----------------------------------------------------------------
7
RED
----------------------------------------------------------------
6
BLACK
----------------------------------------------------------------
8
BLACK
----------------------------------------------------------------
9
RED
----------------------------------------------------------------
Postorder
0
BLACK
----------------------------------------------------------------
2
BLACK
----------------------------------------------------------------
1
BLACK
----------------------------------------------------------------
4
BLACK
----------------------------------------------------------------
6
BLACK
----------------------------------------------------------------
9
RED
----------------------------------------------------------------
8
BLACK
----------------------------------------------------------------
7
RED
----------------------------------------------------------------
5
BLACK
----------------------------------------------------------------
3
BLACK
----------------------------------------------------------------
SHOW
0
BLACK
----------------------------------------------------------------
1
BLACK
----------------------------------------------------------------
2
BLACK
----------------------------------------------------------------
3
BLACK
----------------------------------------------------------------
4
BLACK
----------------------------------------------------------------
5
BLACK
----------------------------------------------------------------
6
BLACK
----------------------------------------------------------------
7
RED
----------------------------------------------------------------
8
BLACK
----------------------------------------------------------------
9
RED
----------------------------------------------------------------
Height: 5
BlackHeight: 3
I hope I was able to give insights into red and black trees 😄