Qual è una buona struttura dati per costruire classi di equivalenza sui nodi di un albero?

Question

Sto cercando una buona struttura dati per creare classi di equivalenza sui nodi di un albero. In una struttura ideale, le seguenti operazioni dovrebbero essere veloce (O (1)/O (n) come appropriato) e veloce (nessun punti di codice mistero):

• (A) Walk l'albero dalla radice; in ogni nodo -> transizione bambino enumerare tutte le versioni equivalenti del nodo figlio
• (B) Unire due classi di equivalenza
• (C) Creazione di nuovi nodi da un elenco di nodi esistenti (i bambini) e altri dati
• (D) Trova tutti i nodi strutturalmente equivalenti al nodo (cioè hanno lo stesso numero di figli, i bambini corrispondenti appartengono alla stessa classe di equivalenza e i loro "altri dati" sono uguali) in modo che i nuovi nodi (o modificati) possano essere inserito nella giusta classe di equivalenza (tramite un'unione)

Finora ho considerato (alcuni di questi potrebbero essere utilizzati in combinazione):

• Un parfait, dove i bambini sono riferimenti a raccolte di nodi anziché a nodi. (A) è veloce, (B) richiede di camminare sull'albero e di aggiornare i nodi per puntare alla raccolta unita, (C) richiede di trovare la raccolta contenente ogni figlio del nuovo nodo, (D) richiede camminare sull'albero
• Manutenzione di un hash dei nodi per le loro caratteristiche. Questo rende (D) molto più veloce ma (B) più lento (poiché l'hash dovrebbe essere aggiornato quando le classi di equivalenza sono unite)
• String i nodi insieme in una lista concatenata circolare. (A) è veloce, (B) sarebbe veloce ma per il fatto che quella "fusione" di una lista circolare con se stessa divide effettivamente la lista (C) sarebbe veloce, (D) richiederebbe camminare sull'albero
• Come sopra, ma con un puntatore "su" aggiuntivo in ciascun nodo, che potrebbe essere utilizzato per trovare un membro canonico dell'elenco circolare.

mi manca un dolce alternativa?

Answer 1

Sembra che tu abbia due forme di equivalenza da gestire. Equivalenza semplice (A), tracciata come classi di equivalenza che sono mantenute aggiornate e equivalenza strutturale (D), per le quali occasionalmente si va a costruire una singola classe di equivalenza e poi buttarla via.

Mi sembra che il problema sarebbe concettualmente più semplice se si mantengono le classi di equivalenza sia per l'equivalenza semplice che per quella strutturale. Se ciò introduce troppo sfasamento per l'equivalenza strutturale, è possibile mantenere le classi di equivalenza per alcuni aspetti dell'equivalenza strutturale. Quindi è possibile trovare un equilibrio in cui ci si può permettere il mantenimento di tali classi di equivalenza, ma ridurre ancora notevolmente il numero di nodi da esaminare quando si costruisce un elenco di nodi strutturalmente equivalenti.

Answer 2

non credo che qualsiasi struttura sta per risolvere i vostri problemi, ma si potrebbe dare un'occhiata al Disjoint-set data structure. Una classe di equivalenza, dopo tutto, è la stessa cosa di una partizione di un set. Dovrebbe essere in grado di gestire alcune di queste operazioni rapidamente.

Answer 3

Tornando indietro per un momento suggerirei di non usare affatto un albero. L'ultima volta che ho dovuto affrontare un problema simile, ho iniziato con un albero, ma in seguito mi sono spostato su un array.

Motivi diversi ma il motivo numero uno era le prestazioni, le mie classi con un massimo di 100 bambini avrebbero effettivamente prestazioni migliori mentre le manipolavano come array rispetto ai nodi di un albero, principalmente a causa della localizzazione dell'hardware e del prefetch della CPU logica e pipelining della CPU.

Quindi anche se algoritmicamente una struttura di array richiede un numero N maggiore di operazioni rispetto a un albero, eseguire queste dozzine di operazioni è probabilmente più veloce che inseguire i puntatori attraverso la memoria.