0
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ What's a $d$-successor? What's a $k$-successor? Where do the pointers $p$ come from? $\endgroup$
    – j_random_hacker
    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$
    – CforLinux
    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$
    – j_random_hacker
    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$
    – CforLinux
    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$
    – j_random_hacker
    Jun 8, 2021 at 13:38

0

Reset to default

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.