I have a tree where every node may have 0 to N children.
Use-case is the following query: Given pointers to two nodes: Are these nodes within the same branch of the tree?
q(2,7) => true q(5,4) => false
By the book (slow)
The straight forward implementation would be to store a pointer to the parent and a pointer to a list of children at each node. But this would lead to bad performance because the tree would be fragmented in memory and therefor not cache-aware.
What would be a good way to represent the tree in compact form? The whole tree has about 100,000 nodes. So it should be possible to find a way to make it fit completely in the CPU-cache.
Binary trees for example are often represented implicitly as an array and are therefor perfect to be completely stored in the CPU-cache (if small enough).