Mira justo el método de borrado es el mas complejo porque hay que tener en cuenta que el nodo borrado no tenga hijos, y si tiene hay que re ordenar, por ejemplo supongamos que este es tu algoritmo:

public class NodoArbolBinario {
private int info = 0;
private NodoArbolBinario derecho = null;
private NodoArbolBinario izquierdo = null;

public NodoArbolBinario ( int x ) {
this.info = x;
this.derecho = null;
this.izquierdo = null;
}

public NodoArbolBinario getDerecho(){
return this.derecho;
}

public void setDerecho(NodoArbolBinario derecho){
this.derecho = derecho;
}


public int getInfo(){
return this.info;
}

public void setInfo(int info){
this.info = info;
}


public NodoArbolBinario getIzquierdo(){
return this.izquierdo;
}

public void setIzquierdo(NodoArbolBinario izquierdo){
this.izquierdo = izquierdo;
}
}

La clase tiene dos atributos del mismo tipo de la clase que indica los hijos, lo que tendrías que hacer para la búsqueda es ingresar el numero de nodo y así lo podes recuperar, el procedimiento de búsqueda es el mas importante porque lo vas a ocupar también para el borrado, para borrar tenes que introducir también el numero de nodo a borrar y una ves encontrado tenes que preguntar si tiene hijos, osea si NodoArbolBinario derecho y NodoArbolBinario izquierdo son nulos, si son nulos simplemente lo borras ya que no tiene hijos, si tiene solo un hijo, es decir que solo uno de los dos atributos no es nulo, lo borras y modificas el enlace del nodo anterior al borrado (ya sea NodoArbolBinario derecho o NodoArbolBinario izquierdo) para que apunte al hijo del borrado y el resto queda igual, si NodoArbolBinario derecho y NodoArbolBinario izquierdo no son nulos, es decir que tiene dos hijos acá la cosa se complica un poco mucho. No es un algoritmo fácil, en si el algoritmo es igual que el de una árbol binario de búsqueda al que se agregan los métodos de rotación que son los que mantienen el árbol equilibrado.

Tipicamente los métodos se llama RSI, RSD, RDI y RDD

Rotacion Simple Izquierda.
Rotacion Simple Derecha.
Rotacion Doble Izquierda.
Rotacion Doble Derecha.

Mas tarde si tengo tiempo te digo mas porque ahora no puedo, espero que te allá servido de algo.

Si podes deja el código fuente.

como dice @agustinpizzio es el mas complejo. Te dejo lo que hice:

 
    public void borrar(Integer elemento){ //  //recive el item que quiere ser borrado
        root = borrar(root, elemento); // llama a la funcion recursiva(root es el nombre de mi nodo raiz)
    }
    private Nodo borrar(Nodo r,Integer elemento){
       if(r.dato.equals(elemento)){ // caso base en el que el nodo r es el que se desea borrar
              if(r.derecho == null && r.izquierda == null){  // caso a en el que el nodo es hoja
                  r = null;                    
                  return r;             
              }
              if(r.derecho == null){  // caso b, tiene un solo hijo(izquierdo)
                 r = r.izquierda;
                 return r;    // ahora el hijo ocupa el lugar del padre y salimos del metodo
              }
              
              if(r.izquierda == null){  // caso b, tiene un solo hijo(derecho)
                 r = r.derecho;
                 return r;
              }
              //caso c; tiene dos hijos
              r.dato = encontrarMaximo(r.izquierda); // sera igual al nodo de mayor valor en el sub-arbol izquierdo
              r = ajuste(r, r.izquierda, r);
              return r;//el nodo igualado (de mayor valor) se debe eliminar para que no quede repetido
          }
       //si no era el nodo que se queria borrar se aprobecha su ordenamiento para buscarlo
       
       if(elemento.compareTo(r.dato)>0){ //si el elemento buscado es mayor al del nodo actual
          r.derecho = borrar(r.derecho, elemento); 
          return r; //lo busca recursivamente en los nodo "mayores"
       }
       //ultima opcion: que el elemento este en la izquierda
       r.izquierda = borrar(r.izquierda, elemento);
       return r;
}


//funcion que encuentra el maximo
private Integer encontrarMaximo(Nodo r){
     if(r.derecho == null) //si no hay un nodo con mayor valor retorna el valor del nodo actual
        return r.dato; 
     // sigue buscando en los nodos de mayor valor
     return encontrarMaximo(r.derecho);    
}
// funcion que elimina el nodo repetido y ajusta el arbol
private Nodo ajuste(Nodo padre,Nodo hijo , Nodo ances){
     if(hijo.derecho == null){
         if(padre.equals(ances)){
            padre.izquierda = hijo.izquierda; 
            return padre;
         } 
         padre.derecho = hijo.izquierda; 
         return padre;
     }        
     // sigue buscando en los nodos de mayor valor
     hijo = ajuste(hijo, hijo.derecho, ances);
     if(padre.equals(ances))
       padre.izquierda = hijo;
     else padre.derecho = hijo;
    return padre;
}



espero que te sirva, saludos

Disculpa por no contestar antes, es que estoy atareado con la universidad. No sé si todavía te será de utilidad pero hice un post de árboles binarios de búsqueda (que creo es lo que necesitas). Es probable que los códigos que doy en el post no te sirvan pues cada uno define un árbol en Java de diferente manera, sin embargo, espero que te sirvan los algoritmos.

http://www.taringa.net/posts/apuntes-y-monografias/14985195/Arboles-binarios-de-busqueda-en-Java.html

Hola queria deciros que estoy en la Universidad estudiando Ingenieria Informatica y me han servido de mucha ayuda vuestros posts para una asignatura de programacion en java. Ya de paso queria preguntaros si sabriais hacer un metodos para arboles binarios de busqueda que devuelva el número de elementos que hay en el árbol, en el nivel pasado como parámetro(int countElemsLevel(int level)) y otro que devuelvea el numero de operadores '+' que tiene el arbol de expresion (int countSum()). Muchas Gracias, Un Saludo!