Given an integer $d$, I need to devise a data structure $S$ with the following actions:

  1. BUILD(S): build the data structure $S$ from $n$ elements in $\Theta(n\lg{n})$
  2. INSERT(S, k): insert a new element to $S$ with the key $k$ in $\Theta(\lg{n} + d)$
  3. DELETE(S, k): delete the element in $S$ with the key $k$ in $\Theta(\lg{n} + d)$
  4. D-SUCCESSOR(S, p): find the $d$ successor of the element pointed by $p$ in $\Theta(1)$
  5. K-SUCCESSOR(S, p, k): find the $k$ successor of element pointed by $p$ in $\Theta(\lg{n})$

$d$ is part of the data structure and I can't treat it like a const in efficiency calculations. Also I need to use minimal space.

Successor is defined as the next element after given element $p$ if all $n$ elements in $S$ were ordered, thus the k-successor is defined recursively as the successor for the (k-1)-successor, and the d-successor is the k-successor when $k=d$

My idea is to use an Order-Static tree, OST, because it can do actions 1-3 & 5 in $\Theta(n\lg{n})$ and $\Theta(n)$ respectively, and I'm left with action 4, and due to the requirement for $\Theta(1)$ I summarized that each node in the tree needs to have a pointer to its d-successor, and maintaining it is what adds $d$ to the insert and delete actions. But maintaining this additional pointer means I need to update it after every insert and delete for all $d$ predecessors of the element added (or deleted) doing this using OST existing functions will add $\Theta(d\lg{n})$ to both insert and delete making them run in more than $\Theta(\lg{n} + d)$.

So I've decided to add another pointer, in addition to the one to the d-successor. The second pointer will point to the predecessor of each node. In insert after adding the new node to the tree I get the new node successor in $\Theta(\lg{n})$ and update its and the new node's predecessor pointer, then I loop to the previous $d$ predecessors and for each I update the d-successor pointer to be pointer of its predecessor with the last one (the d-predecessor) pointing to the new node. I do the same for deletion, and now both run in $\Theta(\lg{n} + d)$.

Though I found the desired $S$ I'm wondering if I can make it without adding more than 1 pointer? maybe even without additional pointers at all?

  • 1
    $\begingroup$ What's a $d$-successor? What's a $k$-successor? Where do the pointers $p$ come from? $\endgroup$ Jun 8, 2021 at 0:33
  • $\begingroup$ k-successor is the k-th successor to the element pointed by $p$, e.g if $p$ points to the first element in the tree in-order traversal and $k=1$ then the k-successor is the second element in the traversal, and if $k=2$ then the k-successor is the third, etc. the d-successor is the k-successor when $k=d$. The pointers $p$ are passed as arguments to the functions, the user can get them by using the tree search function, or calling successor/predecessor calls on available pointers, e.g the tree root $\endgroup$ Jun 8, 2021 at 8:30
  • $\begingroup$ Thanks, please add this info to the question. "in the tree in-order traversal" -- what tree? And what order is it kept in? E.g., are the keys taken from some ordered universe? Or insertion order? $\endgroup$ Jun 8, 2021 at 8:47
  • $\begingroup$ "what tree" the one I describe as the my data structure $S$, in this case an Order-Static tree. It is inferred that the elements in the data structure has an order function, i.e you can do $k_1 < k_2$, otherwise actions like successor are meaningless, and I don't think the identity of said order function is relevant to the discussion $\endgroup$ Jun 8, 2021 at 9:49
  • $\begingroup$ No tree is described as part of the problem specification -- that's just something you decided to use to implement the spec, so it can't be used to define the term "successor", which is part of the spec. "Successor" could mean a variety of things, including at least the 2 examples I gave. $\endgroup$ Jun 8, 2021 at 13:38


Your Answer

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