Perché alberi di ricerca binaria?

Stavo leggendo l'albero di ricerca binario e stavo pensando che perché abbiamo bisogno di BST? Tutte le cose che conosco possono anche essere ottenute usando matrici ordinate semplici. Ad es. - Per creare un BST che abbia n elementi, è necessario il tempo n*O(log n), ovvero O(nlog n) e il tempo di ricerca è O(log n). Ma questa cosa può anche essere raggiunta usando l'array. Possiamo avere una matrice ordinata (richiede tempo O(nlog n)) e il tempo di ricerca è anch'esso pari a O(log n), ad esempio ricerca binaria. Allora perché abbiamo bisogno di un'altra struttura dati? Ci sono altri usi/applicazioni di BST che li rendono così speciali?Perché alberi di ricerca binaria?

--Ravi

fonte

2010-10-14 Ravi Gupta

Qual è l'efficienza dell'inserimento/rimozione dalla versione dell'array? Se si tratta di spostare tutti gli altri elementi dell'array, ciò può essere costoso. –

ok ...trovare la posizione corretta dell'elemento nuovo/esistente sarebbe ancora O (log n), ma sì lo spostamento sarà un problema ... ma solo questo .... come per i testi che ho letto, sembra che loro (BST) sono molto speciali? Voglio sapere di più su cose che li rendono così speciali. –

possibile duplicato di [binary search vs binary search tree] (http://stackoverflow.com/questions/5968937/binary-search-vs-binary-search-tree) – nawfal

Gli array sono fantastici se si parla di scrivere una volta, leggere più volte il tipo di interazioni. È quando si arriva a inserire, scambiare e cancellare in cui BST inizia a brillare davvero rispetto a un array. Dal momento che sono basati su nodi, piuttosto che basati su un blocco contiguo di memoria, il costo di spostare un elemento nella raccolta o fuori dalla raccolta è veloce pur mantenendo la natura ordinata della raccolta.

Pensatelo come si farebbe con la differenza nell'inserimento tra liste collegate e array. Questa è una semplificazione eccessiva, ma evidenzia un aspetto del vantaggio che ho notato sopra.

fonte

2010-10-14 15:53:56 wheaties

E il tempo di inserimento ordinato?

fonte

2010-10-14 15:30:36

ok ... trovare la posizione corretta del nuovo elemento sarebbe ancora O (log n), ma sì lo spostamento sarà un problema ... ma proprio questo .... come per i testi che ho letto, sembra che loro (BST) sono molto speciali? Voglio sapere di più su cose che li rendono così speciali. –

Penso che le altre risposte possano aiutarti. Un'altra cosa da ricordare è che i BST non sono la struttura dati definitiva, ma costituiscono le basi fondamentali per strutture più complicate e più efficienti, il che spiega la loro popolarità. Ad esempio, si può essere consapevoli che la ricerca di un BST è lineare nel caso peggiore; la risposta a questo problema sono gli alberi AVL. Hai anche alberi rosso-nero, 2-3-4 alberi, suffisso/prefisso alberi e DAWG, e così via, che generalizzano tutti i BST in un modo diverso e producono algoritmi efficienti che sarebbero fuori dalla nostra portata con gli array. –

Nella programmazione grafica se si dispone di un oggetto esteso (vale a dire che rappresenta un intervallo in ogni dimensione e non solo un punto) è possibile aggiungerli al livello più piccolo di un albero binario (in genere un albero) in cui si integrano completamente.

E se non si precalcola l'albero/lista ordinata, il tempo di inserimento casuale O (n) in un elenco può essere eccessivamente lento. D'altra parte il tempo di inserimento in un albero è solo O (log (n)).

fonte

2010-10-14 15:36:12 CodesInChaos

Immagina di avere un array con un milione di elementi.

si desidera inserire un elemento in posizione 5.

Quindi si inserisce alla fine della matrice e quindi ordinare.

Diciamo che l'array è pieno; questo è O (nlog n), che è 1.000.000 * 6 = 6.000.000 di operazioni.

Immagina di avere un albero bilanciato.

Questo è O (log n), più un bit per il bilanciamento = 6 + un bit, chiamarlo 10 operazioni.

Quindi, hai appena speso 6.000.000 ops per ordinare il tuo array. Quindi si desidera trovare quell'elemento. cosa fai? ricerca binaria - O (log n) - che è esattamente lo stesso di quello che farai quando cerchi nella struttura ad albero!

Ora immagina di voler allocare -un altro elemento.

L'array è pieno! cosa fai? ri-allocare l'array con n elementi extra e memcpy il lotto? vuoi davvero memcpy 4mbytes?

In un albero, basta aggiungere un altro elemento ...

fonte

2010-10-16 09:14:43

risposta

Problemi correlati