BinarySearchTree.java

Go to the documentation of this file.

package aud;
 
import aud.util.Graphvizable;
import aud.util.GraphvizDecorable;
import aud.util.GraphvizDecorator;
 
public class BinarySearchTree<Key extends Comparable<Key>,Value>
  implements Iterable<BinarySearchTree<Key,Value>.Cursor>,
             Graphvizable, GraphvizDecorable {
 
 
  public class Entry {
    final Key   key_;
    Value       value_;
 
    public Entry(Key key,Value value) {
      key_=key;
      value_=value;
    }
    public Key getKey() { return key_; }
    public Value getValue() { return value_; }
    public void setValue(Value value) { value_=value; }
 
    @Override public String toString() {
      return key_!=null ?
        (key_.toString()+
         (value_!=null? "=>"+value_.toString():"")) : "head";
    }
  }
 
 
 
  protected class Node extends BinaryTree<Entry> {
 
    BinarySearchTree<Key,Value> tree_ = null;
 
    Node(BinarySearchTree<Key,Value> tree,Key key,Value value) {
      super(new Entry(key,value));
      tree_=tree;
    }
 
    public Key getKey() { return getData().getKey(); }
    public Value getValue() { return getData().getValue(); }
    public void setValue(Value value) { getData().setValue(value); }
 
    @Override public GraphvizDecorator getDecorator() {
      return tree_.getDecorator();
    }
 
    Node next() {
      if (getRight()!=null) { // right -> descend left
        Node node=(Node) getRight();
        while (node.getLeft()!=null) { node=(Node) node.getLeft(); }
        return node;
      }
 
      Node node=(Node) getParent(); // ascend up ( -> right -> descend left )
      while (node!=head_ && compareKeys(node.getKey(),getKey())<0) {
        Node right=(Node) node.getRight();
        if (right!=null && right!=this &&
            compareKeys(right.getKey(),getKey())>=0) {
          node=right;
          while (node.getLeft()!=null) { node=(Node) node.getLeft(); }
          return node;
        }
        node=(Node) node.getParent();
      }
      return node!=head_ ? node : null;
    }
  }
 
  protected Node createNode(Key key,Value value) {
    return new Node(this,key,value);
  }
 
  protected Node head_;
 
  public BinarySearchTree() {
    head_ = createNode(null,null);
  }
 
  public boolean isEmpty() {
    return head_.getRight()==null;
  }
 
  protected int compareKeys(Key a,Key b) {
      if (a==null) return -1;
      if (b==null) return +1;
      else         return a.compareTo(b);
  }
 
  protected class LowerBound {
    protected Node node;
    protected Node parent;
    protected int  cmp;
 
    LowerBound(Node node,Node parent,int cmp) {
      this.node=node;
      this.parent=parent;
      this.cmp=cmp;
    }
    Value getValue() {
      return node!=null ? node.getValue() : null;
    }
  }
 
  protected LowerBound findLowerBound(Key key) {
    Node node=(Node) head_.getRight(), parent=head_;
    int  cmp=+1; // always larger than head_
 
    while (node!=null &&
           (cmp=compareKeys(key,node.getKey()))!=0) {
      parent=node;
      if (cmp<0)
        node=(Node) node.getLeft();
      else
        node=(Node) node.getRight();
    }
    return new LowerBound(node,parent,cmp);
  }
 
  public Value find(Key key) {
    return findLowerBound(key).getValue();
  }
 
  public class Cursor {
    final Node node_;
 
    Cursor(Node node) { assert(node!=head_); node_=node; }
 
    public Key getKey() { return node_.getKey(); }
    public Value getValue() { return node_.getValue(); }
    public void setValue(Value value) { node_.setValue(value); }
  }
 
  public Cursor findEntry(Key key) {
    Node node=findLowerBound(key).node;
    return node!=null ? new Cursor(node) : null;
  }
 
  public Cursor getMinimum() {
    Node node=(Node) head_.getRight(), parent=head_;
    while (node!=null) {
      parent=node;
      node=(Node) node.getLeft();
    }
    return parent!=head_ ? new Cursor(parent) : null;
  }
 
  public Cursor getMaximum() {
    Node node=(Node) head_.getRight(), parent=head_;
    while (node!=null) {
      parent=node;
      node=(Node) node.getRight();
    }
    return parent!=head_ ? new Cursor(parent) : null;
  }
 
  public static abstract class Visitor {
    abstract public void visit(String state,
                               String key, String value, String tikz);
  };
 
  public void visitPreorder(Visitor visitor) {
    visitPreorder(visitor, (Node) head_.getRight());
  }
 
  void visitPreorder(Visitor visitor, Node node) {
    visitor.visit("node-pre", null, null, null);
 
    if (node != null) {
      Value val = node.getValue();
      visitor.visit("node", node.getKey().toString(),
                    val != null ? val.toString() : null,
                    node.tikzNodeStyle());
 
      visitor.visit("left-down", null, null, null);
      visitPreorder(visitor, (Node) node.getLeft());
      visitor.visit("left-up", null, null, null);
 
      visitor.visit("right-down", null, null, null);
      visitPreorder(visitor, (Node) node.getRight());
      visitor.visit("right-up", null, null, null);
    }
 
    visitor.visit("node-post", null, null, null);
  }
 
  public class Iterator implements java.util.Iterator<Cursor> {
    java.util.Iterator<BinaryTree<Entry> > iter_;
 
    Iterator
      (java.util.Iterator<BinaryTree<Entry> >iter) {
      iter_=iter;
    }
 
    @Override public boolean hasNext() {
      return iter_!=null && iter_.hasNext();
    }
 
    @Override public Cursor next() {
      Node node=(Node) iter_.next();
      return new Cursor(node);
    }
    @Override public void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
  @Override public Iterator iterator() {
    return new Iterator
      (isEmpty() ? null : head_.getRight().inorder().iterator());
  }
 
 
  public Range range(Key begin,Key end) {
    if (isEmpty() || (end!=null && compareKeys(begin,end)>=0))
      return new Range(null,null);
 
    LowerBound lower=findLowerBound(begin);
    Node start=lower.node!=null ? lower.node : lower.parent;
    Node stop =null;
    if (end!=null) {
      lower=findLowerBound(end);
      stop=lower.node!=null ? lower.node : lower.parent;
    }
    return new Range(start,stop);
  }
 
  public class Range implements Iterable<Cursor> {
    final Node begin_;
    final Node end_;
 
    Range(Node begin,Node end) {
      begin_=begin;
      end_=end;
    }
 
    @Override public RangeIterator iterator() {
      return new RangeIterator(this);
    }
  }
 
  public class RangeIterator implements java.util.Iterator<Cursor> {
    Range range_;
    Node  node_;
 
    RangeIterator(Range range) {
      range_=range;
      node_=range_.begin_;
    }
 
    @Override public boolean hasNext() {
      return node_!=range_.end_;
    }
 
    @Override public Cursor next() {
      assert(node_!=null);
      Node cur=node_;
      node_=node_.next();
      return new Cursor(cur);
    }
    @Override public void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
  public Value insert(Key key,Value value) {
    LowerBound r=findLowerBound(key);
 
    if (r.node!=null) { // key exists in tree
      Value old=r.node.getValue();
      r.node.setValue(value);
      return old;
    }
    assert(r.cmp!=0);
    assert(r.parent!=null);
 
    Node node=createNode(key,value);
    Node old;
 
    if (r.cmp<0)
      old=(Node) r.parent.setLeft(node);
    else
      old=(Node) r.parent.setRight(node);
 
    onInsert(node); // notify via callback
 
    assert(old==null);
 
    return null;
  }
 
  protected void onInsert(Node node) {}
 
 
  public Value remove(Key key) {
    LowerBound r=findLowerBound(key);
    Node   node=r.node;
 
    if (node==null)
      return null; // no such node
 
    Value value=node.getValue();
 
    removeNode(node);
 
    return value;
  }
 
  protected void removeNode(Node node) {
    Node    parent=(Node) node.getParent();
    Node    child;             // update to parent
 
    assert(parent!=null);
    assert(parent.getLeft()==node || parent.getRight()==node);
 
    if (node.isLeaf())              // trivial case
      child=null;
    else if (node.getLeft()==null)  // 1 child
      child=(Node) node.getRight();
    else if (node.getRight()==null) // 1 child
      child=(Node) node.getLeft();
    else {                          // 2 children
      child=(Node) node.getRight();
      while (child.getLeft()!=null)
        child=(Node) child.getLeft();
 
      child.setLeft(node.getLeft());
      node.left_=null;     // because setXXX sets parent!
 
      Node p=(Node) child.getParent();
      if (p!=node) {
        p.setLeft(child.getRight());
        child.right_=null; // because setXXX sets parent!
        child.setRight(node.getRight());
      }
    }
 
    if (parent.getLeft()==node)
      parent.setLeft(child);
    else
      parent.setRight(child);
 
    onRemove();
  }
 
  protected void onRemove() {}
 
  protected Node restructure(Node grandchild) {
    assert(grandchild.getParent()!=head_);
    assert(grandchild.getParent().getParent()!=head_);
 
    Node child=(Node) grandchild.getParent();
    Node parent=(Node) child.getParent();
 
    // tri-node restructuring following [Goodrich andTamassia]
 
    Node x=grandchild, y=child, z=parent;
    boolean xLeft=(x==y.getLeft());
    boolean yLeft=(y==z.getLeft());
 
    Node a,b,c;       // find inorder traversal of x,y,z
    Node t0,t1,t2,t3;
 
    if (xLeft && yLeft) {
      a=x; b=y; c=z;
      t0=(Node) a.getLeft();
      t1=(Node) a.getRight();
      t2=(Node) b.getRight();
      t3=(Node) c.getRight();
    }
    else if (!xLeft && yLeft) {
      a=y; b=x; c=z;
      t0=(Node) a.getLeft();
      t1=(Node) b.getLeft();
      t2=(Node) b.getRight();
      t3=(Node) c.getRight();
    }
    else if (xLeft && !yLeft) {
      a=z; b=x; c=y;
      t0=(Node) a.getLeft();
      t1=(Node) b.getLeft();
      t2=(Node) b.getRight();
      t3=(Node) c.getRight();
    }
    else { // right/right
      a=z; b=y; c=x;
      t0=(Node) a.getLeft();
      t1=(Node) b.getLeft();
      t2=(Node) c.getLeft();
      t3=(Node) c.getRight();
    }
 
    return setupBalancedSubtree(z,a,b,c,t0,t1,t2,t3);
  }
 
  protected Node setupBalancedSubtree
    (Node z,Node a,Node b,Node c,Node t0,Node t1,Node t2,Node t3) {
 
    Node root=(Node) z.getParent();
    assert(root!=null);
 
    if (root.getLeft()==z)
      root.setLeft(b);
    else
      root.setRight(b);
 
    a.left_=a.right_=null; // avoid update of their parent
    a.setLeft(t0);
    a.setRight(t1);
 
    c.left_=c.right_=null;
    c.setLeft(t2);
    c.setRight(t3);
 
    b.left_=b.right_=null;
    b.setLeft(a);
    b.setRight(c);
 
    return b;
  }
 
  protected Node rotateLeft(Node node) {
    Node a=node;
    Node b=(Node) node.getRight(); assert(b!=null);
    Node c=(Node) b.getRight();    assert(c!=null);
 
    Node t0=(Node) a.getLeft();
    Node t1=(Node) b.getLeft();
    Node t2=(Node) c.getLeft();
    Node t3=(Node) c.getRight();
 
    Node z=a;
 
    return setupBalancedSubtree(z, a,b,c, t0,t1,t2,t3);
  }
 
  protected Node rotateRightLeft(Node node) {
    Node a=node;
    Node c=(Node) node.getRight(); assert(c!=null);
    Node b=(Node) c.getLeft();     assert(b!=null);
 
    Node t0=(Node) a.getLeft();
    Node t1=(Node) b.getLeft();
    Node t2=(Node) b.getRight();
    Node t3=(Node) c.getRight();
 
    Node z=a;
 
    return setupBalancedSubtree(z, a,b,c, t0,t1,t2,t3);
  }
 
  protected Node rotateRight(Node node) {
    Node c=node;
    Node b=(Node) node.getLeft(); assert(b!=null);
    Node a=(Node) b.getLeft();    assert(a!=null);
 
    Node t0=(Node) a.getLeft();
    Node t1=(Node) a.getRight();
    Node t2=(Node) b.getRight();
    Node t3=(Node) c.getRight();
 
    Node z=c;
 
    return setupBalancedSubtree(z, a,b,c, t0,t1,t2,t3);
  }
 
  protected Node rotateLeftRight(Node node) {
    Node c=node;
    Node a=(Node) node.getLeft(); assert(a!=null);
    Node b=(Node) a.getRight();   assert(b!=null);
 
    Node t0=(Node) a.getLeft();
    Node t1=(Node) b.getLeft();
    Node t2=(Node) b.getRight();
    Node t3=(Node) c.getRight();
 
    Node z=c;
 
    return setupBalancedSubtree(z, a,b,c, t0,t1,t2,t3);
  }
 
  public void restructure(char action,Key key) {
    if (key==null)
      throw new RuntimeException("invalid key 'null'");
 
    Node node=findLowerBound(key).node;
    if (node==null)
      throw new RuntimeException("no such node '"+key+"'");
 
    switch (action) {
    case '/':
      if (node.getLeft()==null || node.getLeft().getLeft()==null)
        throw new RuntimeException("missing node->left>left");
      decorator_.highlightNode(rotateRight(node));
      break;
    case '\\':
      if (node.getRight()==null || node.getRight().getRight()==null)
        throw new RuntimeException("missing node->left->right");
      decorator_.highlightNode(rotateLeft(node));
      break;
    case '>':
      if (node.getRight()==null || node.getRight().getLeft()==null)
        throw new RuntimeException("missing node->right->left");
      decorator_.highlightNode(rotateRightLeft(node));
      break;
    case '<':
      if (node.getLeft()==null || node.getLeft().getRight()==null)
        throw new RuntimeException("missing node->left->right");
      decorator_.highlightNode(rotateLeftRight(node));
      break;
    case '=':
      if (node.getParent()==head_ || node.getParent().getParent()==head_)
        throw new RuntimeException("missing node->parent->parent");
      decorator_.highlightNode(restructure(node));
    }
  }
 
  public class Decorator extends aud.util.SimpleDecorator {
    @Override public String getNodeDecoration(GraphvizDecorable object) {
      return object==head_ ? "shape=ellipse" : super.getNodeDecoration(object);
    }
    public void highlight(Key key) {
      highlightNode(findLowerBound(key).node);
    }
    public void mark(Key key) {
      markNode(findLowerBound(key).node);
    }
    public void unmark(Key key) {
      unmarkNode(findLowerBound(key).node);
    }
  }
 
  Decorator decorator_ = new Decorator();
 
  @Override public GraphvizDecorator getDecorator() {
    return decorator_;
  }
 
  @Override public String toDot() {
    return head_.toDot();
  }
 
  @Override public String toString() {
    String s="";
    if (!isEmpty()) {
      java.util.Iterator<?> ii=head_.getRight().inorder().iterator();
      while (ii.hasNext()) {
        s+=ii.next();
        if (ii.hasNext())
          s+=",";
      }
    }
    return s;
  }
 
  public String toText() {
    return isEmpty() ? "" : head_.getRight().toText();
  }
 
  public String toTikZ() {
    return isEmpty() ? "" : head_.getRight().toTikZ();
  }
 
  public void checkConsistency() {
    if (!isEmpty())
      checkConsistency((Node) head_.getRight());
  }
  protected void checkConsistency(Node node) {
    Node parent=(Node) node.getParent();
    assert(parent!=null);
    assert((Node) parent.getLeft()==node || (Node) parent.getRight()==node);
 
    if (parent==null)
      throw new RuntimeException("parent!=null");
    if ((Node) parent.getLeft()!=node && (Node) parent.getRight()!=node)
      throw new RuntimeException("invalid parent");
 
    if (node.getLeft()!=null)
      checkConsistency((Node) node.getLeft());
    if (node.getRight()!=null)
      checkConsistency((Node) node.getRight());
  }
 
  public static void main(String[] args) {
    BinarySearchTree<String,Object> tree=
      new BinarySearchTree<String,Object> ();
    System.out.println(tree);
 
    //String[] keys={"a","b","c","d","e","f","g"};
    //String[] keys={"d","b","f","a","c","e","g"};
    String[] keys={"a","b","d","c","g","f","e"};
 
 
    for (String key : keys)
      tree.insert(key,null);
 
    System.out.println(tree);
    System.out.println(tree.toText()); tree.checkConsistency();
 
    for (BinarySearchTree<String,Object>.Cursor c : tree)
      System.out.print(c.getKey());
    System.out.println();
 
    for (BinarySearchTree<String,Object>.Cursor c : tree.range("b","f"))
      System.out.print(c.getKey());
    System.out.println();
 
    keys=new String[]{"a","c","e","g"};
 
    for (String key : keys)
      tree.remove(key);
 
    System.out.println(tree);
    System.out.println(tree.toText());
  }
}