Comment by 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.