# Create a data structure with D-SUCCESSOR running in $O(1)$

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?

• What's a $d$-successor? What's a $k$-successor? Where do the pointers $p$ come from? Jun 8 at 0:33
• 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 Jun 8 at 8:30
• 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? Jun 8 at 8:47
• "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 Jun 8 at 9:49
• 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. Jun 8 at 13:38