Partial and probably not correct prototype below

import java.util.*;

public class LFTreeSet
{
   class Sequence {
       int value;
       synchronized int next() {
           value++;
           return value;
       }
           
   }
       
   Sequence sequence = new Sequence();
   
   class Node {
       
       Object value;
       int height;                 // tree height
       int lheight;                // left subtree height
       int rheight;                // right subtree height
       volatile Node ltree;        // left subtree
       volatile Node rtree;        // right subtree
       
       int unique;                 // unique node id;
       int cost;                   // node cost
       int weight;                 // node weight
       
       void init(Object o, Node lnode, Node rnode) {
           value = o;
           if (lnode != null) {
               ltree = lnode;
               lheight = lnode.height;
           }
           else {
               ltree = null;
               lheight = 0;
           }
           rtree = rnode;
           if (rnode != null) {
               rtree = rnode;
               rheight = rnode.height;
           }
           else {
               rtree = null;
               rheight = 0;
           }
           height = maximum(lheight, rheight) + 1;
           
           unique = sequence.next();   // assign unique sequence number
       }
       
       Node(Object o) {
           init(o, null, null);
       }
       
       Node(Object o, Node lnode, Node rnode) {
           init(o, lnode, rnode);
       }
       
   }

   Comparator comparator;          // comparator
   volatile Node root;             // tree root node
   
   //=========================================================================
   // Private Methods
   //=========================================================================
   
   //-------------------------------------------------------------------------
   // maximum --
   //-------------------------------------------------------------------------
   static int maximum(int x, int y) {
       if (x > y) return x; else return y;
   }
       
   //-------------------------------------------------------------------------
   // addNode --
   //
   //  returns:
   //      subtree height or
   //      0 if tree already contains node
   //      
   //-------------------------------------------------------------------------
   Node addNode(Node z, Object o)
   throws ClassCastException {
       Node p;
       int rc;
       
       if (z == null) {
           comparator.compare(o, o);   // force ClassCastException if wrong class
           return new Node(o);
       }
       
       rc = comparator.compare(o, z.value);
       if (rc < 0) {
           z.ltree = addNode(z.ltree, o);
           z.lheight = z.ltree.height;
       }
           
       else if (rc > 0) {
           z.rtree = addNode(z.rtree, o);
           z.rheight = z.rtree.height;
       }
       
       // calculate height
       z.height = maximum(z.lheight, z.rheight) + 1;

       return z;
   }

   
   //-------------------------------------------------------------------------
   // maxNode --
   //
   //-------------------------------------------------------------------------
   static Node maxNode(Node z) {
       while (z.rtree != null)
           z = z.rtree;
       return z;
   }
   
   
   //-------------------------------------------------------------------------
   // pcloneMinusMaxNode -- partial copy
   //
   // static won't work?
   //-------------------------------------------------------------------------
   Node pcloneMinusMaxNode(Node z) {
       Node p;
       
       if (z.rtree == null)
           return z.ltree;
       else
           return new Node(z.value,
                           z.ltree,
                           pcloneMinusMaxNode(z.rtree));
   }
   
   
   //-------------------------------------------------------------------------
   // rotateRight --
   //
   //-------------------------------------------------------------------------
   Node rotateRight(Node p) {
       if (p == null)
           return null;
           
       if (p.ltree == null)
           return p;
           
       if (p.rtree == null)
           p.rtree = new Node(p.value);
       else
           addNode(p.rtree, p.value);
           
       return new Node(maxNode(p.ltree).value,
                         pcloneMinusMaxNode(p.ltree),
                         p.rtree);
       
   }
   
   
   //=========================================================================
   // Public Constructors and Methods
   //=========================================================================
   
   //-------------------------------------------------------------------------
   // LFTreeSet -- ctor
   //
   //
   //-------------------------------------------------------------------------
   public LFTreeSet(Comparator comparator) {
       this.comparator = comparator;
       root = null;
   }
   
   //-------------------------------------------------------------------------
   // add --
   //
   //-------------------------------------------------------------------------
   public boolean add(Object o)
   throws ClassCastException {
       
       if (contains(o)) {
           return false;
       }
           
       else {
           root = addNode(root, o);
           return true;
       }
           
   }
   
   
   //-------------------------------------------------------------------------
   // remove --
   //
   //-------------------------------------------------------------------------
   public boolean remove(Object o)
   throws ClassCastException {
       Node p, p2, p3;
       int n;
       
       // find parent node
       
       p2 = null;
       p = root;
       while (p != null && ((n = comparator.compare(o, p.value)) != 0)) {
           p2 = p;
           if (n < 0)
               p = p.ltree;
           else
               p = p.rtree;
       }
       
       if (p == null)
           return false;           // not found
       
       // leaf node
       if (p.ltree == null && p.rtree == null)
           p3 = null;
       
       // single subtree
       else if (p.ltree == null)
           p3 = p.rtree;
           
       // single subtree
       else if (p.rtree == null)
           p3 = p.ltree;
           
       // new subtree with root node replaced by max node from left subtree
       else
           p3 = new Node(maxNode(p.ltree).value,
                         pcloneMinusMaxNode(p.ltree),
                         p.rtree);
                           
       //
       // store subtree
       //
       if (p2 == null)
           root = p3;
       else if (p2.ltree == p) {
           p2.ltree = p3;
           p2.lheight = p3.height;
           p2.height = maximum(p2.lheight, p2.rheight) + 1;
       }
       else {
           p2.rtree = p3;
           p2.rheight = p3.height;
           p2.height = maximum(p2.lheight, p2.rheight) + 1;
       }
             
       return true;
   }
   
   
   //-------------------------------------------------------------------------
   // contains --
   //
   //-------------------------------------------------------------------------
   public boolean contains(Object o)
   throws ClassCastException {
       Node p;
       int n;
       
       p = root;
       while (p != null && ((n = comparator.compare(o, p.value)) != 0)) {
           if (n < 0)p = p.ltree; else p = p.rtree;
       }
       
       return (p != null);
   }
   
   
   //-------------------------------------------------------------------------
   // comparator --
   //
   //-------------------------------------------------------------------------
   public Comparator comparator() {
       return comparator;
   }
   
   
   //=========================================================================
   // Debug Methods
   //=========================================================================
   
   //-------------------------------------------------------------------------
   //-------------------------------------------------------------------------
   int nodeCost(Node p) {
       if (p == null) return 0;
       return p.cost = ((nodeCost(p.ltree) + nodeCost(p.rtree))*2 + 1);
   }
   
   //-------------------------------------------------------------------------
   //-------------------------------------------------------------------------
   int nodeWeight(Node p) {
       if (p == null) return 0;
       return p.weight = (nodeWeight(p.ltree) + nodeWeight(p.rtree) + 1);
   }
   
   
   //-------------------------------------------------------------------------
   //-------------------------------------------------------------------------
   public void rotateTreeRight() {
       root = rotateRight(root);
   }
               
       
}

//--//

Rather a dangerous assumption.  As I read the code, you need more
synchronisation than you have (almost none).  There doesn't seem to be anything
to ensure that the height values are propagated correctly (I saw your comment
that they aren't used), nor the costs and weights, nor the "value" of the node,
nor the memory pointed /to/ by value.

Incidentally, the stuff in java.lang.concurrent.atomic might be useful if you
don't already know about it.

   -- chris

...

....

...

Why not do a skip-list instead?  A skiplist
- has the same performance characteristics as a tree (O(logN) lookup,
etc)
- is easier to code
- can be both reader and writer lock free

Tony