There were interesting papers regarding balanced binary trees in 2015 & 2016
http://sidsen.azurewebsites.net// And after reading about "Rank-balanced Trees" I started comparing AVL & Red-black tree performance and was surprised to see that red-black trees are the default in Java given the performance differences noted in Ben Pfaff's 2004 work. So I wrote several new TreeMap implementations and put them on GitHub with two short blog posts- https://refactoringlightly.wordpress.com/ Seems that TreeSet is used a lot in Lucene and if the input has sequences then the constants in the Olog(n) operations make those places a very strong candidate to switch to an AVLTreeSet. So many uses of TreeSet I wasn't sure where/how to start benchmarking? --David
