# Efficient storing and multidirectional lookup of hierachical data

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/...?

• 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? Commented Nov 19, 2014 at 22:08
• @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. Commented Nov 21, 2014 at 8:49