Che aspetto avrebbe un anti-albero?

Se visualizzi un albero come grafico non orientato senza loop, il contrario è lo stesso albero: è completamente isomorfo.

Se parli di una struttura dati reale che utilizza grafici diretti, allora, di nuovo, può essere chiamato solo "albero" che ha i suoi collegamenti invertiti: normalmente hai figli che fanno riferimento ai loro genitori (come il database SQL che avresti parent_id colonna che fa riferimento alla colonna id della stessa tabella), ma qui i genitori hanno riferimenti a tutti i loro figli. Ciò richiederebbe una serie di riferimenti (parent- > child), mentre negli alberi "normali" ogni elemento ha un solo riferimento (child- > parent).

In git, ad esempio, "true" si fondono commit hanno più genitori, che è proprio quello che sei tu ve descritto. Sebbene, git repository generalmente non sia un albero, ma alcune delle sue 'parti possono essere.

EDIT : da Wikipedia :

tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Ciò significa che le relazioni genitore-figlio nei miei esempi git e SQL sono in realtà considerate invertite . Come dice @Wyzard, in realtà è un "anti-albero" che hai descritto. Tuttavia, è ancora chiamato "albero".

L'inversione in questi esempi consente di utilizzare un solo riferimento (a un genitore) per nodo anziché un elenco di riferimenti (ai bambini). Inoltre, è conveniente aggiungere i bambini in un solo passaggio, senza dover aggiungere un riferimento in un elenco di riferimenti figlio del suo 'genitore.

C'è un qualche tipo di è e non è! Ma dobbiamo perfezionare la nostra terminologia per capire cosa sta succedendo.

Abbiamo una gerarchia come questa nella teoria dei grafi, che scorre da generale in alto a più specifico / limitato in basso:

Grafico: una raccolta di nodi (vertici) e percorsi (connessioni tra i vertici)

Grafico connesso: una raccolta di nodi in cui è possibile selezionare qualsiasi nodo iniziale e raggiungere qualsiasi altro nodo finale. La scelta di inizio e fine è arbitraria.

Albero : un grafico connesso in cui esiste un solo e unico percorso tra qualsiasi nodo iniziale e qualsiasi nodo finale. Non ci sono percorsi alternativi che non tornano indietro (visita un nodo due volte).

Rooted Tree : Proprio come un albero, ma esiste un oggetto specifico scelto come root. Da questi definiamo anche le foglie, che è qualsiasi nodo che deve essere un nodo finale quando visitato dalla radice - senza visitare un nodo due volte una volta che si colpisce una foglia non si può andare da nessuna parte, e il percorso è terminato. Le foglie possono anche essere chiamate "vertici terminali".

Nota che anche un albero radice non ha necessariamente direzione - sei libero di iniziare da una foglia e procedere alla radice, ecc.

Se un albero è implementato come una struttura di dati a collegamento singolo, questo può essere considerato come un albero diretto se non è disponibile alcun collegamento di ritorno - una volta lasciato il root per uno dei nodi connessi, non è possibile torna indietro!

Ma una tale implementazione di un albero non è necessaria nella definizione di un albero! Si può implementare un albero con liste a doppio collegamento, in modo tale che si è liberi di fare cose come spostarsi verso la radice (spesso indicata come un genitore) o lontano dalla radice (Bambino).

Quindi, se si desidera una struttura dati in cui è possibile iniziare da una foglia e lavorare alla radice, è sufficiente una che supporti una funzione "visita genitore". È anche possibile definire banalmente un sistema che non consente lo spostamento da root (padre) a figlio, solo da figlio a genitore, e questo suona come quello che stai cercando. In pratica, rimuovi semplicemente la funzionalità "visita bambino".

Tuttavia, non sono a conoscenza di alcun nome formale per una tale struttura o di cosa utilizzerebbe una tale struttura. Gli alberi che partono da una radice sono utili, e quelli che consentono di camminare su e giù sono utili, ma quelli che consentono solo un movimento unidirezionale verso la radice è di tale utilità specializzata / limitata che dubito abbia un nome speciale riservato per essa . Ma suppongo che tutto sia possibile!

Dal punto di vista pratico, puoi facilmente implementarne uno da alberi diretti esistenti o alberi con radici dirette.

Non sono sicuro di un concetto matematico esatto per ciò che stai descrivendo, ma sembra corrispondere abbastanza strettamente al concetto di grafico aciclico diretto alias DAG. Molti programmatori utilizzano effettivamente DAG ogni giorno nel loro lavoro, sotto forma di software di controllo delle versioni. Le storie di commit Git (e Mercurial e etc) formano un DAG. Monitoriamo i nodi foglia (in Git, i refs e i rami, in Mercurial, le teste, ecc.) E attraversiamo il nodo radice. Ogni nodo ha un puntatore al suo genitore, piuttosto che il contrario.

Un DAG non ha bisogno di essere rigorosamente simile ad albero in quanto può avere nodi con più genitori (un merge commit in Git, per esempio).

Non sono veramente sicuro di quale sarebbe la differenza significativa, né di come faresti per implementare una cosa del genere. I due modi in cui ho visto gli alberi implementati sono o con un array o con un riferimento.

In un'implementazione dell'array, il primo elemento è il root e i nodi figli possono essere localizzati mediante una trasformazione piuttosto semplice dell'indice del genitore. Potresti presumibilmente capovolgerlo abbastanza facilmente in modo che il primo elemento sia la foglia più a destra e trovare il genitore di qualsiasi bambino usando la lunghezza e l'indice dell'array. L'unico problema è che la lunghezza dell'array e quindi la dimensione dell'albero sono fisse ed è molto più difficile aumentare le dimensioni in modo dinamico.

Tuttavia è molto più facile fare con i riferimenti. È possibile creare facilmente una classe AntiTree che, ad esempio, fornisce un elenco di tutte le foglie, quindi ogni foglia fa riferimento al suo genitore e così via, fino a raggiungere la radice che non ha alcun genitore. Ma sembra proprio un ordine di attraversamento diverso.

Ho appena avuto un altro pensiero. In termini di come chiamarlo, non è quello che stai descrivendo solo una canalizzazione?

Da un punto di vista puramente tecnico, un anti-albero è ciò che si ha ogni volta che si sceglie di rappresentare un albero non dotando ciascun nodo genitore di una serie di puntatori ai propri nodi figli, ma dotando ciascun nodo figlio di un singolo nodo puntatore al suo nodo genitore.

Gli alberi sono comunemente rappresentati in questo modo, ad esempio, nei database relazionali.