Keep an augmented balanced BST. Augmented data: number of elements in the right and left subtrees .
Insertion: logn Find Median: logn Cheers Nikhil Jindal Delhi College of Engineering On Fri, Sep 17, 2010 at 12:09 PM, vikas kumar <[email protected]>wrote: > struct list > { > median --> median from the start to num > number --->number > list *next > }; > > during insertion : insert in sorted LL > after that all subseq node's median has to be modified > O(n) > during median_retriev > check the median value and return that > O(1) > > I assumed deletion is not happening. if supported , can be done in > O(n) > > On Sep 15, 8:24 pm, bittu <[email protected]> wrote: > > Propose a data structure that would store numbers, without any > > knowledge about them, and allow to perform the operations: insert, get > > median, as efficiently as possible same as before, only this time the > > numbers are from a group V, which is |V|<<n > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
