b"\n_START_ARTICLE_\nAlgoritmo di Barnes-Hut\n_START_PARAGRAPH_\nL'algoritmo di Barnes\xe2\x80\x93Hut, proposto da Josh Barnes e Piet Hut, \xc3\xa8 un algoritmo di approssimazione per eseguire la simulazione a n-corpi. \xc3\x88 noto per avere complessit\xc3\xa0 , al contrario del metodo esaustivo che ha ordine ._NEWLINE_Lo spazio della simulazione \xc3\xa8 di solito diviso in celle cubiche attraverso un octree (nello spazio tridimensionale), in modo che solo le particelle dalle celle vicine vengono trattate individualmente, mentre quelle distanti possono essere considerate come una grande particella situata nel centro di massa della cella (o come un troncamento dello sviluppo in multipoli). In questo modo si riduce drammaticamente il numero di interazioni tra le coppie di particelle che si devono calcolare._NEWLINE_Alcuni dei pi\xc3\xb9 richiesti progetti ad alta prestazione utilizzano l'algoritmo ad albero di Barnes-Hut nell'astrofisica computazionale,_NEWLINE_come DEGIMA.\n_START_SECTION_\nL'albero di Barnes\xe2\x80\x93Hut\n_START_PARAGRAPH_\nIn una simulazione a n-corpi, l'algoritmo di Barnes\xe2\x80\x93Hut suddivide ricorsivamente gli  corpi in gruppi e li memorizza in un octree (o un quad-tree in due dimensioni). Ogni nodo dell'albero rappresenta una regione dello spazio tridimensionale._NEWLINE_La radice rappresenta l'intero spazio, e i suoi otto figli indicano gli otto ottanti del volume. Lo spazio \xc3\xa8 diviso ricorsivamente in ottanti finch\xc3\xa9 ogni suddivisione non contiene al massimo un corpo (qualche regione non possiede alcun corpo in nessuno dei suoi ottanti)._NEWLINE_Ci sono due tipi di nodi nell'octree: i nodi interni e le foglie. Le foglie non hanno figli e rappresentano un singolo corpo oppure sono vuoti. Ogni nodo interno invece descrivono il gruppo di corpi al di sotto di esso, memorizzando il centro di massa e la massa totale di tutti i suoi corpi figli.\n_START_SECTION_\nCalcolare la forza agente su un corpo\n_START_PARAGRAPH_\nPer calcolare la forza risultante su di un particolare corpo, si visitano i nodi dell'albero, partendo dalla radice. Se il centro di massa di un nodo interno \xc3\xa8 abbastanza lontano dal corpo, tutte le particelle contenute in quella parte dell'albero vengono trattate come una sola, la cui posizione e massa sono rispettivamente il centro di massa e la massa totale del nodo. Se invece il nodo interno \xc3\xa8 sufficientemente vicino, si ripete il processo su ognuno dei suoi figli._NEWLINE_Se un nodo \xc3\xa8 o non \xc3\xa8 abbastanza lontano da un corpo dipende dal quoziente , dove  \xc3\xa8 la larghezza dell'ottante rappresentato dal nodo interno, e  \xc3\xa8 la distanza tra il corpo e il centro di massa del nodo. Il nodo \xc3\xa8 abbastanza lontano se questo rapporto \xc3\xa8 minore di un valore soglia . Il parametro  determina la precisione dell'algoritmo; valori maggiori di  aumentano la velocit\xc3\xa0 della simulazione ma diminuiscono la sua precisione. Se , nessun nodo interno viene trattato come una particella unica e l'algoritmo degenera nel metodo esaustivo di somma diretta.\n_START_SECTION_\nC\n_START_PARAGRAPH_\nStruttura albero scritta su C utilizzando i costrutti typedef e struct._NEWLINE_1 typedef struct barnes {2     //coordinate del nodo3     double x, y;4     //massa del nodo5     double massa;6     //puntatori ai sottoalberi7     struct barnes * NW, *NE, *SE, *SW;8 } barnes_t;"