complessità del set :: inserire

Ho letto che l'operazione di inserimento in un set richiede solo il tempo log (n). Come è possibile?complessità del set :: inserire

Per inserire, per prima cosa abbiamo trovato la posizione nell'array ordinato in cui il nuovo elemento deve sedersi. Usando la ricerca binaria prende log (n). Quindi per inserire in quella posizione, tutti gli elementi che succedono dovrebbero essere spostati di un posto a destra. Ci vuole un'altra volta.

Il mio dubbio si basa sul fatto che il set è implementato come una matrice e gli elementi sono memorizzati in ordine. Per favore correggimi se la mia comprensione è sbagliata.

fonte

2012-10-08 bibbsey

Si presume che 'std :: set' sia implementato come array ordinato. Perché? –

Tratto da cppreference: * Gli insiemi sono solitamente implementati come alberi rosso-nero. * – chris

@KonradRudolph: Ora so solo che i set sono implementati usando l'albero rosso-nero. Grazie chris – bibbsey

std::set è comunemente implementato come un albero di ricerca binaria rosso-nero. L'inserimento su questa struttura dati ha un peggior caso di complessità O (log (n)), dato che l'albero viene mantenuto bilanciato.

fonte

2012-10-08 06:39:09 cdhowie

Non proprio: la modifica può comportare il ribilanciamento che è ancora una volta un'operazione O (log n). –

Con un albero rosso-nero, l'inserimento dovrebbe avere il caso peggiore di O (log (n)), anche considerando il riequilibrio. – cdhowie

Sì, certo, non l'ho contestato. Ma hai detto che modificare l'albero è O (1). *Questo è sbagliato. –

risposta

Problemi correlati