Yes you should be fine with immutable data structures when multithreading.
Note that in some cases there are read-only views of mutable structures
and the type itself won't tell it. For example:
http://dot.planet.ee/yeti/docs/latest/yeti.lang.std.html#tail
From the documentation:
"Notes
The tail function can be used on array. In this case a list view of array
is returned, consisting of all elements starting from index 1 (subsequent
applications of tail give views with increased start index). As the list
view still references to the original array, it will change when the array
is modified (use copy function to get an independent copy)."
Using those views without synchronization can obviously give undetermined
results, when some thread modifies the original array.
Another thing is that the standard library don't include immutable tree
maps currently.