CODEWITHSUNDEEP
algorithmsortingdata-structurestree
Nitin Garg
Nitin Garg

Reputation: 2079

Data Structure to maintain numbers

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.

Upvotes: 2

Views: 227

Answers (3)

LiKao
LiKao

Reputation: 10658

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.

Upvotes: 1

jmg
jmg

Reputation: 7414

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

Upvotes: -1

Joop Eggen
Joop Eggen

Reputation: 109567

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)).

Upvotes: 1

Related Questions