Si borraste Google Play Store, puedes descargar el APK desde alguna de las páginas para descargar APKs de confianza e instalarlo de nuevo en tu móvil.