8

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?

+0

hai provato alla ricerca di queste informazioni? Dovrebbe essere facile da trovare. – Howard

+0

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

+0

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

risposta

13

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.

+0

Perché le operazioni costanti 'findMin/findMax'' O (1) 'per un BST bilanciato? – Cratylus

+0

@ 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

+1

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

11

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)

+0

Perché 'O (1) 'trova il massimo/minuto di un BST? – Cratylus

+0

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

+1

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

Problemi correlati