I'd like to make a bunch of disconnected comments: * I have a different take on writing "efficient" AVL trees. Optimizing for human comprehension, I have an im

I'd like to make a bunch of disconnected comments: * I have a different take on writing "efficient" AVL trees. Optimizing for human comprehension, I have an implementation strictly under 100 lines of code: https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java . (Unlike bitlush, mine uses recursion, explicit height tracking, and no parent pointers.) * Java's TreeMap<K,V> is similar to C#'s SortedDictionary<TKey, TValue>. Java also uses a red-black tree. * bitlush claims a 2× to 4× speed-up over the standard library's SortedDictionary. Red-black trees are asymptotically optimal (O(log n)), so they can't improve by more than a constant factor. I get the vague sense that bitlush was able to make a constant speed-up by simplifying some unused code or offering less functionality than the standard library. I doubt that the standard library is being intentionally slow. * If they wanted a faster sorted dictionary, they should use a B-tree. Rust does this, and it is much more cache-friendly. For example, see http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa... . * I think having parent pointers is a more expensive tradeoff than recursion. A binary tree node must have 2 child pointers, and adding a parent pointer brings the total to 3; this costs O(n) space. This cost is borne by all nodes all the time. Meanwhile, using recursion for insert/delete/iterator costs O(log n) space, and only temporarily during the operation. * The author claims "I also wrote a lot of tests to ensure the code is rock solid.". The test suite is at https://github.com/bitlush/avl-tree-c-sharp/tree/master/Bitlush.AvlTree.Tests https://github.com/bitlush/avl-tree-c-sharp/tree/master/Bitl... . The suite looks a bit short to me, and I don't see more than ten elements be tested. I would suggest the author implement one of my favorite ways of testing data structures: Performing thousands of random operations on your data structure, and comparing the results against a naive or standard library implementation.