В третьем абзаце wikipedia's article on AVL trees говорится: «Поскольку деревья AVL более жестко сбалансированы, они быстрее, чем красно-черные деревья для приложений с интенсивным поиском».Почему реализация красно-черного дерева для java TreeMap?
Таким образом, не должно быть TreeMap реализовано с использованием деревьев AVL вместо красно-черных деревьев (так как будут более интенсивные приложения для определения структуры данных на основе хэширования)?
Красно-черные деревья более общего назначения. Они довольно хорошо работают над добавлением, удалением и поиском, но деревья AVL имеют более быстрый поиск за счет более медленного добавления/удаления. Общая политика Java заключается в предоставлении лучших структур данных общего назначения. Это также та же самая причина, по которой реализация Java по умолчанию Array.sort (Object [] a) является стабильной, адаптивной, итеративной сортировкой слияния вместо quicksort.
Статья в Википедии неверна (или, по крайней мере, нет ссылки на поддержку, чтобы поддержать заявку). Верно, что наихудшая высота дерева AVL (1,44 lg n) лучше, чем наихудшая высота красно-черного BST (2 lg n), но это худший случай и, возможно, не так много сделать с реальной работой.
Исторически сложилось так, что число оборотов считалось очень важным, поэтому на AVL были выбраны красно-черные деревья, потому что красно-черные выполняют немного меньше оборотов со случайными вставками - .6 против 7 средних оборотов на каждую вставку.
Оглядываясь назад, деревья AVL, вероятно, были бы лучшим выбором. Вы можете увидеть сравнение производительности красно-черных деревьев AVL & в Java: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/
Со случайными вводами производительность аналогична. При последовательных данных деревья AVL работают намного лучше - 30% и более.
Java использует quicksort для примитивных объектов, поскольку он быстрее, чем сортировка слияния в среднем случае. Он использует сортировку слияния для сортировки объектов, поскольку сортировка слияния является стабильным алгоритмом сортировки. СМ.: Http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types –
@NikunjBanka Хорошая информация, спасибо! – Justin
Поскольку Java 7 merge-sort был заменен на TimSort http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124 –