Confronto tra Red / Black Tree e Java ArrayList, quali sono i vantaggi di ciascuno? [chiuso]

Poiché si tratta di Java, vale la pena separare le interfacce dalle implementazioni nel suo framework Collections.

ArrayList e LinkedList sono entrambi tipi di elenco. Una lista è una collezione ordinata a cui fa riferimento un indice arbitrario (cioè l'indice non è una proprietà dei dati che vengono memorizzati). ArrayList è supportato da un array, che è una sequenza di archiviazione ad accesso casuale. Sono veramente utili quando devi accedere a elementi casuali e non vengono inseriti nel mezzo: ArrayList supporta questa operazione, ma è potenzialmente lenta.

TreeMap e TreeSet sono tipi di Map e Set (e gli Sets delegati alle Trees, quindi le differenze nella pratica sono nul). Questi oggetti sono referenziati da qualche proprietà (chiave) che è un oggetto arbitrario: per una mappa può essere qualsiasi cosa tu voglia (tipicamente una stringa), per un insieme è l'elemento stesso. Si tratta di raccolte ordinate, ovvero gli elementi nell'albero sono ordinati sia dall'ordinamento naturale degli elementi sia da altri criteri (questo è l'interfaccia di Comparator utilizzata).

Quindi le differenze sono:

• Accesso: per indice per la lista, per chiave o elemento per l'albero.
• Mutazione: entrambe sono ordinate, ma una lista è in qualsiasi ordine arbitrario mentre l'albero ricorre a se stesso mentre si inseriscono gli elementi.

Utilizzerai una lista quando non hai bisogno di accedere agli elementi con una chiave, hai solo bisogno di un gruppo di oggetti o di cui hai bisogno in un ordine particolare che non è il loro ordinamento naturale. Dovresti utilizzare una struttura (o una tabella hash) quando desideri un archivio di chiavi / valori simile al recupero dei record da un database tramite la chiave primaria.