dotnet/corefx — pull request #106 by AArnott (2014-11-17 04:58:32+00:00)
Title: Fix AVL tree balancing for dictionary and set collections

The immutable list, dictionary and set collections use AVL trees for their internal data structures. Bug #103 describes and fixes the problem for lists, but left dictionaries and sets untouched.

AVL tree balancing isn't quite right as it leaves the tree slightly imbalanced in some cases. In the best case, this just means we're ever so slightly slower than we need to be at lookups. But I wonder if it's possible for these slight mis-balances to cascade into large imbalances.

This pull request fixes the issue (#105) by performing the appropriate double rotations when we're +/- 1 off instead of +/- 2. Exactly the same fix as the one applied in #103, just to the other collection types.

See commit messages for more explanation, particularly about the test/testability changes.