Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different.
On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > Read the slides i uploaded. They explain what rotation does in a BST. > > Also you might like to refer to Red Black Trees in CLRS.... that chapter > explains rotations. > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > > > On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf > <rohit.kumar.sa...@gmail.com>wrote: > >> but still the binary tree solution is of more practical use.i will explain >> the solution once i reach my comp >> >> >> On 4/11/10, Nikhil Agarwal <nikhil.bhoja...@gmail.com> wrote: >> > >> > >> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >> rohit.kumar.sa...@gmail.com> >> > wrote: >> >> >> >> Time complexity is O(n log n). But the last solution I gave has O(n). >> >> >> >> What did u not understand abt thesolution >> > >> > >> > @Rohit Please explain how that Binary tree solution works. >> >> >> >> >> >> -------------------------------------------------- >> >> Rohit Saraf >> >> Second Year Undergraduate, >> >> Dept. of Computer Science and Engineering >> >> IIT Bombay >> >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> >> >> >> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >> >> <dona.1...@gmail.com> wrote: >> >>> >> >>> >> >>> >> >>> On 11 April 2010 10:46, Rohit Saraf <rohit.kumar.sa...@gmail.com> >> wrote: >> >>>> >> >>>> Construct a binary tree from the data (maintain the size of subtree >> >>>> under each node). >> >>>> Do rotations till the left subtree does not have size k. Rotation is >> a >> >>>> constant time operation. >> >>>> Please prove the correctness of your algorithm with the time >> complexity >> >>>> >> >>>> -------------------------------------------------- >> >>>> Rohit Saraf >> >>>> Second Year Undergraduate, >> >>>> Dept. of Computer Science and Engineering >> >>>> IIT Bombay >> >>>> http://www.cse.iitb.ac.in/~rohitfeb14 >> >>>> >> >>>> >> >>>> >> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond < >> patidarc...@gmail.com> >> >>>> wrote: >> >>>>> >> >>>>> nice solution appreciate it. but your algorithm is wasting time in >> >>>>> finding all the element... >> >>>>> instead of that just find boundary line kth element which can help >> as >> >>>>> in finding element greater that kth and element small than kth and >> that >> >>>>> soluton can be done in O(N) >> >>>>> >> >>>>> >> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >> >>>>> <jaanu.cher...@gmail.com> wrote: >> >>>>>> >> >>>>>> >> >>>>>> 1) Construct max heap by taking first k elements in an array >> >>>>>> 2) if k+1 element less than root of max heap >> >>>>>> a) Delete root of max heap >> >>>>>> b) Insert k+1 element in max heap and apply heapify method >> >>>>>> 3) else skip the element >> >>>>>> 4) apply above procedure for all n elements in an array >> >>>>>> >> >>>>>> At last you will get k smallest elements and root is kth smallest >> >>>>>> element in the array >> >>>>>> >> >>>>>> this is O(nlogk) >> >>>>>> >> >>>>>> >> >>>>>> >> >>>>>> ---------------------------------------- >> >>>>>> CHERUVU JAANU REDDY >> >>>>>> M.Tech in CSIS >> >>>>>> >> >>>>>> >> >>>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy >> >>>>>> <abhijith200...@gmail.com> wrote: >> >>>>>>> >> >>>>>>> Can any one tell how to do this when there are 'm' queries like >> >>>>>>> "query i j k" find the kth largest element in between indices i->j >> in >> >>>>>>> an array. >> >>>>>>> When m is large even an O(n) algorithm would be slow. >> >>>>>>> I thinking that each query could be answered in O(sqrt(n)) time >> >>>>>>> So any suggestions ? >> >>>>>>> >> >>>>>>> Thanks >> >>>>>>> >> >>>>>>> >> >>>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond < >> patidarc...@gmail.com> >> >>>>>>> wrote: >> >>>>>>>> >> >>>>>>>> there are better solution of O(n) are posted in the thread....... >> [?]. >> >>>>>>>> using order statices .... >> >>>>>>>> >> >>>>>>>> >> >>>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur >> >>>>>>>> <mukeshraj8...@gmail.com> wrote: >> >>>>>>>>> >> >>>>>>>>> Create a temp array temp[0..k-1] of size k. >> >>>>>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep >> updating >> >>>>>>>>> the smallest element of temp[] >> >>>>>>>>> 3) Return the smallest of temp[] >> >>>>>>>>> Time Complexity: O((n-k)*k). >> >>>>>>>>> >> >>>>>>>>> >> >>>>>>>>> try it ..............for this problem[?] >> >>>>>>>>> >> >>>>>>>>> -- >> >>>>>>>>> You received this message because you are subscribed to the >> Google >> >>>>>>>>> Groups "Algorithm Geeks" group. >> >>>>>>>>> To post to this group, send email to algogeeks@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. >> >>>>>>>> >> >>>>>>>> >> >>>>>>>> >> >>>>>>>> >> >>>>>>>> -- >> >>>>>>>> ~~~~BL/\CK_D!AMOND~~~~~~~~ >> >>>>>>>> >> >>>>>>>> -- >> >>>>>>>> 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<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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> >>>>>> For more options, visit this group at >> >>>>>> http://groups.google.com/group/algogeeks?hl=en. >> >>>>> >> >>>>> >> >>>>> >> >>>>> >> >>>>> -- >> >>>>> ~~~~BL/\CK_D!AMOND~~~~~~~~ >> >>>>> >> >>>>> -- >> >>>>> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> >>>> For more options, visit this group at >> >>>> http://groups.google.com/group/algogeeks?hl=en. >> >>> >> >>> >> >>> >> >>> >> >>> -- >> >>> Thanks & Regards, >> >>> Priyanka Chatterjee >> >>> Third Year Undergraduate Student, >> >>> Computer Science & Engineering, >> >>> National Institute Of Technology,Durgapur >> >>> India >> >>> http://priyanka-nit.blogspot.com/ >> >>> >> >>> -- >> >>> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> >> For more options, visit this group at >> >> http://groups.google.com/group/algogeeks?hl=en. >> > >> > >> > >> > >> > -- >> > Thanks & Regards >> > Nikhil Agarwal >> > Junior Undergraduate >> > Computer Science & Engineering, >> > National Institute Of Technology, Durgapur,India >> > http://tech-nikk.blogspot.com >> > >> > >> > -- >> > 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. >> > >> >> >> -- >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> > > -- > 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. > -- Thanks & Regards Nikhil Agarwal Junior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- 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.
<<338.gif>>
<<361.gif>>
