Question

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data.

Something like this (I'll be informal, but I hope I can give you some idea of what I mean).

Suppose we have a tree with depth $n$. At depth 1 we would have the nodes $X_1,X_2,\ldots X_{n_1}$. For $i_1 \in \left\{1,\ldots n_1\right\}$ the node $X_{i_1}$ could have as children $X_{i_1,1},X_{i_1,2},\ldots X_{i_1,n_{i_1}}$, for $i_2 \in \left\{1,\ldots,n_{i_1} \right\}$ the node $X_{i_1,i_2}$ could have as children $X_{i_1,i_2,1},X_{i_1,i_2,2},\ldots, X_{i_1,i_2,n_{i_2}}$, and so on. However to get quick access to the nodes say at depth $k$ I could also implement a list of pointers to all the nodes $L_k := \left\{ X_{i_1,\ldots, i_k } \right\}$. So for depth 1 I could have the list

$$ L_1 := \left\{ X_1, \ldots, X_k \right\} $$

At depth 2 instead

$$ L_2 := \left\{ X_{1,1},\ldots, X_{1,m_1},\ldots,X_{n_1, 1} , \ldots, X_{n_1, m_{n_1}} \right\} $$

So in general the list $L_k$ would contain all the nodes with $k$ indices. I'm pretty sure something like this already exists, however I can remember if there's a specific name or not.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top