Un albero rosso-nero è la mia struttura dati ideale?

Question

Ho una collezione di articoli (grandi razionali) che elaborerò. In ogni caso, l'elaborazione consisterà nel rimuovere l'elemento più piccolo nella raccolta, fare del lavoro e aggiungere 0-2 nuovi elementi (che saranno sempre più grandi dell'elemento rimosso). La raccolta verrà inizializzata con un elemento e il lavoro continuerà fino a quando non sarà vuoto. Non sono sicuro delle dimensioni che la raccolta probabilmente raggiungerà, ma mi aspetterei negli articoli da 1M a 100M. Non avrò bisogno di localizzare oggetti diversi dal più piccolo.

Attualmente sto pianificando di utilizzare un albero rosso-nero, possibilmente ottimizzato per mantenere un puntatore all'elemento più piccolo. Comunque non ne ho mai usato uno prima, e non sono sicuro che il mio schema di utilizzo si adatti bene alle sue caratteristiche.

1) Esiste il pericolo che lo schema di cancellazione da sinistra + inserimento casuale influenzi le prestazioni, ad esempio richiedendo un numero significativamente maggiore di rotazioni rispetto all'eliminazione casuale? O cancellerà e inserirà le operazioni ancora O (log n) con questo schema di utilizzo?

2) Qualche altra struttura di dati mi darà prestazioni migliori, sia a causa del modello di eliminazione o sfruttando il fatto che ho sempre bisogno di trovare l'elemento più piccolo?

Aggiornamento: felice che ho chiesto, l'heap binario è chiaramente una soluzione migliore per questo caso e, come promesso, si è rivelato essere molto facile da implementare.

Hugo

Answer 1

A binary heap è molto meglio per quello che vuoi. È più facile da implementare e più veloce poiché ti interessa solo individuare l'elemento e gli inserimenti più piccoli. Individuare l'elemento più piccolo è O (1), rimuoverlo è O (log N), e un inserimento è anche O (log N).

Answer 2

Un mucchio vi darà O (1) O (log n) la rimozione e O (log n) l'inserimento, ed è molto più facile da implementare rispetto a un albero rosso-nero

Answer 3

È utile sapere come creare strutture di dati più complesse, se necessario. Tuttavia, in genere la soluzione migliore è iniziare il più semplice possibile e utilizzare solo qualcosa di più complesso quando risulta necessario.

L'unica volta in cui ho implementato un albero autobilanciato è stata una volta in cui mi è capitato di sapere che il mio albero sarebbe stato davvero grande (oltre 10.000 elementi), e che i dati sarebbero arrivati ​​a scatti ordinati. Ciò significava che se avessi usato un normale albero binario, avrei finito con quasi una lista collegata.

Se i dati vengono inseriti in un ordine casuale, non dovresti preoccuparti di un algoritmo di bilanciamento.