Warum Rot-Schwarz-Baum-basierte Implementierung für Java TreeMap?

Question

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."

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)?

Answer 1

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.

Answer 2

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.

Answer 3

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.