1

I'm working on a question from a test in Data Structures, I need to suggest a data structure S that will comply with the follwing requirements:

NOTE: S should allow multiple values with the same keys to be inserted

  • INSERT(S, k): insert object with key k to S with time complexity O(lg n)
  • DELETE_OLD(S): Delete the oldest object in S with time complexity O(lg n)
  • DELETE_OLD_MIN(S): Delete the oldest object that has the lowest key in S with time complexity O(lg n)
  • MAX_COUNT(S): Return the key with the maximum frequency (most common key in S) with time complexity O(lg n)
  • FREQ_SUM(S,z): Finding two keys (a and b) in S such that frequency.a + frequency.b = z with time complexity O(lg n)

I tried some ideas but could not get passed the last two.

EDIT: The question A data structure traversable by both order of insertion and order of magnitude does NOT answer my question. Please do not mark it as duplicate. Thank you.

EDIT #2: Example for what freq_sum(S,z) does:

Suppose that one called freq_sum(S,5) over the data structure that contains: 2, 2, 2, 3, 4, 4, 4, 5, 5

The combination 2 and 5 could be a possible answer, becuase 2 exists 3 times in the structure and 5 exists 2 times, so 3+2=z

Community
  • 1
  • 1
Tom Klino
  • 2,358
  • 5
  • 35
  • 60
  • That last requirement looks less related to the data structure and more to the algorithm that uses the look ups. – Mike Jul 12 '15 at 14:43
  • possible duplicate of [A data structure traversable by both order of insertion and order of magnitude](http://stackoverflow.com/questions/31162171/a-data-structure-traversable-by-both-order-of-insertion-and-order-of-magnitude) – sds Jul 12 '15 at 14:47
  • @sds This is not a duplicate of that question – Evan Bechtol Jul 12 '15 at 14:54
  • @EvanBechtol: I think it is sufficiently similar that the same approach applies. – sds Jul 12 '15 at 14:56
  • @Tom Klino Besides the last and the third, rest can be easily implemented in log n time. What do you think? – Sumeet Jul 12 '15 at 15:07
  • Well, according to my proffessors I will lose 90% of the score if I don't manage to implement one of the requirements, so not doing 2 will lose me 99%, which is bad :-( – Tom Klino Jul 12 '15 at 16:04
  • @sds this question is not even remotely similar to this, why would you mark it as duplicate? – Tom Klino Jul 12 '15 at 16:08

1 Answers1

-1

You could use a Red-Black to accomplish this.

Red-Black Trees are very fast data structures that adhere to the requirements you have stated above (the last two would require slight modification to the structure).

You would simply have to allow for duplicate keys, since Red-Black Trees follow the properties of Binary Search Trees. Here is an example of a BST allowing duplicate keys

Red-Black Trees are sufficient to maintain running time of:

  • Search: O(log N)
  • Insert: O(log N)
  • Delete: O(log N)
  • Space : O(N)

EDIT: You could implement a Self-Balancing Binary Tree, with modification to allow duplicate keys and find the oldest key (see above reference). Building on this, a Splay Tree can meet all of your requirements with an amortized runtime of O(log N)

For finding FREQ_SUM(S,z):
Since search runs with an amortized time of O(log N) and you are searching for 2 nodes in the tree you end up with runtime of O(2*log N). But when considering runtime, scalar constants are ignored; you result with a runtime of O (log N). You then find the node 'z', with runtime of O(log N);

This is the fundamental runtime of a search utilizing a Binary Search Tree, which the Splay tree is built on.

By using the Split operation, you can return two new trees: one that contains all of the elements less than or equal to x, and the other that contains all of the elements greater than x.

Community
  • 1
  • 1
Evan Bechtol
  • 2,855
  • 2
  • 18
  • 36
  • How can I delete the oldest key in `O(lg n)` time. In a red black tree I need to know the value of the key in order to delete it in that time. Is there a way I can find out the value of that key in less than that time? – Tom Klino Jul 12 '15 at 16:12
  • @TomKlino I have read your comment and updating answer shortly – Evan Bechtol Jul 12 '15 at 17:41
  • I can see how that solves *most* of the requirments, but I don't see how one can implement `FREQ_SUM(S,z)` on such a tree with time complexity of `O(lg n)` – Tom Klino Jul 13 '15 at 08:10
  • I don't think you really understood what `freq_sum(S,z)` does. There is no node `z`. `z` is the target sum of the frequencies of two keys in the tree. Also, you don't know which combination of two keys (if any) will result in such a sum, so you don't know what key you are looking for and therefor looking for it is not `O(lg n)`. Unless you think I misunderstood your explanation, this data structure doesn't seem to comply with the requirements. – Tom Klino Jul 13 '15 at 17:16
  • If the key that you are searching for doesn't exist, the runtime will always be above O (log N), without some type of constraint built-in to check. Otherwise you run into a situation where you must look though all N nodes – Evan Bechtol Jul 13 '15 at 17:20