convex hull with AVLTree, demo: http://studio.sketchpad.cc/sp/pad/view/ro.9Da4TMdejnS2I/latest

AVLIterator.pde

class AVLIterator {
  AVLTree tree;
  Node begin;
  Node end;
  Node current;

  AVLIterator(AVLTree t) {
    this.tree = t;
    current = begin = t.findMin(t.root);
    end = t.findMax(t.root);
  }

  Node getBegin() {
    current = begin;
    return current;
  }

  Node getEnd() {
    current = end;
    return current;
  }

  boolean hasNext() {
    return current!=end;
  }

  Node next() {
    if (hasNext()) {
      if (current.right!=null) {
        current = tree.findMin(current.right);
      }
      else if (current.parent!=null) {
        while (current==current.parent.right) {
          current=current.parent;
        }
        current=current.parent;
      }
      else {
        // error;
      }
    }
    else { 
      return null;
    }
    return current;
  }

  boolean hasPrevious() {
    return current!=begin;
  }

  Node previous() {
    if (hasPrevious()) {
      if (current.left!=null) {
        current = tree.findMax(current.left);
      }
      else if (current.parent!=null) {
        while (current==current.parent.left) {
          current=current.parent;
        }
        current=current.parent;
      }
      else {
        // error;
      }
    }
    else { 
      return null;
    }

    return current;
  }
}

AVLTree.pde

class Node {
  // content element
  Comparable element;
  // tree construction
  int height;
  Node left;
  Node right;
  Node parent;
  Node() {
    init(null, null, null, null);
  }

  Node(Comparable e) {
    init(e, null, null, null);
  }

  Node(Comparable e, Node parent) {
    init(e, parent, null, null);
  }

  Node(Comparable e, Node parent, Node left, Node right) {
    init(e, parent, left, right);
  }

  void init(Comparable e, Node parent, Node left, Node right) {
    this.element = e;
    this.parent = parent;
    this.left = left;
    this.right = right;
    this.height = 0;
  }
}

class AVLTree {

  Node root;
  int size;

  AVLTree() {
    init(null);
  }

  AVLTree(Node r) {
    init(r);
  }

  private void init(Node r) {
    this.root =r;
    size = 0;
  }

  int height(Node node) {
    return node==null?0:node.height;
  }

  boolean isEmpty() {
    return root == null;
  }
  
  void makeEmpty() {
    root = null;
    size = 0;
  }

  Node findMin(Node node) {
    if (node==null) return null;
    else if (node.left==null) return node;
    else return findMin(node.left);
  }

  Node findMax(Node node) {
    if (node==null) return null;
    else if (node.right==null) return node;
    else return findMax(node.right);
  }

  void printTree() {
    if (isEmpty()) {
      println("Empty tree");
      return;
    } 
    else {
      fill(0);
      printTree(root, null);
    }
  }

  void printTree(Node node, Node parent) {
    if (node != null) {
      Point2D p = (Point2D)node.element;
      noStroke();
      ellipse(p.x, p.y, 7, 7);
      if (parent != null) {
        Point2D q = (Point2D)parent.element;
        stroke(map(parent.height,10,0,128,200));
        line(q.x, q.y, p.x, p.y);
        stroke(32);
        noFill();
        ellipse(q.x,q.y,9,9);
      }
      fill(255, 0, 0);
      printTree(node.left, node);
      fill(0, 255, 0);
      printTree(node.right, node);
      fill(255);
    }
  }

  void insert(Comparable element) {
    root = insert(element, root, null);
  }

  Node insert(Comparable element, Node node, Node parent) {
    if (node == null) {
      size++;
      node = new Node(element, parent);
    } 
    else if (element.compareTo(node.element) < 0) {
      node.left = insert(element, node.left, node);
      if (height(node.left) - height(node.right) == 2) {
        if (element.compareTo(node.left.element) < 0) {
          // LL
          node = rotateWithLeftChild(node);
        } 
        else {
          // LR
          node = doubleRotateWithLeftChild(node);
        }
      }
    } 
    else if (element.compareTo(node.element) > 0) {
      node.right = insert(element, node.right, node);
      if (height(node.right) - height(node.left) == 2) {
        if (element.compareTo(node.right.element) < 0) {
          // RL
          node = doubleRotateWithRightChild(node);
        } 
        else {
          // RR
          node =rotateWithRightChild(node);
        }
      }
    } 
    else {
      // duplicate;
    }
    node.height = max(height(node.left), height(node.right)) + 1;
    return node;
  }

  Node rotateWithLeftChild(Node k2) {
    Node k1 = k2.left;
    if(k1.right!=null)
      k1.right.parent = k2;
    k2.left = k1.right;
    k1.parent = k2.parent;
    k2.parent = k1;
    k1.right = k2;
    k2.height = max(height(k2.left), height(k2.right)) + 1;
    k1.height = max(height(k1.left), k2.height) + 1;
    return k1;
  }

  Node rotateWithRightChild(Node k1) {
    Node k2 = k1.right;
    if(k2.left!=null)
      k2.left.parent = k1;
    k1.right = k2.left;
    k2.parent = k1.parent;
    k1.parent = k2;
    k2.left = k1;
    k1.height = max(height(k1.left), height(k1.right)) + 1;
    k2.height = max(k1.height, height(k2.right)) + 1;
    return k2;
  }

  Node doubleRotateWithLeftChild(Node k3) {
    k3.left = rotateWithRightChild(k3.left);
    return rotateWithLeftChild(k3);
  }

  Node doubleRotateWithRightChild(Node k3) {
    k3.right = rotateWithLeftChild(k3.right);
    return rotateWithRightChild(k3);
  }
}

convex_hull_avltree.pde

import java.util.Iterator;
AVLTree pointSet;
AVLIterator iterator;
ArrayList<Point2D> convex_hull, convex_hull_up, convex_hull_down;

void setup() {
  size(640, 480);
  // initial AVLTree
  pointSet = new AVLTree();
  convex_hull = new ArrayList<Point2D>();
  convex_hull_up = new ArrayList<Point2D>();
  convex_hull_down = new ArrayList<Point2D>();
}

void draw() {
}

void mouseClicked() {
  background(200);
}

void mousePressed() {
  pointSet.makeEmpty();
}

void mouseDragged() {
  Point2D p = new Point2D(mouseX, mouseY);
  pointSet.insert(p);
  point(mouseX, mouseY);
}

void mouseReleased() {
  if (pointSet.isEmpty())
    return;

//  strokeWeight(1);
  pointSet.printTree();

  convex_hull.clear();
  convex_hull_up.clear();
  convex_hull_down.clear();

  iterator = new AVLIterator(pointSet);
  Node i = iterator.getBegin();
  Point2D p = (Point2D)i.element;
  convex_hull_up.add(p);
  while (iterator.hasNext ()) {
    i = iterator.next();
    p = (Point2D)i.element;
    convex_hull_up.add(p);
    int total;
    while ( (total = convex_hull_up.size ())>2) {
      if (isOnTheRight(convex_hull_up.get(total-1), convex_hull_up.get(total-2), convex_hull_up.get(total-3))) {
        break;
      }
      convex_hull_up.remove(total-2);
    }
  }

  p = (Point2D)i.element;
  ellipse(p.x, p.y, 10, 10);
  convex_hull_down.add(p);
  while (iterator.hasPrevious ()) {
    i = iterator.previous();
    p = (Point2D)i.element;
    convex_hull_down.add(p);
    int total;
    while ( (total = convex_hull_down.size ())>2) {
      if (isOnTheRight(convex_hull_down.get(total-1), convex_hull_down.get(total-2), convex_hull_down.get(total-3))) {
        break;
      }
      convex_hull_down.remove(total-2);
    }
  }

  convex_hull.addAll(convex_hull_up);
  convex_hull.addAll(convex_hull_down);
  fill(255);
//  strokeWeight(2);
stroke(0);
  Iterator<Point2D> iter = convex_hull.iterator();
  Point2D lastPoint = null;
  while (iter.hasNext ()) {
    Point2D point = iter.next();
    if (lastPoint!=null)
      line(lastPoint.x, lastPoint.y, point.x, point.y);
    lastPoint = point;
  }
}

boolean isOnTheRight(Point2D p, Point2D q, Point2D r)
{
  return q.x*r.y+p.x*q.y+p.y*r.x-q.y*r.x-p.x*r.y-p.y*q.x>0;
}

void keyReleased() {
  switch(key) {
  case 'r':
    mousePressed();
    mouseClicked();
    break;
  case'a':
    mouseClicked();
    mouseDragged();
    mouseReleased();
    break;
  case 's':
    mouseReleased();
    break;
  case 'c':
    mouseClicked();
    break;
  case 'b':
    println("for breakpoint");
    break;
  }
}

Point2D.pde

class Point2D implements Comparable {
  float x;
  float y;
  Point2D(float x, float y) {
    this.x = x;
    this.y = y;
  }

  int compareTo(Object o) {
    return compareToPoint2D((Point2D)o);
  }

  private int compareToPoint2D(Point2D p) {
    if (abs(this.x-p.x)<0.001) {
      if (abs(this.y-p.y)<0.001)
        return 0; else  
        return this.y<p.y?-1:1;
    }
    return this.x<p.x?-1:1;
  }

  String toString() {
    return "("+x+", "+y+")";
  }
}