What's the difference between `ImmutableSortedSet` and fsharp `Set`?

Question

BCL has introduced a group of Immutable Collections

I am wondering what's the difference between ImmutableSortedSet and the native FSharp Set? It seems that the performance signatures of both are similar. Also I saw somewhere that SortedSet is implemented as a Red Black Tree, so I guess ImmutableSortedSet does the same.

What is the internal implementation of fsharp map? Is is Red Black Tree as claimed here or AVL tree as found out here?

In addition, why MSDN documents don't state clear what the actual data structure is for the library collection? I know these are implementation details and are about to change. My point is that if they don't want to bind the library data type to a certain type of well known data structure, they should at least offer a summery of all the methods performance signatures in terms of complexity?

Answer 1

The F# Set and Map types are implemented with AVL trees.

I don't know about the MSDN documentation, you'd have to ask the F# team about that :)

In any case, Red-Black trees and AVL trees have the same computational complexity for their main operations. In practice, they have different performance characteristics which may lead you to choose one or the other for your specific application -- Red-Black trees have faster insert/delete because they don't need to do as much rebalancing of the tree, but retrieval is faster in AVL trees thanks to that additional balancing it performs for insert/delete. I imagine that is why AVL trees were chosen for the F# Map and Set implementations -- a Map/Set is usually created once (i.e., not modified) then queried repeatedly.

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

https://en.wikipedia.org/wiki/AVL_tree