Perché l'inserimento di elementi sequenziali in un albero richiede più tempo rispetto all'inserimento di elementi casuali in un albero?

Question

Questo non è compito Sto prendendo una classe di strutture dati e di recente abbiamo finito gli alberi. Alla fine della lezione, il mio professore ha mostrato questa immagine.

ConcreteBTree è un albero binario non bilanciato. Ho alcune domande sui tempi necessari per completare queste procedure.

1. Perché ci vuole molto di più tempo per inserire 100.000 elementi sequenziali in ConcreteBTree di quello necessario per inserire elementi casuali in esso? La mia intuizione sarebbe che, poiché gli elementi sono sequenziali, dovrebbe impiegare meno tempo di quanto occorra per inserire 1.000.000 di elementi casuali.

2. Perché i tempi di insert() e find() di ConcreteBTree con elementi casuali sono così ravvicinati? È perché entrambi hanno la stessa complessità temporale? Ho pensato che fosse inserto O (1) e trovare era O (n)

Mi piacerebbe davvero capire che cosa sta succedendo qui, ogni spiegazione sarebbe molto apprezzato. Grazie

Answer 1

Inserendo elementi sequenziali (1,2,3,4 ...) in un albero binario, verrà sempre aggiunto i nodi sullo stesso lato (a sinistra, ad esempio). Quando si inseriscono elementi casuali si aggiungeranno i nodi casualmente a sinistra ea destra.

Aggiunta in sequenza farà sì che l'elenco di comportarsi come una lista concatenata ordinaria (per le voci sequenziali) perché nuovi elementi dovranno visitare ogni elemento aggiunto in precedenza e che prenderà O (n) passi, quando si aggiunge a caso ci vorrà O (log N) passi in media.

Answer 2

Armin ha risposto al primo trimestre.

2. Perché sono le ore di insert() e find() di ConcreteBTree con elementi casuali così ravvicinati? È perché entrambi hanno la stessa complessità temporale? Ho pensato che fosse inserto O (1) e trovare è stato O (n)

insert e find hanno a che fare lo stesso lavoro - che scendono attraverso qualsiasi albero strano che hai messo insieme alla ricerca di quella dell'ultimo nodo in base al quale il valore è collegato o sarebbe (e sarà nel caso di insert), quindi fanno lo stesso numero di confronti e attraversamenti di nodi, prendendo tempo simile.

L'inserimento di elementi casuali in un albero bilanciato è O (registro N). Il tuo inserimento di valori casuali in un albero che non autoregola il riequilibrio sarà un po 'ma non drammaticamente peggiore in quanto alcuni rami finiranno per essere considerevolmente più lunghi di altri - probabilmente otterrai una sorta di curva a campana delle lunghezze dei rami. insert è solo O (1) se si conosce già il nodo nell'albero sotto il quale deve essere eseguito l'inserto (vale a dire che è necessario normalmente trovare il passaggio sopra). find 's solo O (n) se deve essere visitato ogni nodo dell'albero, che è solo il caso di un albero patologicamente sbilanciato, formando efficacemente un elenco collegato, come ti è stato già detto che puoi generare inserendo elementi ordinati.