esempi reali di strutture ad albero

https://stackoverflow.com/questions/577659

05-09-2019
|

Domanda

Sto cercando alcuni esempi di strutture ad albero che vengono utilizzati in progetti di software commerciali / libero, moderni o antichi. Posso vedere esempi su wikipedia, ma sto cercando degli esempi più concreti e come vengono utilizzati. Ad esempio le chiavi primarie nei database sono (da quello che ho letto) memorizzati nella struttura BST o una variazione del BST (sentitevi liberi di correggere me su questo)

La mia domanda non è limitata alberi binari di ricerca (BST), che possono includere qualsiasi variazione come il rosso-nero, AVL e così via.

Soluzione

Va bene se gli esempi sono un po 'po' generica cioè riguardare i grafici e non necessariamente per gli alberi? Se lo è, continuate a leggere.

Inutile dire che la maggior parte dei parser XML / Markup utilizzano alberi. Vedere Apache Xerces per esempio. In alternativa, il parser Xalan XSLT. Grazie mathewsdave26 per avermelo ricordato!
PDF è un formato basato albero. Ha un nodo root seguito da un nodo catalog (questi sono spesso gli stessi) seguito da un nodo pages che ha diversi nodi figlio page. I produttori / consumatori utilizzano spesso un'implementazione albero bilanciato per memorizzare un documento in memoria.
Computer giochi di scacchi costruire un enorme albero (formazione) che potano in fase di esecuzione utilizzando l'euristica per raggiungere un movimento ottimale.
Flare è una libreria di visualizzazione scritto in AS. Si consiglia di verificare come gli oggetti di dati vengono mappati. In particolare, il pacchetto di flare.analytics utilizza pesantemente una struttura grafico, spanning tree ecc.
Il social networking è la parola d'ordine in corso nel campo della ricerca CS. Va da sé che le connessioni / rapporti sono molto naturalmente modellati utilizzando grafici. Spesso, gli alberi vengono utilizzati per rappresentare / identificare fenomeni più interessanti. Come si fa a rispondere a domande quali "Fa Harry e Sally hanno alcun comune amico (s)?"
Alcuni di grande successo motori fisici / Giochi Costruire alberi per simulare con precisione il movimento umano. Un albero in questo caso sarà tipicamente corrisponde ad un insieme di azioni; Il contesto determina quale percorso è presa per rendere una particolare risposta.
L'apprendimento basato Albero decisionale costituisce in realtà una zona formidabile di ricerca di data mining. Numerosi metodi famosi esistono come insaccamento, aumentando, e relative modifiche, che lavorano su alberi. Tale lavoro è spesso usato per generare un modello predittivo.
Un problema comune in bioinformatica è alla ricerca di grandi database per trovare le corrispondenze per un dato stringa di query. Tentativi sono un evento comune c'è.
Un bel po 'di successo (stock) commercianti utilizzare alberi di decisione nel loro giorno per giorno di negoziazione - di scegliere un mestiere, per uscire uno. Spesso questi non sono codificati in un programma per computer, ma scritto da qualche parte sul retro del proprio notebook.

Dupe. Vedi questo e questo .

Altri suggerimenti

Il B in indice del database B * alberi sta per bilanciata, non binario. L'albero è mantenuto ad una profondità uniforme per garantire anche tempi di accesso.

Il file system è una struttura ad albero. Allora date un'occhiata alla fonte a qualsiasi file system libero.
Il compilatore genera un AST dal codice sorgente, come una fase intermedia. Allora date un'occhiata alla fonte a qualsiasi compilatore gratuito.

indici di database sono normalmente memorizzati come variamts di B * alberi che, nonostante il loro nome non sono alberi binari.

Gli alberi binari sono stati utilizzati per lo spazio di partizionamento e la rimozione delle superfici nascoste sui giochi 3D di vecchio, credo che uno è stato utilizzato nel Doom gioco.

Scrivere un semplice parser ricorsivo-discesa, e lo hanno generare un albero sintattico.
Bill-Of-Materiali struttura utilizzata nella fabbricazione (come un'automobile è costituito da sottounità, ricorsivamente, fino ai dadi e bulloni).
Tabella dei simboli (come quello usato in un compilatore).
Struttura dei conti come quello usato nella gestione dei progetti. Un progetto complessivo ha sottoprogetti, a cui le spese possono essere applicate.
Società struttura organizzativa:. Divisioni, dipartimenti, ecc
Tabella dei contenuti per un documento.
Discendenti di una persona, gli antenati di una persona.
Qualsiasi Lisp s-espressione, compresa qualsiasi programma Lisp.

caratteristiche Auto-complete del software (ad es. Motore di ricerca "suggerimenti", IDE completamento tipo / simbolo, i nomi di posta elettronica e la rubrica, ecc) sono spesso implementati come tentativi, che sono strutture ad albero.

Guardando uno dei prodotti datawarehousing vedrete modi intelligenti di memorizzazione e di perforazione in forma di albero dimensioni. Si ottiene una struttura ad albero per la posizione (paese, regione, stato, m contea, città, ecc) e il tempo (anno, mese, giorno, ora). Queste due dimensioni sono comuni in molti settori, ma molto altri dati del mondo reale si presta anche per l'albero.

Per esempio nel commercio al dettaglio alimentare, alla radice dell'albero si potrebbe avere generi alimentari, che possono visualizzare in dettaglio latticini, frutta e verdura, ecc A seguito di un singolo thread si potrebbe avere. Barattoli di fagioli, al livello più alto sarete parlando in camion carichi Allora ti scendono a pallet, casse, dimensioni di latta. Tutte le diverse SKU (stock keeping unit) sono importanti per qualcuno all'interno del negozio o azienda. Poi diversi tipi di fagioli, diversi fornitori, produttori -. Tutti gli esempi di alberi per la stessa dimensione

Tutti i diversi prodotti formano un albero enorme, con diversi modi di affettare e dicinng.

C ++ include una serie di collezioni (set, multi_set, mappa, multi_map) che sono normalmente implementati come alberi rosso-neri, una sorta di albero bilanciato.

(standard Il C ++ non richiede esplicitamente questa implementazione, ma questo è il disegno più semplice che soddisfa i requisiti di complessità.)

In un / luogo interruttore router che ho usato per lavorare abbiamo usato un po 'di strutture ad albero, per la tabella di route software abbiamo usato un radix albero (scelta abbastanza comune per una tabella di routing IP).

La nostra implementazione OSPF fatto uso di alberi rosso-neri , la nostra implementazione BGP fatta uso di skiplists .

skiplists Tecnicamente non sono strutture ad albero, ma sono in pratica molto simili, e sono davvero cool.

Abbiamo sicuramente usato cumuli un po 'oltre il pensiero su di esso, è stato un po 'da quando ho lavorato lì.

query DNS .. qualsiasi cosa utilizzando una mappa utilizza AVL

System.Collections.Generic.SortedList un albero binario di ricerca come l'implementazione sottostante. Lo stesso vale per il System.Collections.GenericSortedDictionary . Qualsiasi codice utilizzando SortedList o SortedDictionary utilizza un albero binario di ricerca.

Nel mio progetto, un sistema di modifica e di imputazione per i dati dell'indagine / censimento, usiamo un albero di decisione binario di decidere quali variabili di un record per imputare o meno imputare. L'albero di decisione binario ci permette di effettuare in modo efficiente le decisioni sui percorsi sugli alberi che dovremmo e non dovremmo prendere.

Credo che questo approccio (anche se forse non solo gli alberi binari) viene utilizzato in applicazioni di intelligenza artificiale e

Usiamo una struttura ad albero per modellare un sistema di classificazione parte. Le parti sono classificati in 'classi' che hanno le classi genitore e così via. Le classi di primo livello di macchina il testo per schede in catalogo UI. Le classi sono utilizzati anche per applicare regole di pricing, di individuare 'punti caldi' su un veicolo in cui le parti vengono visualizzate in un 'configuratore', ecc modellare l'albero in SQL utilizzando set nidificati di Joe Celko e caricarli on-demand in memoria per una migliore prestazione. Le query più comuni che facciamo sono 'chi sono i miei discendenti' e 'è questa classe di un mio antenato?'

Molto utile

la classificazione degli oggetti in generale è molto spesso fatto usando alberi. E molto spesso, un grafico che sarebbe molto più adatto di un albero, ma un albero offre due grandi vantaggi su un grafico:

Si può essere rappresentato come un elenco (nested). Ad esempio, è molto più facile per mostrare un grande albero su carta (con i titoli, sottotitoli, paragrafi e liste nidificate) o sullo schermo del computer di un grafico.
È possibile puntare a un elemento nella struttura utilizzando una stringa di percorso semplice (o una pila), ad esempio "http / StackOverflow.com / Users / Dimitri C", qualcosa che è molto più difficile da fare in un grafico.

C'è un Treap implementata in ActionScript. Fonti:

Il treap fa parte del AS3Commons Collezioni quadro . Un Treap modificato viene utilizzato per eseguire le collezioni SortedSet e SortedMap inclusi.

Mettiti come la radice di albero e ora fare i tuoi genitori come figli di albero e dei genitori dei genitori come i loro figli di albero e questo può fare un caso di albero pieno uso.

Quindi attuazione qualcosa in cui la gerarchia completa di famiglia richiedono è possibile utilizzare l'albero di attuare tale.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow