When dealing with sets and maps, a lot depends on the specific data structure. Trees are quite common for associative containers, including sets and maps, so I'll deal purely with those.
For unbalanced binary trees, an insert operation operation works in two phases - the top-down part to find the insert point and the bottom-up part to modify (or create) the new tree.
The point here is that for each node, only one of the two subtrees contains the insertion point, and only that one subtree needs to be duplicated for a pure-functional tree insert. So the only new nodes needed are in a chain from the insert point back up to the root.
This means that assuming the tree is (accidentally) balanced, you have O(log n) new nodes for a single insert - the number of new nodes depends on the depth of the tree, not the total size.
A key assumption here is that nodes only store pointers to their children. In imperative languages, it's common for nodes to store pointers back to their parents. This means there are cyclic references, so the data structure must be copied as a whole. There are similar issues with threaded binary trees. The general rule is that when creating a new state, every strongly connected component must be copied as a whole - in practice, these data structures are rarely used in functional programming.
Of course parent links can be stored outside of the tree data structure, and the functional way to handle this is using a zipper. One issue (sometimes advantage, sometimes disadvantage) is that the zippers, like externally-stored parent links generally, refer to the particular state they were created to refer to, not to any newer state.
With balanced binary tree schemes such as AVL trees and red-black trees, there will be more complex changes due to rebalancing, but you still generally get the same O(log n) nodes copied per single item insert - unless you have parent links again.
Digital trees or tries use a tree data structure, but base that on the binary (or digital, at least) representation of the keys, not the ordering. For example, using base 10 digits, you might find the item for key 123 by starting at the root node, following child link 1, then child link 2, then child link 3. The depth of these trees is logarithmic in the maximum possible size because if you have an n-digit number and k distinct digits, you can form k^n digit strings so the maximum possible size is k^n. For example, with three decimal digits, you can only have 1000 different keys, so the maximum size is 1000 - 3 is the base 10 logarithm of 1000.
The story is similar to binary trees, except that you tend to have better constants (the tree branches more ways at each node) and you can often claim O(1) because the keys all have a fixed number of bits. This structure, with hashes for keys, can even be used to give a kind of hash table - with both advantages and disadvantages over the usual array-based hash tables from imperative programming.
There's an in-between structure called a ternary tree - basically a tree of binary trees, so you binary search for the first character of the string, then the next and so on. Again, it's still a tree, and provided there are no parent pointers or other cyclic references each insert should only have to copy O(log n) nodes.