Archiviazione efficiente e ricerca multidirezionale di dati gerarchici

1

Faccio un gioco e tra l'altro ho nazioni, province, tessere ed eserciti. Ogni esercito appartiene a esattamente una tessera, ogni tessera appartiene esattamente a una provincia, ogni provincia a esattamente una nazione. Voglio porre le seguenti domande:

  1. Quali eserciti / tessere / province appartengono a una nazione?
  2. Quali armate / tessere appartengono a una provincia?
  3. Quali eserciti appartengono a una tessera?
  4. A quale tessera / provincia / nazione appartiene questo esercito?
  5. A quale provincia / nazione appartiene questa tessera?
  6. A quale nazione appartiene questa provincia?

Queste domande sono multidirezionali. Un albero gerarchico con nazioni in cima e province, tessere, armate di seguito rispondono solo alle domande 1-3 in modo efficiente mentre le risposte 4-6 richiedono un giro su tutte le nazioni / province / tessere per trovare la nazione / provincia / tessera che appartiene ad un provincia / piastrelle / esercito.

Quindi è possibile memorizzare 4 alberi diversi, ogni volta con nazioni / province / tessere o armate in cima per consentire una rapida ricerca. Tuttavia, la modifica dell'intera struttura (aggiunta / eliminazione / modifica di una nazione / provincia / tessera / esercito) diventa un'attività complessa e quindi soggetta a errori.

Sono un po 'perso qui. Vorrei mantenere il codice e le strutture dati sottostanti semplici per evitare errori durante la modifica della struttura o l'aggiunta di ulteriori funzionalità, ma non vorrei rinunciare alla velocità per rispondere alle domande citate. Sto cercando un equilibrio di complessità e velocità del codice in cui la semplicità del codice è più importante.

In particolare: posso avere una singola struttura dati (e aggiungere / eliminare facilmente) senza dover ricorrere a tutte le nazioni / ... quando faccio la domanda inversa? Qual è la struttura / algoritmo dei dati più semplice che consente di porre tutte queste domande a una velocità ragionevole, ovvero senza dover ricorrere a loop su ogni nazione / ... ??/?p>     

posta Trilarion 19.11.2014 - 22:52
fonte

1 risposta

2

Un'opzione consiste nel dare a ciascuna delle tue province, tessere ed eserciti un riferimento alla sua tessera / provincia / nazione genitore. È quindi necessario prendere in considerazione questo riferimento su ogni aggiornamento, dato che ora si dispone di una certa ridondanza nel codice e di un piccolo sovraccarico di memoria. Tuttavia, la cosa buona è che ti dà le risposte per le domande 4-6 in un istante (tempo costante).

(Dal mio commento alla domanda, vedi anche: link )

    
risposta data 21.11.2014 - 10:51
fonte

Leggi altre domande sui tag