Der dritte Absatz von wikipedia's article on AVL trees sagt: "Weil AVL-Bäume starrer ausbalanciert sind, sind sie schneller als Rot-Schwarz-Bäume für Lookup-intensive Anwendungen."Warum Rot-Schwarz-Baum-basierte Implementierung für Java TreeMap?
Also, sollte nicht TreeMap mit AVL-Bäumen statt Rot-Schwarz-Bäume implementiert werden (wie es mehr Look-Up intensive Anwendungen für eine Hash-basierte Datenstruktur sein wird)?
Rot-Schwarz-Bäume sind allgemeiner einsetzbar. Sie fügen relativ gut hinzu, entfernen und suchen, aber AVL-Bäume haben schnellere Look-Ups auf Kosten von langsamerem Hinzufügen/Entfernen. Die allgemeine Richtlinie von Java besteht darin, die besten Datenstrukturen für allgemeine Zwecke bereitzustellen. Aus demselben Grund ist die standardmäßige Array.sort (Object [] a) -Implementierung von Java eine stabile, adaptive, iterative Mischsortierung anstelle von Quicksort.
Der Wikipedia-Artikel ist falsch (oder zumindest gibt es kein unterstützendes Zitat, um den Anspruch zu stützen). Es stimmt, dass die Worst-Case-Höhe eines AVL-Baums (1,44 lg n) besser ist als die Worst-Case-Höhe eines Rot-Schwarz-BST (2 lg n), aber dies ist der schlimmste Fall und hat möglicherweise nicht viel zu tun mit realer Leistung.
Historisch Anzahl der Umdrehungen gedacht war sehr wichtig zu sein, so rot-schwarz Bäume über AVL wurden ausgewählt, weil rot-schwarz etwas weniger Rotationen mit zufälligen Einsätze durchführen - 0,6 vs 0,7 durchschnittliche Umdrehungen pro Einsatz.
Rückblickend wären AVL-Bäume wahrscheinlich eine bessere Wahl gewesen. Sie können einen Leistungsvergleich von AVL & rot-schwarz Bäume in Java sehen hier: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/
Mit zufälligen Einfügungen die Leistung ähnlich ist. Mit sequentiellen Daten schneiden AVL-Bäume viel besser ab - 30% oder mehr.
Java verwendet Quicksort für primitive Objekte, da es im Durchschnitt schneller ist als merge sort. Sie verwendet merge sort zum Sortieren von Objekten, da merge sort ein stabiler Sortieralgorithmus ist. SEE: http://StackOverflow.com/Questions/3707190/Why-Java-Arrays-Nutzung-Two-Different-Sort-Algorithmen-für-verschiedene-Typen –
@NikunjBanka Gute Infos, danke! – Justin
Seit Java 7 merge-sort wurde durch TimSort http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124 ersetzt –