В третьем абзаце статьи статьи в википедии на деревьях AVL говорится: "Поскольку деревья AVL более жестко сбалансированы, они быстрее, чем красно-черные деревья для приложений с интенсивным поиском" .
Итак, не следует TreeMap внедряться с использованием деревьев AVL вместо красно-черных деревьев (так как будет более интенсивный поиск приложения для структуры данных, основанной на хэшировании)?
Красно-черные деревья более общего назначения. Они довольно хорошо работают над добавлением, удалением и поиском, но деревья AVL имеют более быстрый поиск за счет более медленного добавления/удаления. Общая политика Java заключается в предоставлении лучших структур данных общего назначения. Это также та же причина, по которой Java по умолчанию Array.sort(Object [] a) реализация является стабильной, адаптивной, итеративной сортировкой слияния вместо быстрой сортировки.
Исторически сложилось так, что число вращений было очень важным, поэтому на AVL были выбраны красно-черные деревья, потому что красно-черные выполняют немного меньше оборотов со случайными вставками - 0,6 против 7 средних оборотов на каждую вставку.
В ретроспективе, деревья AVL, вероятно, были бы лучшим выбором. Вы можете увидеть сравнение производительности AVL и красно-черных деревьев в Java здесь: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/
При случайных вставках производительность аналогична. При последовательных данных деревья AVL работают намного лучше - 30% и более.
Статья в Википедии неверна (или, по крайней мере, нет ссылки на поддержку, чтобы поддержать заявку). Верно, что наихудшая высота дерева AVL (1,44 lg n) лучше, чем наихудшая высота красно-черного BST (2 lg n), но это худший случай и, возможно, не так много сделать с реальной производительностью.