I've implemented a n-ary tree ( to be more specific, a trie ) and I was wondering if there's a method to represent and traverse it as a vector. With a binary tree that would be trivial ( see this question ) but I don't seem to find a way to perform this with a n-ary tree.
My final goal would be storing the vector represented tree to a file, mmap it and perform fast lookups without having it effectively loaded into memory.
An efficient approach to store a trie on disk ad using it with a mmap-ped pointer instead of allocating its inner structures would be great too.
Thanks.
If you have a tree where every node n has exactly k children, then you can proceed by placing the children of node n at positions k*n+m in the array, where m is between 0 and k-1. This will also work if every node has k or less children, but it will use a lot more memory than required if a lot of nodes have fewer than k children. The only other way I know of to store a tree as an array where nodes have different number of children is to store an auxillary array,, where for each node you store the offset into the original array to find that node's children and then you can either also store the number of children for each node or simply look up the offset for the next node's children to figure out how many children there are for the node.