"Immutable" data structures is rather confusing name. Here it is a synonym for persistent data structure [1], which means that you operate on data structures by creating new "versions" of them, which share a lot of memory with the old versions. Parts of the program that refer to the old version see it as immutable.

[1] https://en.wikipedia.org/wiki/Persistent_data_structure