Eliminar datos de un Árbol AVL, sin que este pierda sus propiedades.


public void Eliminar(int dato){
	if(dato < this.raiz.info){
		Eliminar(this.raiz, this.raiz.getIzq(), dato);
	} else if(dato > this.raiz.info){
		Eliminar(this.raiz, this.raiz.getDer(), dato);
	} else {
		Eliminar_min(raiz, raiz, raiz.getIzq());
	}
}

private void Eliminar(Nodo padre, Nodo n, int dato){
	if(n == null){ 
		return;
	}
	if(n.info > dato){ 
		Eliminar(n, n.getIzq(), dato);
	} else if(n.info < dato){ 
		Eliminar(n, n.getDer(), dato);
	} else { -
                    if(n.isHoja()){
			n= null;
			if(dato>padre.info)
				padre.setDer(null);
			else
				padre.setIzq(null);
		} else if(n.getDer() == null){ 
			if(dato>padre.info)
				padre.setDer(n.getIzq());
			else
				padre.setIzq(n.getIzq());

			n = null; n.setIzq(null);
		} else if(n.getIzq() == null){
                       if(dato>padre.info)
				padre.setDer(n.getIDer());
			else
				padre.setIzq(n.getDer());

			n = null; n.setDer(null);
		} else { 
Eliminar_min(n, n, n.getIzq());
		}
	}
	Balancear(n);  
n.actualizarAltura();  
}

private void Eliminar_min(Nodo aux, Nodo padre, Nodo n){

	if(n.isHoja()){ 
		if(padre == aux){
			padre.setIzq(n);
		} else {
			padre.setDer(n);
		}
		aux.info = n.info;
		n = null;
	} else if(n.getDer()==null){
		aux.info = n.info;
padre.setDer(n.getIzq());
n.setIzq(null);
		n=null;	
	} else{
		Eliminar_min(aux, n, n.getDer());
	}

}



T(n) = C1 + Max(C2+T1(n/2), C3+T1(n/2)) + C4

T(n) = C1 + C2 + T(n/2) + C3

T(n) = C + T(n/2)

T(n) = 2C + T(n/4)

T(n) = 3C + T(n/8)

T(n) = kC + T(n/2k)                           n = 2k    ->  k = log2 n

T(n) = C*log2 n + T(n/n)

T(n) = C * log2 n + 1

O(log2 n)