Aggiunta di nodi ordinati all'albero in ordine arbitrario

Question

Aggiunta di nodi ordinati all'albero in ordine arbitrario

#1 da (2 voti)
#2 da (1 voti)

0

Ho un database di nodi. Ogni nodo può avere esattamente un genitore, ma un numero qualsiasi di bambini. Alcuni nodi possono essere memorizzati senza genitore, ma in fase di esecuzione, posso creare un nodo "root" predefinito per essere il genitore di questi.

Innanzitutto, come viene chiamata questa struttura dati? Penso che sia solo un "albero", ma voglio essere sicuro di usare la terminologia corretta.

Un altro problema che sto incontrando è trovare un modo efficiente per creare l'albero. I nodi possono essere recuperati dal database in qualsiasi ordine, quindi quando aggiungo un nodo all'albero, il suo genitore potrebbe non essere ancora nella struttura. Ciò significa che quando aggiungo un nodo, devo verificare se i nodi esistenti hanno genitori e quindi aggiungere il genitore nel punto appropriato.

Ho cercato molto online, ma la maggior parte parla di alberi si riferisce semplicemente a "alberi binari" e anche in questo caso non riesco nemmeno a trovare alcun buon esempio di come costruire l'albero nel codice - di solito funziona con un albero esistente albero.

Ci sono esempi di modi efficienti per costruire questo albero (qualunque esso possa essere chiamato)? La lingua non ha importanza, ma userò php.

php data-structures trees

posta Explosion Pills 27.01.2012 - 08:09

fonte

2 risposte

1

La tua definizione è insufficiente per un albero. Applicare semplicemente che ogni nodo ha esattamente un genitore è in effetti lontano da un albero, perché garantisce già che la struttura sarà ciclica.

Un albero è un grafico diretto senza cicli, in cui due vertici sono collegati esattamente da uno (semplice) percorso. Se si omette il requisito del percorso semplice, si ottiene una struttura più generale, denominata grafico aciclico diretto . Se autorizzi ulteriormente i cicli, ottieni un grafico diretto, che è praticamente quello che hai dato alla tua semplice descrizione.

Indipendentemente dal fatto che la definizione dei tuoi nodi dati sia esatta o meno, puoi fare meglio assumendo un grafico diretto (aciclico) per il tuo processo di costruzione. In un grafico, i nodi standalone che non sono (ancora) connessi sono un caso normale che non ti darà alcun problema. Così puoi leggere il database in qualsiasi ordine tu voglia e costruire la tua infrastruttura da quella.

Modifica: ho già pensato che la tua struttura sia aciclica. Ma notate che ogni albero è anche un caso speciale di un grafico, quindi vale soprattutto. Leggi su strutture di dati del grafico, poiché ti consentono di costruire alberi in modo incrementale, senza richiedere sempre radici e bambini adeguati. Devi solo garantire che il grafico finale sarà effettivamente una struttura ad albero (che dipende principalmente dal contenuto del tuo database).

risposta data 27.01.2012 - 08:24

fonte

Leggi altre domande sui tag php data-structures trees

Ereditarietà rispetto alla composizione in un'applicazione aziendale C programmazione in Windows 7 [chiuso]

score 2 · Accepted Answer

Con l'avvertenza che ogni nodo ha esattamente un genitore tranne il nodo radice , chiamare questo albero va bene.

Per quanto riguarda la costruzione dell'albero, un modo è quello di fare quanto segue:

mantenere una sorta di ricerca associativa dei nodi esistenti indicizzati dal loro ID univoco (non conosco PHP, ma sto pensando ad una sorta di dizionario o hash)
mantenere una ricerca simile dei nodi orfani , indicizzati dall'ID genitore
quando crei un nodo:
1. controlla se è genitore nell'insieme esistente
  - se lo è, collega il figlio al genitore
  - se non lo è, inserisci il nuovo nodo nel orfano set
2. quindi controlla se qualche orfano lo sta aspettando (i nodi nell'insieme orfano indicizzati con l'ID del nuovo nodo)
  - se ce ne sono, collegali e rimuovili dal orfano set
3. infine, aggiungi il nuovo nodo al set esistente
alla fine, qualsiasi cosa ancora nell'insieme orfano è un problema o dovrebbe essere collegata al tuo nodo root.

Supponendo, ovviamente, che tu abbia un ID univoco per identificare le relazioni genitore / figlio.

Oh, e sembra che abbia usato la parola set per significare un qualche tipo di contenitore associativo - nota che non può essere univoco o che 3.2 avrà problemi con più orfani dello stesso nodo.