5
$\begingroup$

Iv'e been struggling a lot with this one. I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which supports the following methods, all with time complexity (at worst-case) of $O(log(n))$:

  1. Insert(v) - insert v to the structure
  2. search(v) - search for v
  3. delete(v) - delete node with value v
  4. updateKeys(x,v) - for each node with a value greater then x, add v to it's value, where v is a positive number.

For example, if I had the following set of elements: ${1,2,5,8,10,15,20}$ , using updateKeys the following way: $ updateKeys(10,5) $ would change the set to : $ {1,2,5,8,15,20,25} $.

Well, I had a lot in my mind. Basically, my assignment is on the following data-structures:

  1. Hash tables - which sounded good at first, but I couldn't think of a way to find all elements larger than or equal to x.

  2. AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than $ log(n) $. Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.

  3. A combination of the two above - looked promising at first, but again, I couldn't find a way to find those elements.
  4. Heap - for some reason it sounds like a good direction since I have some sort of order, but update the values with log(n) time? seems impossible.

  5. Skip list - here I thought about using skip list since the most bottom layer is sorted in increasing order, so I thought about finding the minimum value larger than x, and then update all of it's followers from the right. Sounds good, but it is definitely not within $ O(log(n)) $, since for the following set ${1,2,3,4...10}$, and for $ x=1 $, I need to iterate 10 numbers, which is $ O(n) $

We also studied B-trees, ADT structures...

Then, almost hopeless, I started reading about data structures that weren't even taught in our course, such as range trees, BIT trees and so on.For some reason, some of them seemed suitable for this purpose, but since it's not in our syllabus, I don't think we are even allowed to use them.

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ 1. Why do you think you're not allowed to use things not in your syllabus? Have you actually checked with your instructor? 2. If you want to restrict answers to use only a specific set of data structures, please list the set of all data structures that you're allowed to use. (I'm not sure if that kind of restriction is even well-defined.) 3. I don't see a question here; merely a long list of declarative statements. Can you edit your question to add a question? (continued) $\endgroup$ – D.W. May 26 '16 at 23:34
  • 1
    $\begingroup$ I'm afraid questions of the form "here is my exercise, I can't figure out how to solve it, can you solve my exercise for me?" usually aren't a good fit here. We want to help you understand concepts, not do your exercise for you. Exercises exist to help you practice problem-solving, and you can only learn by struggling with them yourself, not by outsourcing their solution to others. $\endgroup$ – D.W. May 26 '16 at 23:35
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – greybeard May 27 '16 at 19:12
  • $\begingroup$ Look at the order statistics tree. Also, if there's a name for the value shift requested here it would be handy; it's come up before in literature with nobody having a name or reference for it. $\endgroup$ – KWillets Jun 4 '16 at 5:46
3
$\begingroup$

AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than log(n).

Not quite. In order to change all those entries, yes; but by searching for $x$ you can identify all nodes that have greater values: all nodes you visit and have key $> x$, namely those where you go left, and their right subtrees.

Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.

No, and that may be the key insight. If we increase all keys $>x$ by some constant we maintain the search-tree property! In particular, you never increase a left son and not its parent!

These two observations lead us to the idea: use AVL-trees (or any balanced search tree, I daresay) and execute key increments lazily. For that, add to every node an integer inc that is initially $0$.

Now, a call updateKeys(x,v) proceeds as follows.

  1. Search for x using usual BST search.
  2. Whenever you go left at some node y,

    1. increase y.key by v and
    2. increase y.right.inc by v.

This adds at most constant overhead per visited node, so it has the same $\Theta$-running-time as search.

We execute the updates whenever we traverse the tree anyway. That is, augment all four operations so that when they access some y.key they execute this first (if y.inc > 0):

y.left.inc  += y.inc
y.right.inc += y.inc
y.key       += y.inc
y.inc        = 0

This adds at most a constant amount of effort per visited node for all the operations, so it does not change their $\Theta$-bounds on time. We do need a linear amount of extra memory, but that seems to be allowed.

Detailed pseudocode and proofs of correctness are good exercises.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.