I have 'discovered' a way to encode rose trees (see e.g. What are the applications of Rose trees? ) as a sparse matrix: if you have a node n with ID i and parent ID p, then you place n in the matrix at coordinates (row, column) of (p, i). This makes it easy to:
- Get a node by its ID and parent ID (single lookup of the matrix)
- Get all children of a node ID (lookup a matrix row)
- Prune and graft subtrees (change the coordinates of the subtree root)
Now I'm thinking that I can't be the first person to have thought of this. Can anyone point me to any literature which discuss this encoding?