By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be indexed.
I feel this question must be pretty elementary, but as a CS noob I don't know how to search for the answer. I may not even be phrasing the question correctly.
So let me describe a hypothetical use case. Say my program stores a chess game (including variations) as a tree, with each node representing the state of the game after a move. Given any two nodes which are guaranteed to be in the tree, what is the most efficient way to find the path (a sequence of intervening nodes) from one to the other? I'm mostly concerned with time complexity, although I'd like to save space as well (not sure how to express myself more precisely).
Edit: to clarify what I want, say I have a Python program like this:
tree = Tree(game_record) # there's a tree constructed from a game record
# this tree can be traversed by calling `advance` and `backtrack`
tree.advance(child=0) # advance the game into the first child of the current node
tree.backtrack() # backtrack to the parent of the current node
# and it can tell you which node it's currently at
current_node = tree.current_node()
# now this is my question: at first we're at one node
node1 = tree.current_node()
# after some advancing and backtracking, we arrive at another
node2 = tree.current_node()
# I want a method that returns the path from node1 to node2
tree.find_path(node1, node2) # should return something like [node3, node4, ...]
# what would be a good way to implement this method?
Walking the whole tree is probably not it. I'm thinking that maybe each node can be assigned an informative address
, perhaps an array. One scheme would be to let a child's address
be one element longer than its parent's, where the extra element uniquely identifies the child. So if the first node has address [0]
, its children would have [0, 0]
, [0, 1]
, ... and the children of [0, 1]
would have addresses like [0, 1, 0]
, [0, 1, 1]
, and so on. With this scheme the nodes on the path between any two nodes can be directly read off from their addresses.
With a tall tree though, the addresses can get quite long. Not a real concern for a chess program, but this way of indexing a tree just feels inefficient and inelegant to me. Is there a better way to assign addresses? Or is there a completely different approach to this problem?