4

I need a data structure that supports two operations - delete and search. Now, the delete operation should run in amortized O(1) time, while search should run in O(log n) time.

Search operation should work as follows: look for value specified and if it is here, return value itself. Otherwise, return the nearest greater value (return inorder successor).

What could this data structure be?

Improve this question
8
  • And that is exactly my problem. I don't know how to make delete faster than delete. I don't even know if it is actually possible. Commented Mar 13, 2018 at 9:37
  • The only way that delete can be faster than search is if you know in advance where the element to delete is (for example if you always want to delete the first element in a list). Commented Mar 13, 2018 at 9:58
  • What's the range of values? Commented Mar 13, 2018 at 10:05
  • 1
    Doesn't a hash table/set fit your use case? (delete O(1), look-up O(1)) Also, what does "search" exactly mean? If your values are just integers, if you want to look for an element then you already have it. Do you mean just checking if the element is contained in the structure? Commented Mar 13, 2018 at 10:21
  • 1
    If n is very high but always starts with the sequence 1,2..n, as you commented, it seems you'd be looking for a structure to represent ranges of values rather the values themselves. Commented Mar 13, 2018 at 11:02

3 Answers 3

Reset to default
1

It could be a pair of data structures:

  • binary search tree, holding values
  • hash table, holding pointers to nodes in binary search tree

When you want to search, do the search in binary search tree in O(log n) time. When you want to delete, first find the node in hash table in amortized O(1) and delete in binary search tree in amortized O(1).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Alright, I can surely find node in hastable in O(1). But then you say that I can delete in binary search tree in O(1) - is this really true? It may be true when the node is a leaf, but what about a case with children?
At least in red black trees deletion is amortized O(1), see en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal: 'Mehlhorn & Sanders (2008) point out: "AVL trees do not support constant amortized deletion costs", but red-black trees do'.
Uh, I didn't know red-black trees have deletion in amortized O(1), thanks a lot!
0

If your range is reasonably bound at m, you could implement a Y-fast trie. This supports delete and search for successor in O(log log m) time and takes O(n) space.

You could also use k tries with the same m as buckets with offsets, to represent the range km.

If the number of deletions is small compared to the range, save only the deletions rather than the available numbers.

Improve this answer

Comments

0

Another solution is to start with a hash set that is initially empty. When somebody requests a delete, add that value to the hash set. That's O(1).

There are several ways to proceed after that.

  1. When searching for items, if you encounter a node whose value is in the hash set, mark it as deleted and continue the search. You never remove anything from the tree, but nodes that are marked as deleted are no longer "found." You just return the inorder successor.
  2. When you find an item that was searched for, check the hash set to see if the item was supposed to be deleted. Delete the item and return its inorder successor.
  3. When searching the tree, whenever you run across a node whose value is in the hash set, delete the node and continue the search.

Of course, you'd remove the value from the hash set whenever you marked a node as deleted or removed a node from the tree.

All three of those give you O(log n) search, and amortize the cost of deletions as part of the search process.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.