A red-black tree is a binary search tree in which each node is colored red or black such that
Example:
Red black trees do not necessarily have minimum height, but they never get really bad. The height is never greater than 2 log2(n), where n is the number of nodes.
A red black tree is a BST. Lookup in an RBT is just lookup in a BST. The colors don't matter.
The algorithm has three steps:
A double red problem is corrected with zero or more recolorings followed by zero or one restructuring.
Recolor whenever the sibling of a red node's red parent is red:
Restructure whenever the red child's red parent's sibling is black or null. There are four cases:
When you restructure, the root of the restructured subtree is colored black and its children are colored red.
Let's insert into an initially empty red-black tree, the following: 4 7 12 15 3 5 14 18 16 17. The tree takes shape like this:
The algorithm is in the code below. Have fun figuring it out.
Since Red Black Trees are just a kind of binary search tree, it makes sense to subclass:
package edu.lmu.cs.rtoal.collections;
import java.util.Comparator;
import java.awt.Color;
/**
* A simple red-black tree class.
*/
public class RedBlackTree extends BinarySearchTree {
/**
* Constructs an empty RedBlackTree that can only accept Comparables as
* items.
*/
public RedBlackTree() {
this(null);
}
/**
* Constructs an empty RedBlackTree that orders its items according to the
* given comparator.
*/
public RedBlackTree(Comparator c) {
super(c);
}
/**
* The nodes in a red-black tree store a color together with the actual data
* in the node.
*/
class Node extends LinkedBinaryTreeNode {
Color color = Color.black;
public Node(Object data) {
super(data);
}
}
/**
* Adds a single data item to the tree. If there is already an item in the
* tree that compares equal to the item being inserted, it is "overwritten"
* by the new item. Overrides BinarySearchTree.add because the tree needs to
* be adjusted after insertion.
*/
public void add(Object data) {
if (root == null) {
root = new Node(data);
}
BinaryTreeNode n = root;
while (true) {
int comparisonResult = compare(data, n.getData());
if (comparisonResult == 0) {
n.setData(data);
return;
} else if (comparisonResult < 0) {
if (n.getLeft() == null) {
n.setLeft(new Node(data));
adjustAfterInsertion((Node) n.getLeft());
break;
}
n = n.getLeft();
} else { // comparisonResult > 0
if (n.getRight() == null) {
n.setRight(new Node(data));
adjustAfterInsertion((Node) n.getRight());
break;
}
n = n.getRight();
}
}
}
/**
* Removes the node containing the given value. Does nothing if there is no
* such node.
*/
public void remove(Object data) {
Node node = (Node) nodeContaining(data);
if (node == null) {
// No such object, do nothing.
return;
} else if (node.getLeft() != null && node.getRight() != null) {
// Node has two children, Copy predecessor data in.
BinaryTreeNode predecessor = predecessor(node);
node.setData(predecessor.getData());
node = (Node) predecessor;
}
// At this point node has zero or one child
Node pullUp = leftOf(node) == null ? rightOf(node) : leftOf(node);
if (pullUp != null) {
// Splice out node, and adjust if pullUp is a double black.
if (node == root) {
setRoot(pullUp);
} else if (node.getParent().getLeft() == node) {
node.getParent().setLeft(pullUp);
} else {
node.getParent().setRight(pullUp);
}
if (isBlack(node)) {
adjustAfterRemoval(pullUp);
}
} else if (node == root) {
// Nothing to pull up when deleting a root means we emptied the tree
setRoot(null);
} else {
// The node being deleted acts as a double black sentinel
if (isBlack(node)) {
adjustAfterRemoval(node);
}
node.removeFromParent();
}
}
/**
* Classic algorithm for fixing up a tree after inserting a node.
*/
private void adjustAfterInsertion(Node n) {
// Step 1: color the node red
setColor(n, Color.red);
// Step 2: Correct double red problems, if they exist
if (n != null && n != root && isRed(parentOf(n))) {
// Step 2a (simplest): Recolor, and move up to see if more work
// needed
if (isRed(siblingOf(parentOf(n)))) {
setColor(parentOf(n), Color.black);
setColor(siblingOf(parentOf(n)), Color.black);
setColor(grandparentOf(n), Color.red);
adjustAfterInsertion(grandparentOf(n));
}
// Step 2b: Restructure for a parent who is the left child of the
// grandparent. This will require a single right rotation if n is
// also
// a left child, or a left-right rotation otherwise.
else if (parentOf(n) == leftOf(grandparentOf(n))) {
if (n == rightOf(parentOf(n))) {
rotateLeft(n = parentOf(n));
}
setColor(parentOf(n), Color.black);
setColor(grandparentOf(n), Color.red);
rotateRight(grandparentOf(n));
}
// Step 2c: Restructure for a parent who is the right child of the
// grandparent. This will require a single left rotation if n is
// also
// a right child, or a right-left rotation otherwise.
else if (parentOf(n) == rightOf(grandparentOf(n))) {
if (n == leftOf(parentOf(n))) {
rotateRight(n = parentOf(n));
}
setColor(parentOf(n), Color.black);
setColor(grandparentOf(n), Color.red);
rotateLeft(grandparentOf(n));
}
}
// Step 3: Color the root black
setColor((Node) root, Color.black);
}
/**
* Classic algorithm for fixing up a tree after removing a node; the
* parameter to this method is the node that was pulled up to where the
* removed node was.
*/
private void adjustAfterRemoval(Node n) {
while (n != root && isBlack(n)) {
if (n == leftOf(parentOf(n))) {
// Pulled up node is a left child
Node sibling = rightOf(parentOf(n));
if (isRed(sibling)) {
setColor(sibling, Color.black);
setColor(parentOf(n), Color.red);
rotateLeft(parentOf(n));
sibling = rightOf(parentOf(n));
}
if (isBlack(leftOf(sibling)) && isBlack(rightOf(sibling))) {
setColor(sibling, Color.red);
n = parentOf(n);
} else {
if (isBlack(rightOf(sibling))) {
setColor(leftOf(sibling), Color.black);
setColor(sibling, Color.red);
rotateRight(sibling);
sibling = rightOf(parentOf(n));
}
setColor(sibling, colorOf(parentOf(n)));
setColor(parentOf(n), Color.black);
setColor(rightOf(sibling), Color.black);
rotateLeft(parentOf(n));
n = (Node) root;
}
} else {
// pulled up node is a right child
Node sibling = leftOf(parentOf(n));
if (isRed(sibling)) {
setColor(sibling, Color.black);
setColor(parentOf(n), Color.red);
rotateRight(parentOf(n));
sibling = leftOf(parentOf(n));
}
if (isBlack(leftOf(sibling)) && isBlack(rightOf(sibling))) {
setColor(sibling, Color.red);
n = parentOf(n);
} else {
if (isBlack(leftOf(sibling))) {
setColor(rightOf(sibling), Color.black);
setColor(sibling, Color.red);
rotateLeft(sibling);
sibling = leftOf(parentOf(n));
}
setColor(sibling, colorOf(parentOf(n)));
setColor(parentOf(n), Color.black);
setColor(leftOf(sibling), Color.black);
rotateRight(parentOf(n));
n = (Node) root;
}
}
}
setColor(n, Color.black);
}
// The following helpers dramatically simplify the code by getting
// all the null pointer checking out of the adjustment methods.
private Color colorOf(Node n) {
return n == null ? Color.black : n.color;
}
private boolean isRed(Node n) {
return n != null && colorOf(n) == Color.red;
}
private boolean isBlack(Node n) {
return n == null || colorOf(n) == Color.black;
}
private void setColor(Node n, Color c) {
if (n != null)
n.color = c;
}
private Node parentOf(Node n) {
return n == null ? null : (Node) n.getParent();
}
private Node grandparentOf(Node n) {
return (n == null || n.getParent() == null) ? null : (Node) n
.getParent().getParent();
}
private Node siblingOf(Node n) {
return (n == null || n.getParent() == null) ? null : (n == n
.getParent().getLeft()) ? (Node) n.getParent().getRight()
: (Node) n.getParent().getLeft();
}
private Node leftOf(Node n) {
return n == null ? null : (Node) n.getLeft();
}
private Node rightOf(Node n) {
return n == null ? null : (Node) n.getRight();
}
}
For fun, I made my own viewer application. No animation, though:
package edu.lmu.cs.rtoal.collections;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextField;
import javax.swing.border.BevelBorder;
/**
* A little application that lets you interactively manipulate a
* binary search tree.
*/
public class RedBlackTreeViewer extends JFrame {
RedBlackTree tree = new RedBlackTree();
JFrame frame = new JFrame("Red Black Tree Viewer");
JTextField valueField = new JTextField(40);
JPanel buttonPanel = new JPanel();
BinaryTreePanel panel = new BinaryTreePanel(null, 40, 40);
JScrollPane displayArea = new JScrollPane();
JLabel messageLine = new JLabel();
/**
* An operation encapsulates a button and its action. The constructor
* will create a button, add it to a button panel, and register itself
* as a listener for the button. The listener first reads inputs from
* a textfield, then calls a subclass-supplied method with those inputs,
* then displays the resulting tree in the display area.
*/
private abstract class Operation implements ActionListener {
public Operation(String label) {
JButton button = new JButton(label);
buttonPanel.add(button);
button.addActionListener(this);
}
public void actionPerformed(ActionEvent event) {
String value = valueField.getText();
messageLine.setText("");
try {execute(value);} catch (Exception e) {e.printStackTrace();}
// Update the picture and return the focus to the text field. Select
// all the text in the textfield so it can easily be overwritten.
panel.setTree(tree.getRoot());
valueField.requestFocus();
valueField.selectAll();
}
protected abstract void execute(String value);
}
/**
* Constructs a viewer, laying out all the components in a
* very nice way, and constructs and registers all the
* operation objects.
*/
public RedBlackTreeViewer() {
JPanel valuePanel = new JPanel();
valuePanel.add(new JLabel("Value: "));
valuePanel.add(valueField);
JPanel controlPanel = new JPanel();
controlPanel.setLayout(new GridLayout(0, 1));
controlPanel.add(valuePanel);
controlPanel.add(buttonPanel);
// NOTE: Hardcoded preferred size! Fix this in the exercises.
panel.setPreferredSize(new Dimension(2048, 2048));
panel.setBackground(Color.white);
panel.setBorder(new BevelBorder(BevelBorder.LOWERED));
displayArea.setViewportView(panel);
frame.setBackground(Color.lightGray);
frame.getContentPane().add(controlPanel, "North");
frame.getContentPane().add(displayArea, "Center");
frame.getContentPane().add(messageLine, "South");
frame.pack();
new Operation("Add") {
protected void execute(String value) {
tree.add(value);}};
new Operation("Add All") {
protected void execute(String value) {
for (String s: value.split("\\s+")) tree.add(s);}};
new Operation("Lookup") {
protected void execute(String value) {
messageLine.setText("The value \"" + value + "\" is " +
(tree.contains(value) ? "" : "not ") + "found");}};
new Operation("Remove") {
protected void execute(String value) {
tree.remove(value);}};
}
/**
* Makes an application whose main window is a RedBlackTreeViewer.
*/
public static void main(String[] args) {
RedBlackTreeViewer viewer = new RedBlackTreeViewer();
viewer.frame.setSize(540, 480);
viewer.frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
viewer.frame.setVisible(true);
}
}