2

Please suggest a data structure to maintain numbers in such a way that i can answer the following queries -

Find(int n) - O(log(n))

Count number of numbers less than k = O(log(n))

Insert - O(Log(n))

It's not homework, but a smaller problem that i am encountering to solve a bigger one - Number of students with better grades and lower jee rank

I have though of an avl tree with maintaining number of nodes in subtree at each nod.But i dont know how to maintain this count at each node when an insert is being done and re-balancing is being done.

Improve this question
1
  • Smells homework... What you've thought about so far? Commented Nov 8, 2011 at 8:44

3 Answers 3

Reset to default
1

I would also try using an AVL Tree. Without looking much deeper into it, I don't think this would be too hard to add. In case of an AVL tree you alway need to know the depth of each subtree for each node anyway (or at least the balancing factor). So it should not be too hard to propagate the size of the subtrees. In case of an rotation, you know exactely where each node and each subtree will land, so it should be just a simple recalculation for those nodes, which are rotated.

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

Comments

1

Finding in a binary tree is O(log(n)), inserting too. If you store the subtree size in the node:

  • you can coming back from a successful insert in a subtree increment the node's counter;
  • on deleting the same.

So subtree size is like a find, O(log(n)).

Improve this answer

2 Comments

These operations are log(n) in balanced binary search trees only. And how to update relevant nodes counter in them in exactly my question.
@NitinGarg: Whenever someone mentions a binary tree they are most likely a balanced tree anyway. Mantaining extra count info on the nodes is just a matter of mantaining invariants whenever you do any operation on the tree
-1

Have a look at the different variants of heap data structures, e.g. here.

Improve this answer

1 Comment

Heaps are also good for finding n smallest numbers. The OP asked for " Count number of numbers less than k". I understand that he is interested in the number of elements smaller than k. That is solvable by repeatedly taking the smallest element, or by inspecting the heap data structure.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.