RedBlackTree.java

Go to the documentation of this file.

package aud;
 
public class RedBlackTree<Key extends Comparable<Key>,Value>
  extends BinarySearchTree<Key,Value> {
 
  protected class RBNode extends BinarySearchTree<Key,Value>.Node {
    RBNode(RedBlackTree<Key,Value> tree,Key key,Value value) {
      super(tree,key,value);
      tree_=tree;
      red_=true; // insert red node
    }
 
    boolean red_;
 
    public boolean isRed() { return red_; }
 
    @Override protected String textLabel() {
      if (red_)
        return "["+getData().toString()+"]";
        // return "\033[91m"+getData().toString()+"\033[0m";
      else
        return getData().toString();
    }
 
    @Override protected String tikzNodeStyle() {
      return isRed() ? "[red]" : "[black]";
    }
  }
 
  @Override protected Node createNode(Key key,Value value) {
    return new RBNode(this,key,value);
  }
 
  public RedBlackTree() {
    super();
    decorator_ = new RedBlackDecorator();
  }
 
  private boolean isRed(RBNode node) {
    return node!=null ? node.isRed() : false;
  }
 
  private boolean isRoot(RBNode node) {
    assert(node!=null && node!=head_);
    return node.getParent()==head_;
  }
 
  @Override protected void onInsert(Node _node) {
    RBNode node=(RBNode) _node;
    node.red_=true;
 
    if (isRoot(node))
      node.red_=false;
    else
      remedyDoubleRed(node);
  }
 
  protected void remedyDoubleRed(RBNode node) {
    RBNode parent=(RBNode) node.getParent();
 
    assert(parent!=head_); // !isRoot(node)
 
    if (isRoot(parent) ||  // root is black!
        !parent.isRed())
      return;
 
    RBNode grandparent=(RBNode) parent.getParent();
 
    RBNode sibling=(RBNode) grandparent.getLeft();
    if (sibling==parent)
      sibling=(RBNode) grandparent.getRight();
 
    if (!isRed(sibling)) {           // restructuring
      RBNode b=(RBNode) restructure(node);
      b.red_=false;
      ((RBNode) b.getLeft()).red_=true;
      ((RBNode) b.getRight()).red_=true;
 
      onRestructuring();
    }
    else {                           // recoloring
      parent.red_=false;
      assert(sibling!=null) : "red node must exist";
      sibling.red_=false;
 
      assert(grandparent!=null && grandparent!=head_);
      if (!isRoot(grandparent)) {
        grandparent.red_=true;
        remedyDoubleRed(grandparent);
 
        onRecoloring();
      }
    }
  }
 
  protected void onRestructuring() {
  }
  protected void onRecoloring() {
  }
 
  @Override protected void checkConsistency(Node node) {
    super.checkConsistency(node);
 
    RBNode anode=(RBNode) node;
 
    if (anode.isRed()) {
      RBNode left=(RBNode) anode.getLeft();
      RBNode right=(RBNode) anode.getRight();
 
      assert(left ==null || !left .isRed());
      assert(right==null || !right.isRed());
 
      if ((left !=null && left .isRed()) ||
          (right!=null && right.isRed()))
        throw new RuntimeException("double red node at '"+anode+"'");
    }
  }
 
  @Override public Value remove(Key key) {
    throw new UnsupportedOperationException("RedBlackTree#remove");
  }
 
  public class RedBlackDecorator extends Decorator {
    @Override
    @SuppressWarnings("unchecked")
    public String getNodeDecoration(aud.util.GraphvizDecorable object) {
      String style=super.getNodeDecoration(object);
      if (style!=null || object==head_)
        return style;
      return ((RBNode) object).isRed() ?
         "style=filled,fillcolor=lightcoral,penwidth=1" :
         "style=filled,fillcolor=lightblue,penwidth=3";
    }
  }
 
  public static void main(String[] args) {
 
    //RedBlackTree<String,Object> tree=new RedBlackTree<String,Object> ();
    RedBlackTree<Integer,Object> tree=new RedBlackTree<Integer,Object> ();
 
    System.out.println(tree);
 
    //String[] keys={"a","b","c","d","e","f","g"};
    int[] keys={4,7,12,15,3,5,14,18,16,17,};
 
    //for (String key : keys) {
    for (int key : keys) {
      System.out.println("insert '"+key+"'");
      tree.insert(key,null);
      System.out.println(tree);
      System.out.println(tree.toText());
      tree.checkConsistency();
    }
 
    System.out.println(tree.toTikZ());
  }
}