The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it is approximately \(\log n\) nodes high, allowing search in \(O(\log n)\) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee \(O(\log n)\) search.
Insert and delete are also performed in \(O(\log n)\) time. The 'fixup' operations where the balancing occurs after insert and delete have quite complex implementations as you will see below. This is because we need the properties of the red-black tree to hold otherwise it may not be balanced.
Complexity
| Operation | Average case | Worst case |
|---|---|---|
| Delete | \(O(\log n)\) | \(O(\log n)\) |
| Insert | \(O(\log n)\) | \(O(\log n)\) |
| Search | \(O(\log n)\) | \(O(\log n)\) |
| Space | \(O(n)\) | \(O(n)\) |
Representation
See binary search tree for information on representing a binary tree.
Properties
Here are the set of rules that a red-black tree must follow:
- Each node is either red or black
- The root node is black
- All leaf nodes (nil) are black
- Both children of every red node are black
- For each node, all paths from the node to descendant leaves contain the same number of black nodes
Operations
Rotation
Performing a left rotate and a right rotate on nodes is an important operation used in both delete and insert operations. Here is an illustration of the process:
Delete(a)
Delete performs a slightly modified binary search tree delete and then performs a fix-up function. Here are the cases that need to be fixed up if they occur.
- The deleted node a's sibling is red
- The deleted node a's sibling b is black and both of b's children and black
- The deleted node a's sibling b is black, b's left child is red and a's right child is black
- The deleted node a's sibling b is black and b's right child is red
Insert(a)
Insert performs a slightly modified binary search tree insert and then performs a fix-up function. Here are the cases that need to be fixed up if they occur.
- The inserted node a's uncle is red
- The inserted node a's uncle is black and a is a right child
- The inserted node a's uncle is black and a is a left child
Search(n)
For search we use the search operation on the regular binary search tree. Only now instead of having a worst case of \(O(n)\), it's \(O(\log n)\) as we balance the tree.
Code
public class RedBlackTree {
private TreeNode root;
public RedBlackTree() { }
public void insert(int key) {
TreeNode parent = null;
TreeNode node = root;
while (node != null && !node.isNilNode()) {
parent = node;
if (key < parent.getKey())
node = parent.getLeft();
else
node = parent.getRight();
}
if (parent == null) {
node = new TreeNode(key, null);
root = node;
} else {
node.setParent(parent);
node.setKey(key);
node.setNilNode(false);
node.setColor(TreeNode.Color.RED);
}
node.setColor(TreeNode.Color.RED);
insertFixup(node);
}
private void insertFixup(TreeNode node) {
while (node.getParent() != null &&
node.getGrandparent() != null &&
node.getParent().getColor() == TreeNode.Color.RED) {
if (node.getParent() == node.getGrandparent().getLeft()) {
TreeNode uncle = node.getGrandparent().getRight();
if (uncle.getColor() == TreeNode.Color.RED) {
node.getParent().setColor(TreeNode.Color.BLACK);
uncle.setColor(TreeNode.Color.BLACK);
node = node.getGrandparent();
node.setColor(TreeNode.Color.RED);
} else {
if (node == node.getParent().getRight()) {
node = node.getParent();
rotateLeft(node);
}
node.getParent().setColor(TreeNode.Color.BLACK);
node.getGrandparent().setColor(TreeNode.Color.RED);
rotateRight(node.getGrandparent());
}
} else if (node.getParent() == node.getGrandparent().getRight()) {
TreeNode uncle = node.getGrandparent().getLeft();
if (uncle.getColor() == TreeNode.Color.RED) {
node.getParent().setColor(TreeNode.Color.BLACK);
uncle.setColor(TreeNode.Color.BLACK);
node = node.getGrandparent();
node.setColor(TreeNode.Color.RED);
} else {
if (node == node.getParent().getLeft()) {
node = node.getParent();
rotateRight(node);
}
node.getParent().setColor(TreeNode.Color.BLACK);
node.getGrandparent().setColor(TreeNode.Color.RED);
rotateLeft(node.getGrandparent());
}
}
}
root.setColor(TreeNode.Color.BLACK);
}
private void rotateLeft(TreeNode x) {
TreeNode y = x.getRight();
x.setRight(y.getLeft());
if (y.getLeft() != null)
y.getLeft().setParent(x);
y.setParent(x.getParent());
if (x.getParent() == null)
root = y;
else {
if (x == x.getParent().getLeft())
x.getParent().setLeft(y);
else
x.getParent().setRight(y);
}
y.setLeft(x);
x.setParent(y);
}
private void rotateRight(TreeNode x) {
TreeNode y = x.getLeft();
x.setLeft(y.getRight());
if (y.getRight() != null)
y.getRight().setParent(x);
y.setParent(x.getParent());
if (x.getParent() == null)
root = y;
else {
if (x == x.getParent().getLeft())
x.getParent().setLeft(y);
else
x.getParent().setRight(y);
}
y.setRight(x);
x.setParent(y);
}
public void delete(int key) {
TreeNode node = search(key);
TreeNode y, x;
if (node.getLeft().isNilNode() || node.getRight().isNilNode())
y = node;
else
y = treeSuccessor(node);
if (y.getLeft() != null && !y.getLeft().isNilNode())
x = y.getLeft();
else
x = y.getRight();
x.setParent(y.getParent());
if (y.getParent() == null)
root = x;
else {
if (y == y.getParent().getLeft())
y.getParent().setLeft(x);
else
y.getParent().setRight(x);
}
if (y != node)
node.setKey(y.getKey());
if (y.getColor() == TreeNode.Color.BLACK)
deleteFixup(x);
}
private void deleteFixup(TreeNode node) {
while (node != root && node.getColor() == TreeNode.Color.BLACK) {
if (node == node.getParent().getLeft()) {
TreeNode w = node.getParent().getRight();
if (w.getColor() == TreeNode.Color.RED) {
w.setColor(TreeNode.Color.BLACK);
node.getParent().setColor(TreeNode.Color.RED);
rotateLeft(node.getParent());
}
if (w.getLeft().getColor() == TreeNode.Color.BLACK &&
w.getRight().getColor() == TreeNode.Color.BLACK) {
w.setColor(TreeNode.Color.RED);
node = node.getParent();
} else {
if (w.getRight().getColor() == TreeNode.Color.BLACK) {
w.getLeft().setColor(TreeNode.Color.BLACK);
w.setColor(TreeNode.Color.RED);
rotateRight(w);
w = node.getParent().getRight();
}
w.setColor(node.getParent().getColor());
node.getParent().setColor(TreeNode.Color.BLACK);
w.getRight().setColor(TreeNode.Color.BLACK);
rotateLeft(node.getParent());
node = root;
}
} else {
TreeNode w = node.getParent().getLeft();
if (w.getColor() == TreeNode.Color.RED) {
w.setColor(TreeNode.Color.BLACK);
node.getParent().setColor(TreeNode.Color.RED);
rotateRight(node.getParent());
}
if (w.getRight().getColor() == TreeNode.Color.BLACK &&
w.getLeft().getColor() == TreeNode.Color.BLACK) {
w.setColor(TreeNode.Color.RED);
node = node.getParent();
} else {
if (w.getLeft().getColor() == TreeNode.Color.BLACK) {
w.getRight().setColor(TreeNode.Color.BLACK);
w.setColor(TreeNode.Color.RED);
rotateLeft(w);
w = node.getParent().getLeft();
}
w.setColor(node.getParent().getColor());
node.getParent().setColor(TreeNode.Color.BLACK);
w.getLeft().setColor(TreeNode.Color.BLACK);
rotateRight(node.getParent());
node = root;
}
}
}
node.setColor(TreeNode.Color.BLACK);
}
private TreeNode treeSuccessor(TreeNode node) {
if (node.getRight() != null && !node.isNilNode())
return treeMinimum(node.getRight());
TreeNode successor = node.getParent();
while (successor != null && !successor.isNilNode() && node == successor) {
node = successor;
successor = node.getParent();
}
return successor;
}
private TreeNode treeMinimum(TreeNode node) {
while (!node.getLeft().isNilNode() && !node.isNilNode())
node = node.getLeft();
return node;
}
public TreeNode search(int key) {
if (root == null)
return null;
return search(key, root);
}
public TreeNode search(int key, TreeNode node) {
if (key == node.getKey())
return node;
if (key < node.getKey()) {
if (!node.leftExists())
return null;
return search(key, node.getLeft());
}
if (key > node.getKey()) {
if (!node.rightExists())
return null;
return search(key, node.getRight());
}
return null;
}
public String toString() {
if (root == null)
return "(empty)";
return root.toString();
}
}
Here is the TreeNode class. There is a little extra logic in it on top of the binary search tree implementation to fulfil the property "All leaf nodes (nil) are black".
public class TreeNode {
private final String nullNodeString = "_B";
private TreeNode left;
private TreeNode right;
private TreeNode parent;
private int key;
private boolean isNilNode;
private Color color;
public TreeNode(int key, TreeNode parent) {
this.key = key;
this.parent = parent;
this.color = Color.RED;
this.setNilNode(false);
}
// Constructor for nil leaf node
private TreeNode(TreeNode parent) {
this.parent = parent;
this.color = Color.BLACK;
this.setNilNode(true);
}
public String toString() {
if (isNilNode)
return nullNodeString;
return key + getColorCode() + " : { " +
(leftExists() ? left.toString() : nullNodeString) + " , " +
(rightExists() ? right.toString() : nullNodeString) + " }";
}
private String getColorCode() {
if (color == Color.BLACK)
return "B";
return "R";
}
public boolean leftExists() {
return left != null;
}
public boolean rightExists() {
return right != null;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public TreeNode getLeft() {
// Create nil leaf nodes lazily
if (left == null)
left = new TreeNode(this);
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
// Create nil leaf nodes lazily
if (right == null)
right = new TreeNode(this);
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public TreeNode getParent() {
return parent;
}
public TreeNode getGrandparent() {
if (parent != null && parent.getParent() != null)
return parent.getParent();
return null;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public Color getColor() {
return color;
}
public void setColor(Color color) {
this.color = color;
}
public boolean isNilNode() {
return isNilNode;
}
public void setNilNode(boolean isNilNode) {
this.isNilNode = isNilNode;
}
public enum Color {
BLACK,
RED
}
}