[lozenge]

But there's nothing preventing Microsoft from changing SortedDictionary to use an AVL tree. The asymptotic complexity of all the operations would be the same.

[wmccullough]

I'm actually tempted to do a PR against dotnet to see if they'd accept this improvement. My guess is that just like with Roslyn, customers have come to count on the implementation, bugs and all, and it may not be accepted.

[kristianp]

But they didn't, did they? Their performance optimizations have usually been at a lower level, fixing inefficient code and speeding hot paths, e.g.:

https://blogs.msdn.microsoft.com/dotnet/2017/06/07/performan...