Efficient storing and multidirectional lookup of hierachical data

Question

I make a game and among others I have nations, provinces, tiles and armies. Each army belongs to exactly one tile, each tile belongs to exactly one province, each province to exactly one nation. I want to ask the following questions:

1. Which armies/tiles/provinces belong to a nation?
2. Which armies/tiles belong to a province?
3. Which armies belong to a tile?
4. To which tile/province/nation belongs this army?
5. To which province/nation belongs this tile?
6. To which nation belongs this province?

These questions are multidirectional. A hierachical tree with nations on top and provinces, tiles, armies below will only answer questions 1-3 efficiently while answers 4-6 would require a loop over all nations/provinces/tiles to find the nation/province/tile that belongs to a province/tile/army.

So one could store 4 different trees, each time with nations/provinces/tiles or armies on top to enable a fast lookup. However then modifying the whole structure (adding/deleting/modifying a nation/province/tile/army) gets a complex task and therefore prone to errors.

I'm a bit lost here. I would like to keep the code and the underlying data structures simple to prevent errors when modifying the structure or when adding more functionality but I would not like to give up speed for answering the mentioned questions. I'm looking for a balance of code complexity and speed where code simplicity is more important.

In particular: Can I have a single data structure (and easy adding/deleting) while not having to loop over all nations/... when asking the reverse question? What is the simplest data structure/algorithm that allows asking all these questions with reasonable speed, i.e. without having to loop over every nation/...?

• valenterry: Why don't you give every of your provinces, tiles and armies a (redundant) reference to its parent tile/province/nation? You then have to consider this reference on each update of course, but it gives you instant access to the answers for questions 4-6. Would that be already too messy/complex?
• NoDataDumpNoContribution: @valenterry Thank you for this helpful comment. This seems like the obvious way to go and now I ask myself why I haven't seen this for myself. It's not too complex although the number of tiles, armies and provinces is quite large, so storing a back reference induces some overhead, but not too much. Thanks again.
• valenterry: Glad I could help you. I created an answer so that you can mark the answer as accepted solution.

Answer 1

One Option is to give every of your provinces, tiles and armies a reference to its parent tile/province/nation. You then have to consider this reference on each update of course as you now have some redundancy in your code and a little memory overhead. Though, the good thing is that it gives you the answers for questions 4-6 in an instant (constant time).

---

(From my comment to the question, see also: https://meta.stackexchange.com/questions/1555/mark-a-comment-as-answer-to-a-question)