You can maintain the size. or it can be computed in at worst linear time. In first method, the only difference is that it will make the kth smallest element the root of the tree. When in 2nd method it goes to left, in first method it will also go to left but rotate the tree right.
Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay On Wed, Dec 9, 2009 at 9:45 PM, Vikram Sridar <vikramsridar...@gmail.com>wrote: > read augmenting data structures (chapter 14 i think) in Introduction in > Algorithms by Corman.. if an extra attribute is added to each of the nodes > storing the number of elements in the sub tree rooted at the node, this can > be done easily.. the extra is neither global or static(as it is created n > destroyed with each node).. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
