Is an iteration on a F# map or set in-order traver

2019-06-27 13:25发布

问题:

AFAIK, F# Map and set are implemented as red-black trees, so I guess that an iteration on these would be in-order traversal. I did some test and the iteration results are always sorted. But I want to make it sure.

Is it in-order traversal?

回答1:

The documentation on MSDN is pretty good for figuring this out. For instance, the return value for Set.toSeq is "An ordered sequence of the elements of set." It looks like the answer to your question is yes, for both maps and sets.



回答2:

AFAIK, F# Map and set are implemented as red-black trees

AVL trees.

Is it in-order traversal?

Yes.