Come programmatore quando dovrei considerare l'utilizzo di un albero RB, albero B o un albero AVL? Quali sono i punti chiave che devono essere considerati prima di decidere sulla scelta?Quando scegliere albero RB, albero B o albero AVL?
Qualcuno può spiegare con uno scenario per ogni struttura ad albero perché viene scelto rispetto ad altri con riferimento ai punti chiave?
prendere questo con un pizzico di sale:
B-tree, quando si sta gestendo più di migliaia di oggetti e li stai paging da un disco o un supporto di memorizzazione lento.
Albero RB quando si eseguono inserimenti, eliminazioni e retrieval molto frequenti nell'albero.
albero AVL quando gli inserimenti e le eliminazioni non sono frequenti relativamente ai recuperi.
Solo per aggiungere qualche dettaglio in più: gli alberi B possono avere un numero variabile di bambini che gli permettono di contenere molti record ma mantiene comunque un albero ad altezza ridotta. RB Tree ha regole meno rigide sul ribilanciamento che rendono gli inserimenti/eliminazioni più veloci dell'albero AVL. Al contrario, l'albero AVL è più strettamente bilanciato, quindi le ricerche sono più veloci dell'albero RB. Gli alberi RB – pschang
hanno anche prestazioni migliori O (1) sul ribilanciamento che li rende più adatti per strutture dati persistenti con roll-back e roll-forward. –
Quando si sceglie strutture di dati che si sono negoziazione off fattori quali
vorrei iniziare leggendo gli articoli di Wikipedia fa riferimento da Robert Harvey.
Pragmaticamente, quando si lavora in linguaggi come Java, il programmatore medio tende a utilizzare le classi di raccolta fornite. Se in un'attività di ottimizzazione delle prestazioni si scopre che le prestazioni della raccolta sono problematiche, è possibile cercare implementazioni alternative. Raramente è la prima cosa che uno sviluppo guidato dall'azienda deve prendere in considerazione. È estremamente raro che uno abbia bisogno di implementare tali strutture di dati a mano, di solito ci sono librerie che possono essere utilizzate.
Per essere onesti, OP ha chiesto 'quando dovrei considerare l'utilizzo', non' quando dovrei considerare l'implementazione'. Mentre l'ultimo paragrafo è vero, non fornisce molto valore nel contesto di questa domanda. Anche con le librerie, è necessario comprendere gli algoritmi al fine di scegliere in modo efficace quale struttura si adatta meglio alle esigenze aziendali. – Dan
Penso che gli alberi B + siano una buona struttura dati del contenitore ordinata per uso generale, anche nella memoria principale. Anche quando la memoria virtuale non è un problema, la compatibilità con la cache è spesso, e le strutture B + sono particolarmente adatte per l'accesso sequenziale: le stesse prestazioni asintotiche di una lista collegata, ma con una facilità di memorizzazione della cache vicina a un semplice array. Tutto questo e O (log n) cercano, inseriscono ed eliminano.
Gli alberi B + presentano tuttavia problemi, ad esempio gli elementi che si spostano all'interno dei nodi quando si inseriscono/eliminano, invalidando i puntatori a tali elementi. Dispongo di una libreria contenitore che esegue "manutenzione del cursore": i cursori si collegano al nodo foglia a cui fanno attualmente riferimento in un elenco collegato, in modo che possano essere corretti o invalidati automaticamente. Dato che raramente c'è più di uno o due cursori, funziona bene, ma è comunque un lavoro in più lo stesso.
Un'altra cosa è che l'albero B + è essenzialmente proprio quello. Immagino che sia possibile rimuovere o ricreare i nodi non fogliali a seconda che ne siano necessari o meno, ma con i nodi binari si ottiene molta più flessibilità. Un albero binario può essere convertito in una lista collegata e tornare indietro senza copiare i nodi - basta cambiare i puntatori quindi ricorda che lo stai trattando come una struttura di dati diversa ora. Tra le altre cose, ciò significa che O (n) è abbastanza facile unire gli alberi: convertire entrambi gli alberi in elenchi, unirli e poi riconvertirli in un albero.
Un'altra cosa è l'allocazione della memoria e la liberazione.In un albero binario, questo può essere separato dagli algoritmi - l'utente può creare un nodo quindi chiamare l'algoritmo di inserimento e le eliminazioni possono estrarre i nodi (staccarli dall'albero, ma non liberare la memoria). In un albero B o in un albero B +, ovviamente non funziona: i dati vivranno in un nodo a più voci. Scrivere metodi di inserimento che "pianificano" l'operazione senza modificare i nodi fino a quando non sanno quanti nuovi nodi sono necessari e che possono essere allocati è una sfida.
Rosso nero vs AVL? Non sono sicuro che faccia una grande differenza. La mia libreria ha una classe "strumento" basata su policy per manipolare i nodi, con metodi per elenchi double-linked, alberi binari semplici, alberi di diffusione, alberi rosso-nero e traci, comprese varie conversioni. Alcuni di questi metodi sono stati implementati solo perché mi annoiavo in un momento o nell'altro. Non sono sicuro di aver nemmeno testato i metodi di treap. La ragione per cui ho scelto gli alberi rosso-neri piuttosto che AVL è perché personalmente comprendo meglio gli algoritmi - il che non significa che siano più semplici, è solo un colpo di storia che mi è più familiare.
Un'ultima cosa: ho inizialmente sviluppato i miei contenitori per alberi B + come esperimento. È uno di quegli esperimenti che non sono mai finiti davvero, ma non è qualcosa che incoraggerei gli altri a ripetere. Se tutto ciò di cui hai bisogno è un contenitore ordinato, la risposta migliore è utilizzare quello fornito dalla tua libreria esistente, ad es. std :: map etc in C++. La mia libreria si è evoluta nel corso degli anni, ci è voluto del tempo per renderla stabile, e ho scoperto, relativamente di recente, che è tecnicamente non portatile (dipende da un po 'di comportamento non definito WRT offsetof).
Nella memoria B-Tree ha il vantaggio quando il numero di elementi è superiore a 32000 ... Vedere speedtest.pdf da stx-btree.
Bene, io per prima cosa apprezzo questa domanda - attualmente presentata con una scelta di fastutil IntAVLTreeSet vs. IntRBTreeSet. – Yang