Differenza tra un LinkedList e un albero di ricerca binario
https://stackoverflow.com/questions/270080
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Quali sono le principali differenze tra un elenco collegato e un BinarySearchTree? BST è solo un modo per mantenere un LinkedList? Il mio istruttore ha parlato di LinkedList e poi di BST, ma non li ha confrontati o non ha detto quando preferire l'uno all'altro. Questa è probabilmente una domanda stupida ma sono davvero confuso. Gradirei se qualcuno potesse chiarire questo in modo semplice.
Soluzione
Elenco collegato:
Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)
Albero binario:
Node(1)
/
Node(2)
/ \
/ Node(3)
RootNode(4)
\ Node(5)
\ /
Node(6)
\
Node(7)
In un elenco collegato, gli elementi sono collegati tra loro tramite un singolo puntatore successivo. In un albero binario, ogni nodo può avere 0, 1 o 2 nodi secondari, dove (nel caso di un albero di ricerca binario) la chiave del nodo sinistro è inferiore alla chiave del nodo e la chiave del nodo destro è maggiore di il nodo. Finché l'albero è bilanciato, il percorso di ricerca per ciascun elemento è molto più breve di quello in un elenco collegato.
percorsi di ricerca:
------ ------ ------
key List Tree
------ ------ ------
1 1 3
2 2 2
3 3 3
4 4 1
5 5 3
6 6 2
7 7 3
------ ------ ------
avg 4 2.43
------ ------ ------
Con strutture più grandi il percorso di ricerca medio diventa significativamente più piccolo:
------ ------ ------
items List Tree
------ ------ ------
1 1 1
3 2 1.67
7 4 2.43
15 8 3.29
31 16 4.16
63 32 5.09
------ ------ ------
Altri suggerimenti
Un Albero di ricerca binario è un albero binario in cui ciascun nodo interno x memorizza un elemento in modo tale che l'elemento memorizzato nella sottostruttura sinistra di x sono minori o uguali a x e gli elementi memorizzati nella sottostruttura destra di x sono maggiori o uguali a x .
Ora un Elenco collegato è costituito da una sequenza di nodi, ciascuno contenente valori arbitrari e uno o due riferimenti che puntano al nodo successivo e / o precedente.
In informatica, un albero di ricerca binario (BST) è una struttura di dati di albero binario che ha le seguenti proprietà:
- ogni nodo (elemento nella struttura) ha un valore distinto;
- entrambi i sottotitoli sinistro e destro devono anche essere alberi di ricerca binari;
- la sottostruttura sinistra di un nodo contiene solo valori inferiori al valore del nodo;
- la sottostruttura destra di un nodo contiene solo valori maggiori o uguali al valore del nodo.
In informatica, un elenco collegato è una delle strutture di dati fondamentali e può essere utilizzato per implementare altre strutture di dati.
Quindi un albero di ricerca binaria è un concetto astratto che può essere implementato con un elenco collegato o un array. Mentre l'elenco collegato è una struttura di dati fondamentale.
Direi che la differenza PRINCIPALE è che un albero di ricerca binario è ordinato. Quando si inserisce in un albero di ricerca binario, dove quegli elementi finiscono per essere archiviati in memoria è una funzione del loro valore. Con un elenco collegato, gli elementi vengono aggiunti alla cieca all'elenco indipendentemente dal loro valore.
Puoi subito alcuni compromessi: Gli elenchi collegati mantengono l'ordine di inserimento e l'inserimento è meno costoso Gli alberi di ricerca binaria sono generalmente più veloci da cercare
Un elenco collegato è un numero sequenziale di "nodi" collegati tra loro, ovvero:
public class LinkedListNode
{
Object Data;
LinkedListNode NextNode;
}
Un albero di ricerca binario utilizza una struttura di nodo simile, ma invece di collegarsi al nodo successivo, si collega a due nodi figlio:
public class BSTNode
{
Object Data
BSTNode LeftNode;
BSTNode RightNode;
}
Seguendo regole specifiche quando si aggiungono nuovi nodi a un BST, è possibile creare una struttura di dati che è molto veloce da attraversare. Altre risposte qui hanno dettagliato queste regole, volevo solo mostrare a livello di codice la differenza tra le classi di nodi.
È importante notare che se inserisci dati ordinati in un BST, finirai con un elenco collegato e perderai il vantaggio di usare un albero.
Per questo motivo, un LinkedList è una struttura dati traversale O (N), mentre un BST è una struttura dati traversale O (N) nel caso peggiore e una O (registro N) nel migliore dei casi.
Le liste collegate e i BST non hanno molto in comune, tranne per il fatto che sono entrambe strutture di dati che fungono da contenitori. Elenchi collegati consentono sostanzialmente di inserire e rimuovere elementi in modo efficiente in qualsiasi posizione nell'elenco, mantenendo l'ordinamento dell'elenco. Questo elenco è implementato usando i puntatori da un elemento al successivo (e spesso al precedente).
Un albero di ricerca binario è invece un dato struttura di un'astrazione più alta (cioè non è specificato come questo è implementato internamente) che consente ricerche efficienti (cioè per trovare un elemento specifico non devi guardare tutti gli elementi.
Si noti che un elenco collegato può essere pensato come un albero binario degenerato, ovvero un albero in cui tutti i nodi hanno un solo figlio.
In realtà è piuttosto semplice. Un elenco collegato è solo un insieme di elementi concatenati insieme, in nessun ordine particolare. Puoi pensarlo come un albero davvero magro che non si ramifica mai:
1 - > 2 - > 5 - > 3 - > 9 - > 12 - > | i. (l'ultimo è un tentativo ascii-art di terminare un null)
Un albero di ricerca binario è diverso in 2 modi: la parte binaria significa che ogni nodo ha 2 figli, non uno, e la parte di ricerca significa che quei bambini sono disposti per accelerare le ricerche - solo oggetti più piccoli a sinistra e solo quelli più grandi a destra:
5
/ \
3 9
/ \ \
1 2 12
9 non ha figli di sinistra e 1, 2 e 12 sono "foglie" - non hanno rami.
Ha senso?
Per la maggior parte di " ricerca " tipi di usi, un BST è migliore. Ma solo per "tenere un elenco di cose da affrontare in seguito First-In-First-Out o Last-In-First-Out" tipi di cose, un elenco collegato potrebbe funzionare bene.
Il problema con un elenco collegato è la ricerca al suo interno (sia per il recupero o l'inserimento).
Per un elenco a collegamento singolo, devi iniziare dalla testa e cercare in sequenza per trovare l'elemento desiderato. Per evitare la necessità di scansionare l'intero elenco, sono necessari ulteriori riferimenti ai nodi all'interno dell'elenco, nel qual caso non è più un semplice elenco collegato.
Un albero binario consente una ricerca e un inserimento più rapidi essendo intrinsecamente ordinati e navigabili.
Un'alternativa che ho usato con successo in passato è una SkipList. Ciò fornisce qualcosa di simile a un elenco collegato ma con riferimenti extra per consentire prestazioni di ricerca paragonabili a un albero binario.
Un elenco collegato è proprio questo ... un elenco. È lineare; ogni nodo ha un riferimento al nodo successivo (e al precedente, se si parla di un elenco doppiamente collegato). Rami di un albero --- ogni nodo ha un riferimento a vari nodi figlio. Un albero binario è un caso speciale in cui ogni nodo ha solo due figli. Pertanto, in un elenco collegato, ogni nodo ha un nodo precedente e un nodo successivo e, in un albero binario, un nodo ha un figlio sinistro, un figlio destro e un genitore.
Queste relazioni possono essere bidirezionali o unidirezionali, a seconda di come è necessario essere in grado di attraversare la struttura.
Hanno somiglianze, ma la differenza principale è che un albero di ricerca binario è progettato per supportare la ricerca efficiente di un elemento o "chiave".
Un albero di ricerca binario, come un elenco doppiamente collegato, punta ad altri due elementi nella struttura. Tuttavia, quando si aggiungono elementi alla struttura, piuttosto che aggiungerli alla fine dell'elenco, l'albero binario viene riorganizzato in modo che gli elementi collegati a "sinistra" siano nodo sono inferiori al nodo corrente e gli elementi collegati al "diritto" nodo sono maggiori del nodo corrente.
In una semplice implementazione, il nuovo elemento viene confrontato con il primo elemento della struttura (la radice dell'albero). Se è inferiore, la "sinistra" " viene eseguito il ramo, altrimenti il ??"diritto" il ramo è esaminato. Questo continua con ciascun nodo, fino a quando un ramo viene trovato vuoto; il nuovo elemento riempie quella posizione.
Con questo semplice approccio, se gli elementi vengono aggiunti in ordine, si finisce con un elenco collegato (con le stesse prestazioni). Esistono diversi algoritmi per mantenere una certa misura di equilibrio nell'albero, riorganizzando i nodi. Ad esempio, gli alberi AVL fanno il massimo lavoro per mantenere l'albero il più equilibrato possibile, offrendo i migliori tempi di ricerca. Gli alberi rosso-neri non mantengono l'albero equilibrato, con conseguenti ricerche leggermente più lente, ma fanno meno lavoro in media man mano che le chiavi vengono inserite o rimosse.
L'elenco collegato è costituito da dati lineari diritti con nodi adiacenti collegati tra loro, ad es. A- > B- > C. Puoi considerarlo come una recinzione diritta.
BST è una struttura gerarchica proprio come un albero con il tronco principale collegato ai rami e quei rami a loro volta collegati ad altri rami e così via. Il "binario" la parola qui significa che ogni ramo è collegato ad un massimo di due rami.
Si utilizza l'elenco collegato per rappresentare i dati semplici solo con ciascun elemento collegato a un massimo di un elemento; mentre puoi usare BST per connettere un oggetto a due oggetti. Puoi usare BST per rappresentare un dato come l'albero genealogico, ma quello diventerà un albero di ricerca n-ary poiché possono esserci più di due figli per persona.
Un albero di ricerca binario può essere implementato in qualsiasi modo, non è necessario utilizzare un elenco collegato.
Un elenco collegato è semplicemente una struttura che contiene nodi e puntatori / riferimenti ad altri nodi all'interno di un nodo. Dato il nodo principale di un elenco, è possibile passare a qualsiasi altro nodo in un elenco collegato. Gli elenchi doppiamente collegati hanno due puntatori / riferimenti: il normale riferimento al nodo successivo, ma anche un riferimento al nodo precedente. Se l'ultimo nodo in un elenco doppiamente collegato fa riferimento al primo nodo dell'elenco come nodo successivo e il primo nodo fa riferimento all'ultimo nodo come nodo precedente, si dice che sia un elenco circolare.
Un albero di ricerca binario è un albero che divide il suo input in due metà approssimativamente uguali basate su un algoritmo di confronto di ricerca binaria. Pertanto, sono necessarie solo pochissime ricerche per trovare un elemento. Ad esempio, se avessi un albero con 1-10 e avessi bisogno di cercarne tre, prima verrebbe controllato l'elemento in alto, probabilmente un 5 o 6. Tre sarebbero meno di quello, quindi solo la prima metà del l'albero sarebbe quindi controllato. Se il valore successivo è 3, è necessario, altrimenti viene eseguito un confronto, ecc., Fino a quando non viene trovato o non vengono restituiti i suoi dati. Pertanto l'albero è veloce per la ricerca, ma non è necessariamente veloce per l'inserimento o l'eliminazione. Queste sono descrizioni molto approssimative.
Elenco collegato da wikipedia e Albero di ricerca binario , anche da wikipedia.
Sono strutture di dati totalmente diverse.
Un elenco collegato è una sequenza di elementi in cui ogni elemento è collegato al successivo e, nel caso di un elenco doppiamente collegato, il precedente.
Un albero di ricerca binario è qualcosa di completamente diverso. Ha un nodo radice, il nodo radice ha fino a due nodi figlio e ogni nodo figlio può avere fino a due note figlio ecc. Ecc. È una struttura di dati piuttosto intelligente, ma sarebbe un po 'noioso spiegarlo qui. Dai un'occhiata al Wikipedia artcle su di esso.
