# Are there data structures that mix a tree structure with lists?

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.

## 1 Answer

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.

• Even though probably the concept is trivial, in a nutshell could you tell me what an augmented data structure is? – user8469759 Jun 28 '16 at 9:29
• @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. – D.W. Jun 28 '16 at 9:32
• 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? – user8469759 Jun 28 '16 at 9:37
• Yes, this is exactly augmented data structure. But this additional pieces of information are not in the basic version. – Evil Jun 28 '16 at 9:44