0
$\begingroup$

I'm trying to design a data structure that supports the following operations in $O(1)$ time:

  • $\operatorname{query}(\ell)$: Yield some auxiliary datum associated with list $\ell$ (just a single integer for my use case).
  • $\operatorname{update}(\ell,v)$: Set the auxiliary datum of list $\ell$ to $v$.
  • $\operatorname{list}(n)$: Get the list associated with node $n$.
  • $\operatorname{ends}(\ell)$: Get the end nodes of list $\ell$.
  • $\operatorname{concat}(n_0,n_1)$: Concatenate $\operatorname{list}(n_0)$ and $\operatorname{list}(n_1)$ so that nodes $n_0$ and $n_1$ are adjacent. Preconditions are that $n_0$ and $n_1$ are end nodes in two distinct lists and those two lists have the same auxiliary data (which becomes the auxiliary datum of the resulting list).
  • $\operatorname{split}(n)$: Split $\operatorname{list}(n)$ after node $n$ (according to some arbitrary assignment of direction to the lists). The resulting two lists have the same auxiliary data as the original list.

Use a model as powerful as you want, eg, word RAM.

Basically these are just linked lists with some additional data. The tricky part is to ensure the datum for a list can be updated in $O(1)$ but also accessed from any node in $O(1)$.

I was unable to do this with only elementary data structures like arrays and linked lists. The naive strategies I can think of run in $O(N)$ time (where $N$ is the maximum total number of nodes over the lifetime of the data structure). I think any balanced BST can yield a working solution$^1$, but that's $O(\log N)$ and the approach I'm thinking of does not lend itself well to using standard library BST containers, which is a pain. I'm hoping that this can be done in $O(1)$ in a simple-to-implement way. Something like $O(\log^\ast N)$ or $O(\alpha(N))$ would be good as well, and I would even be interested in a simple $O(\log N)$ strategy that doesn't require implementing a balanced BST from scratch.

$^1$: The idea for implementing these operations with BSTs is to let the key of a node in the tree be its rank in the current list ordering. The $\operatorname{split}$ and $\operatorname{concat}$ operations can change that ordering so we just have to let the structure of the trees represent the ordering implicitly. In all BST implementations that I'm aware of, the balancing, $\operatorname{split}$, and $\operatorname{concat}$ operations don't compare keys explicitly but just look at the tree structure so this works.

For the particular application that originally inspired this, the nodes come from a constant universe $U=\{0,1,\dotsc,N-1\}$ and represent vertices in a rooted tree such that, at any given point, all lists will be descending paths in the tree. This makes the BST strategy particularly simple to implement: the key ordering is the (fixed) ordering by depth.

$\endgroup$
  • $\begingroup$ "There is no operation in your data structure that returns a node 𝑛". See the ends operation. As for construction it didn't seem important but you can imagine a create() operation that returns a list consisting of a single new node. $\endgroup$ – dysonsfrog Sep 1 at 3:21
  • $\begingroup$ Sorry, my previous comment doesn't fully clarify things. The two ways of getting pointers to nodes that I had in mind were 1. some operation for iterating over lists and 2. the user storing nodes from the create() operation and then accessing them later. For my use case the nodes correspond directly to vertices in a given tree and the user could just store them in an array. $\endgroup$ – dysonsfrog Sep 1 at 4:51
  • $\begingroup$ What is a "list"? You want to fetch lists by integer n? What range is n? Use hashing on the key n? $\endgroup$ – vonbrand Sep 3 at 18:43
  • $\begingroup$ A list is just a list of nodes (a group of nodes with some linear ordering). n mostly means node, not integer. I unfortunately chose to use n to also represent the total number of nodes over the use of this data structure, but I've rewritten things to use N to represent that instead. $\endgroup$ – dysonsfrog Sep 3 at 22:40
  • $\begingroup$ That said, to obtain O(1) or o(log N) time, it might be necessary to view the nodes as just indices from some universe U, as opposed to taking more of a pointer machine perspective. I think that's why you're suggesting hashing? $\endgroup$ – dysonsfrog Sep 3 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.