1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Yes. Build a tree (with any branching factor you want).

Then, augment the data structure by maintaining one doubly linked list per level that contains all of the nodes at that level. In particular, in each node you have a "left" and "right" field which goes to the next and previous elements in that doubly linked list (i.e., the next sibling to the right of it and the previous sibling to the left of it).

All of the standard tree operations can be augmented to update/maintain these doubly linked lists as well. This adds only $O(1)$ extra time to each operation to update the doubly linked lists, so the asymptotic running time for each tree operation remains the same.

This construction can be applied to any tree with any structure you want (binary tree, $k$-ary tree, b-tree, AVL tree, red-black tree, etc.)

I don't know of any particular name for this specific case. It is an instance of augmenting a data structure. Many data structures/algorithms textbooks will have a chapter on augmenting data structures.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Even though probably the concept is trivial, in a nutshell could you tell me what an augmented data structure is? $\endgroup$
    – user8469759
    Jun 28, 2016 at 9:29
  • 1
    $\begingroup$ @user8469759, Use some initiative! Googling the phrase immediately turns up hits. Or, as I suggested, look at a textbook. Don't ask questions here that you could easily answer on your own. $\endgroup$
    – D.W. ♦
    Jun 28, 2016 at 9:32
  • $\begingroup$ My apologies... So an augmented data structure is a data structure where you store additional information and then you implement the operations you need. Is that right? $\endgroup$
    – user8469759
    Jun 28, 2016 at 9:37
  • $\begingroup$ Yes, this is exactly augmented data structure. But this additional pieces of information are not in the basic version. $\endgroup$
    – Evil
    Jun 28, 2016 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.