Organise trees like for scene graphs in an array so that traversing the nodes is done cache optimally. Cover Depth-first, breadth-first, parent before child. Reorgansize trees to amortize traversal - when and how does this yield a better performance? Determine the influence of the size of nodes, size of tree - number of children. As simplification implement turning any tree into an into binary tree. Compare: https://youtu.be/SzjJfKHygaQ
One optimization: Keep the tree as tree then create a flattened version (no need for child information) to improve cache friendliness.
- Recreate if the tree changes
- Or keep the tree as flattened and make update operations
If you are interested in this topic or for more information please contact Prof. Helmut Hlavacs (helmut.hlavacs(at)univie.ac.at).