check this out.. an efficient algorithm to balance a binary tree in linear time and space. The other famous algorithm(easier one) by sedgewick does not give O(n) but average case linear time. http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf
Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay On Thu, Dec 10, 2009 at 7:38 AM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > 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.
