Voglio sapere qual è il migliore: Array O Albero di ricerca binario in (inserire, eliminare, trovare max e min) e come posso migliorarli entrambi?Qual è la differenza tra l'albero di ricerca Array e Binary in termini di efficienza?
risposta
Un array consente random access a ciascun elemento in esso. quindi ottieni inserto, elimina e cerca un elemento specifico in O(1)
e max/min, elimina in O(n)
. [puoi anche fare max/min O(1)
e cancellare invece O(n)
]. Se si mantiene ordinato il proprio array, ciò causerà l'inserimento/eliminazione dello O(n)
, ma si otterrà O(logn)
find e O(1)
min/max.
Un BST è ordinato per definizione, e per un regolare [sbilanciato] BST, si ottiene O(n)
peggiore comportamento caso. Per BST bilanciato, si ottiene O(logn)
inserire/eliminare/trovare. È possibile ottenere O(1)
min/max qualsiasi come per entrambi.
Gli array sono in genere più veloci fino a iterate [presupponendo che l'ordine di iterazione non sia importante] poiché si ottiene una migliore prestazione cache. Inoltre, a differenza del BST, che ha una dimensione illimitata per natura, un array richiede la riallocazione e copia i dati quando l'array è pieno.
Migliorare un BST può essere fatto rendendo balanced - come AVL o red-black-trees.
Quale è il migliore? dipende dall'applicazione. Di solito quando si pianifica di inserire dati e tenerli ordinati, verrà preferita la BST. Se l'accesso casuale o l'iterazione è lo scopo principale: di solito si utilizza un array.
Perché le operazioni costanti 'findMin/findMax'' O (1) 'per un BST bilanciato? – Cratylus
@ user384706: Ogni volta che si inserisce/rimuove un elemento da un BST bilanciato, è 'O (logn)' e 'O (n)' per BST non bilanciato. Puoi mantenere puntatori extra 'min' e' max', che verranno modificati solo quando inserisci/rimuovi elementi dalla BST. Trovare il nuovo massimo/minimo è 'O (logn)' per BST bilanciato e 'O (n)' per non bilanciati - quindi non c'è alcuna perdita di prestazioni [grandi termini O] in questa operazione, e in termini di grande O, tu è possibile mantenere questi puntatori per "gratis" – amit
Ah, quindi si consiglia di utilizzare i puntatori extra.Ma in questo caso, si tratta di un'ottimizzazione non direttamente correlata agli algoritmi BST. Quindi non è in qualche modo incoerente/fuorviante rivendicare in un confronto con un'altra struttura dati (in questo caso un array) che 'max/min' è' O (1) 'dato che non è di default? Si deve implementarlo in modo tale che sia – Cratylus
confronto delle prestazioni di array e alberi binari di ricerca:
Array Binary search tree
Unsorted Sorted Average Worst case
Space O(n) O(n) O(n) O(n)
Search O(n) O(log n) * O(log n) O(n)
Max/Min O(n) O(1) O(1) ** O(1) **
Insert O(1) O(n) O(log n) O(n)
Delete O(1) O(n) O(log n) O(n)
*
assumendo ricerca binaria
**
richiede puntatori in più per min e max, altrimenti è O (log n)
Perché 'O (1) 'trova il massimo/minuto di un BST? – Cratylus
Ora che chiedi, non sono sicuro che sia corretto. Gli alberi di ricerca binaria sono ordinati per definizione, ma (a seconda dell'implementazione?) Potrebbe non essere possibile ottenere il minimo/il massimo in O (1). In tal caso sarebbe invece O (log n). – Peladao
Non è 'O (1)' a meno che la tua implementazione mantenga un puntatore ai valori 'min' e' max'. Controlla anche i commenti nella risposta di amit – Cratylus
hai provato alla ricerca di queste informazioni? Dovrebbe essere facile da trovare. – Howard
Intendi le strutture dati astratte [elenco collegato] (http://en.wikipedia.org/wiki/Linked_list) e [albero di ricerca binario] (http://en.wikipedia.org/wiki/Binary_search_tree)? – Gumbo
migliorare in che modo? il meglio per cosa? quelle sono strutture di dati completamente diverse e ognuna di esse potrebbe essere la "migliore" per una determinata applicazione. – amit