Perché l'implementazione basata sull'albero rosso-nero per Java TreeMap?

Question

Il terzo paragrafo di wikipedia's article on AVL trees dice: "Poiché gli alberi AVL sono più rigidamente bilanciati, sono più veloci degli alberi rosso-neri per le applicazioni di ricerca intensiva."

Quindi, non è necessario implementare TreeMap utilizzando alberi AVL anziché alberi di colore rosso-nero (poiché ci sarà più ricerca di applicazioni intensive per una struttura dati basata su hash)?

Answer 1

Gli alberi di colore rosso-nero sono più generici. Fanno relativamente bene su aggiungere, rimuovere e cercare, ma gli alberi AVL hanno una ricerca più rapida a costo di aggiungere/rimuovere più lentamente. La politica generale di Java è quella di fornire le migliori strutture di dati per scopi generali. È anche la stessa ragione per cui l'implementazione predefinita di Array.sort (Object [] a) di Java è stabile, adattativa, iterativa, invece di quicksort.

Answer 2

L'articolo di Wikipedia è errato (o almeno non esiste una citazione di supporto per eseguire il backup). È vero che l'altezza peggiore di un albero AVL (1,44 lg n) è migliore dell'altezza del caso peggiore di un BST rosso-nero (2 lg n), ma questo è il caso peggiore e potrebbe non avere molto da fare con prestazioni reali.

Answer 3

Storicamente, si pensava che il numero di rotazioni fosse molto importante in modo da scegliere gli alberi rosso-neri su AVL perché il rosso-nero eseguiva un numero leggermente inferiore di rotazioni con inserti casuali - .6 vs .7 rotazioni medie per inserto.

Con il senno di poi, probabilmente gli alberi AVL sarebbero stati una scelta migliore. Si può vedere un confronto delle prestazioni di AVL & alberi rosso-neri in Java qui: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

Con inserimenti casuali le prestazioni sono simili. Con gli alberi AVL di dati sequenziali si ottengono prestazioni migliori del 30% o più.