Calcolo di un sottoalbero massimo ripetitivo in un albero degli oggetti

Naviga le tue risposte
-1

Sto cercando di risolvere un problema nel trovare un sottoalbero massimo ripetitivo in un albero degli oggetti.

Per albero degli oggetti intendo un albero in cui ogni foglia e nodo ha un nome. Ogni foglia ha un tipo e un valore di quel tipo associato a quella foglia. Ogni nodo ha un insieme di foglie / nodi in un determinato ordine.

Dato un albero di oggetti che - sappiamo - ha un sub-albero ripetitivo in esso.

Per ripetitivo intendo 2 o più sotto-alberi che sono simili in tutto (nomi / tipi / ordine di sottoelementi) ma i valori delle foglie. Nessun nodo / foglia può essere condiviso tra sotto-alberi.

Il problema è identificare questi sottoalberi dell'altezza massima.

So che la ricerca esauriente può fare il trucco. Sto piuttosto cercando un approccio più efficiente.

    
posta bonomo 04.09.2012 - 16:38
fonte

2 risposte

2

Puoi eseguire l'hash dei sottoalberi: per ogni nodo, generare un valore hash basato sui valori di interesse (ad esempio, esclusi i valori foglia) e i valori hash dei relativi figli, nell'ordine.

Usa questo hash per inserire i tuoi nodi in una tabella hash di dimensioni appropriate e controlla le collisioni per determinare quali sono effettivamente ripetitivi e quali sono accidentali.

    
risposta data 04.09.2012 - 20:37
fonte
0

Potresti scambiare qualche spazio di archiviazione per il calcolo:

Se inserito, controlla la somiglianza con il genitore e, se trovato, copia il "contatore ad albero simile" da genitore e incrementa per figlio. Quello che fai con quello dipende da te. O lasciatelo su un albero o mantieni una mappa da qualche parte indicizzata sulla testa di ogni sotto-albero.

Come minimo, stai solo facendo confronti n-1, senza contare la contabilità che scegli di fare per tenere traccia dei sotto-alberi.

    
risposta data 04.09.2012 - 19:14
fonte

Leggi altre domande sui tag

Principio della singola responsabilità: Responsabilità sconosciuta [chiusa] gestione degli utenti mongoDB (integrata o propria implementazione) [chiusa]