Come si chiama un albero che cresce in entrambe le direzioni? [chiuso]

Ci sono un paio di semplici categorie in cui è possibile inserire grafici che rendono più facile classificarle.

• Diretto: questo è un grafico in cui si hanno relazioni genitore-figlio che sono a senso unico, cioè il bambino potrebbe non fare direttamente riferimento al genitore
• Undirected: questo è un grafico in cui si hanno relazioni nodo-nodo, non sono genitore-figlio e possono andare in entrambi i modi
• Aciclico: questo è un grafico che non ha cicli in esso, questo significa che nessuno dei nodi può fare riferimento a un nodo che lo fa direttamente o indirettamente, vale a dire che potrebbe non fare riferimento a uno dei suoi antenati
• Ciclico: questo è un grafico che può avere cicli in esso, questo significa che qualsiasi nodo può fare riferimento a qualsiasi nodo
• Balanced: è un grafo diretto con qualsiasi percorso fino alla lunghezza di N + -1, quando viene disegnato è riconoscibile perché sembra simmetrico e i nodi senza figli vivono tutti entro 1 livello di altezza l'uno dall'altro.
• Binario: si tratta di un grafico diretto in cui ogni nodo non ha più di 2 figli.

Il grafico che hai disegnato è un Grafico Aciclico Diretto , spesso definito DAG in breve. La maggior parte delle cose a cui ci riferiamo come "alberi" rientrano in questa categoria, le persone solitamente non chiamano grafici che sono "alberi" non orientati o ciclici perché quando ne disegni uno, non dà l'impressione di avere una radice che è cresciuto da come fanno gli alberi. Le persone di solito ricorrono al termine "grafico" nel caso di non-DAG

Sopra sono i classificatori comunemente visti e ben noti, scavando intorno a Wikipedia ( link ) potresti trovare altri che sono meno conosciuto come:

• Radicato: questo è un grafico con un singolo nodo radice (il tuo esempio specifico può essere chiamato senza radici, anche se sono poche le persone che riconoscono questa terminologia)
• Simmetrico: sinceramente; Non lo so a portata di mano.
• Completo: un grafico completo è un grafico in cui tutti i nodi hanno riferimenti diretti a tutti gli altri nodi.

Un albero è un tipo speciale di grafico. Più specificamente, è "qualsiasi grafico connesso senza cicli semplici" . Quindi, il tuo grafico è un albero. Non importa se cresce o no. Il tuo è un grafico diretto quindi non importa comunque. Non è un albero binario, se è quello che stavi chiedendo =)

Non credo che ci sia un nome speciale per questo, è semplicemente un albero. "Crescere in entrambe le direzioni" è puramente un artefatto di come hai disegnato l'albero.

Inoltre, è un po 'difficile da capire dalla tua arte ASCII, ma se la parte superiore e quella inferiore sono collegate e hai cicli, allora questo non è tecnicamente un albero, ma un grafico (di quali alberi sono più specifici caso).

In base all'immagine aggiornata, questo non è un albero ma un grafico diretto. Ciò che è etichettato come "root" non può essere una radice perché ha più spigoli che vi conducono. Un albero è un tipo molto specifico di grafico aciclico diretto, che è questo, ma ha il vincolo aggiuntivo che deve avere solo un singolo nodo senza alcun bordo che vi porti dentro. Quel nodo è la radice. Come puoi vedere, nessuno dei nodi nel tuo grafico può soddisfare questa definizione.

Un albero è un qualsiasi grafico aciclico.

In un albero non orientato, qualsiasi nodo può essere la radice, poiché tutti i bordi sono non orientati e quindi non esiste una relazione "genitore / figlio". Molti di questi non sono in genere considerati come alberi e non sono disegnati come tali, ma si applicano tutte le definizioni matematiche.

In un albero diretto, di solito c'è una singola radice, se si definisce se la direzione dei bordi è "figlio- gen" o "genitore- > figlio". Quale di solito è un dettaglio di implementazione: le strutture in memoria hanno in genere puntatori da genitore a figlio, i database relazionali utilizzano chiavi esterne da bambini a genitore.

Si noti che un albero diretto non può avere radice se la direzione degli archi non rappresenta una relazione genitore / figlio. Questo è ancora un tre, ma la maggior parte delle semplificazioni di implementazione tipiche di un terzo diretto sono meno ovvie. In tal caso, un'implementazione potrebbe trattare i tre come non orientati o aggiungere un albero radice sottostante etichettando separatamente le relazioni padre / figlio.

In questo caso la direzione del bordo viene disegnata in modo incoerente, ma immagino che qualsiasi implementazione ne sceglierebbe una e capovolgere le frecce di una metà, così si termina con un albero con radici piuttosto standard. Ovviamente, per mantenere la sottostruttura del 'prefisso' separata da quella del 'suffisso', vorrei usare due alberi indipendenti, o inizializzare la radice con due nodi fissi ('prefisso' e 'suffisso') e crescere ognuno in modo indipendente.