red black tree

1/1/13 9:26 PM

Page 1 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

import java.util.Set; import java.util.TreeSet;

/** * This is a skeleton of a red black tree. The basic functionality of a map backed by a binary search tree is provided, but * the red black handling has been left as an exercise. * * @author C. Andrews * * @param <K> the key type of the Map * @param <V> the value type associated with the key */ public class RBMap<K extends Comparable<K>, V> implements Map<K, V> { private static enum NodeColor {RED, BLACK}; BinaryTree<Pair> _root =null; Set<K> _keys;

public RBMap(){ _keys = new TreeSet<K>(); }

/** * Add an element to the map. * * If the key is already present in the map, the value is replaced with {@code value}. * * @param key the key to associate the value with * @param value the value being added to the map */ @Override public void put(K key, V value) { BinaryTree<Pair> tmp = new BinaryTree<Pair>(null, new Pair(key, value), null); BinaryTree<Pair> current = _root; BinaryTree<Pair> parent = null; _keys.add(key);

while (current != null){ parent = current; if (key.compareTo(current.getValue()._key) == 0){ // they are the same, just update the value current.getValue()._value = value; return; }else if (key.compareTo(current.getValue()._key) < 0){ // the key is smaller, go left current = current.getLeft(); }else{ // the key is larger, go right current = current.getRight(); } }

tmp.setParent(parent);

if (parent == null){ _root = tmp; }else{ if (key.compareTo(parent.getValue()._key) < 0){ parent.setLeft(tmp); }else{ parent.setRight(tmp); }

} // TODO rebalance the tree }

/** * Perform a lookup in the map based on the input key.

1/1/13 9:26 PM

Page 2 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

* * @param key the key associated with the value to be returned */ @Override public V get(K key) { BinaryTree<Pair> tmp = find(key);

if(tmp == null) return null; else return tmp.getValue()._value; }

/** * This private method finds nodes in the tree based on the key value. * * If the key exists in the map, this returns the node associated with it (not just the value). If the * key is not present, this returns null. This is used to implement get and remove. * * @param key the key that we are looking for * @return the node containing the key or null if the key is not present */ private BinaryTree<Pair> find(K key){ BinaryTree<Pair> current = _root;

while (current != null && key.compareTo(current.getValue()._key) != 0){ if (key.compareTo(current.getValue()._key) < 0){ current = current.getLeft(); }else{ current = current.getRight(); } }

if (current != null) return current; else return null; }

/** * Does the map contain the given key? * * @param key the key value to look for in the map * @return a boolean value indicating if the key is present */ @Override public boolean containsKey(K key) { return get(key) != null; }

/** * Remove the value associated with {@code key} from the map. * * Removes the key and value pair and returns the value. * * @param key the key for the value we are trying to remove * @return the value associated with the key or null if the key is not present in the map */ @Override public V remove(K key) { _keys.remove(key); BinaryTree<Pair> toRemove = find(key); BinaryTree<Pair> child; V value; if (toRemove == null){ return null; } value = toRemove.getValue()._value; if (toRemove.getLeft() != null && toRemove.getRight() != null){ BinaryTree<Pair>tmp = toRemove; NodeColor color = toRemove.getValue()._color;

1/1/13 9:26 PM

Page 3 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

toRemove = successor(toRemove); tmp.setValue( toRemove.getValue()); tmp.getValue()._color = color; }

if (toRemove.getLeft() != null){ child = toRemove.getLeft(); }else{ child = toRemove.getRight(); }

if (child != null){ child.setParent(toRemove.getParent()); } if (toRemove.getParent() == null){ _root = child; }else if (toRemove.getParent().getLeft() == toRemove){ toRemove.getParent().setLeft(child); }else{ toRemove.getParent().setRight(child); }

// TODO rebalance tree if necessary return value; }

/** * Return the set of all keys present in the map. * * @return the {@code Set} of all keys in the map */ @Override public Set<K> keySet() { return _keys; }

/** * A private helper that finds the immediate successor of a node in the tree. * * @param t the node we are trying to find the successor of * @return the immediate successor of the node or null if there isn't one */ private BinaryTree<Pair> successor(BinaryTree<Pair> t){ if (t.getRight() != null){ return minimum(t.getRight()); }

BinaryTree<Pair> parent = t.getParent();

while (parent != null && parent.getRight() == t){ t = parent; parent = parent.getParent(); } return parent; }

/** * A private helper that finds the minimum value in the tree rooted at t. * * This will fail if t is null since that would be an invalid operation. * * @param t the subtree we are exploring * @return the minimum value in t */ private BinaryTree<Pair> minimum(BinaryTree<Pair> t){ while (t.getLeft() != null){ t = t.getLeft(); } return t; }

1/1/13 9:26 PM

Page 4 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

/** * A private helper that finds the maximum value in the tree rooted at t. * * This will fail if t is null since that would be an invalid operation. * * @param t the subtree we are exploring * @return the maximum value in t */ @SuppressWarnings("unused") private BinaryTree<Pair> maximum(BinaryTree<Pair> t){ while (t.getRight() != null){ t = t.getRight(); } return t; }

/** * Returns a String representation of the tree. * * The representation is a preorder traversal of the tree in which each node is printed out in the * form of the key, followed by a colon and then a B or an R, all in square brackets. So a tree * with root 5 and children 3 and 9 would look like [5:B][3:R][9:R]. * */ public String toString(){ // TODO implement this method }

/** * Returns the black height of the tree. * * If there are any violations, this returns -1. * * @return the black height or -1 if there are any violations */ public int blackHeight(){ // TODO implement this method }

/** * Indicates if there is a red violation in the tree * * @return a boolean value that indicates if there is a red violation in the tree */ public boolean redViolation(){ // TODO implement this method }

/** * This is a simple wrapper class that provides the associations in the tree. * * @author C. Andrews * */ private class Pair{ private K _key; private V _value; private NodeColor _color;

private Pair(K key, V value){ _key = key; _value =value; _color = NodeColor.RED; // all new nodes are RED }

1/1/13 9:26 PM

Page 5 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

} }