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.
TreeSet
and TreeMap
classes in
the Java Core API, as well as the Standard C++ sets and maps.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.collections; import java.awt.Color; import java.util.Comparator; /** * 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.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); } }