Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
One can, for example, represent 2d arrays such as:
[[1,2],[3,4],[4,5]]
as flat arrays:
[1,2,3,4,5,6]
as long as he transforms the indices before accessing:
index(x,y) = x + y*2 // because internal width=2
This is often faster. My question is: is it possible to use a similar approach of representing an structure as a flat array, for, instead of n-dimensional tables, free-form trees such as:
[[1,2,3],4,[5,[6,7]],8]
Well, it depends a bit on the operations. You cannot do anything reasonable if you want to realize you data structure inside an $n$-elementary array. The 2d array works, since there is a bijection between the 2d array entries and the 1d array entries. There is also such a bijection for any fixed tree, but I think this is not what you are looking for.
Notice that your tree decoding [[1,2,3],4,[5,[6,7]],8] also uses more structure than a normal 1d array. So if you ask for data structures of size $O(n)$ with $O(1)$ operations than you can actually do something.
One idea is to use a array where you store the DFS-tour (sometimes called Euler tour) of your tree, and the information about the time when you discover and when you finished a vertex in the DFS search. This can be stored inside an array of size $4n$ plus another $n$ for the values at the nodes, and it allows you to navigate through the tree using $O(1)$ operations per step.
With more involved data structures you can also answer level ancestor queries (what is the $i$-th vertex about vertex $x$?) or lowest common ancestor queries in constant time with a data structure of size $O(n)$. If you want to know more about these two data structures, look up the references in wikipedia.
No, it does not seem to be possible, if there are no constraints on the shape or size of the tree.
(If you are able to impose some strict requirements on the structure of the tree, there are known methods. For instance, heaps are one example of exactly this optimization, applied to a particular kind of binary tree. However, I realize this doesn't address your request for a data structure for free-form trees.)
Since you care about performance, it is also important to understand that performance depends not solely upon the number of memory accesses, but also upon locality: how well those accesses play with caches. Cache-friendly data structures are not studied as much in typical undergraduate data structures classes, but they have been studied extensively in other contexts (e.g., databases).
Yes and no. If the structure of your tree has a known maximum depth and constant structure, you can statically calculate a matrix that defines the transform of I indexes to a single linear index in k time. Calculating this matrix, though, requires I*N time for N elements.
I'd rather make this a comment, but I don't have enough reputation.
I feel like you should provide more information of what is expected from the structure. Like what kind of access you need, and what kind of operations are going to be performed, etc.
For example, you have already provided one of the flat structures for a general tree. Notice, that brackets [], represent your subtrees as a continuous ranges in the array. You can utilize that if you need to access the whole subtrees in constant time.
Also, as answered by sqykly, if the graph is constant you can pre-calculate the transform I. If the tree allows dynamic changes to its structure, you should be able to update your transform in sub-linear time.
Yes, you can represent tree structure in flat list.
One example in world of databases is called Closure Table Pattern.
It lets you get all ancestors or all childs of specific node without using recursive query. Best article (the most simple and straightforward) I found is: https://towardsdatascience.com/closure-table-pattern-to-model-hierarchies-in-nosql-c1be6a87e05b
The only missing thing in above article is exact definition of create, delete and update parent of node, but you can deduce it basing on image that contains tree structure and table of Ancestors and Descendants.
