Here is what you want exactly: http://anuragsharma-sun.blogspot.com/2010/03/converting-bst-to-circular-doubly.html
Hope it helps -Anurag Sharma On Thu, Apr 1, 2010 at 4:54 PM, <[email protected]<algogeeks%[email protected]> > wrote: > Today's Topic Summary > > Group: http://groups.google.com/group/algogeeks/topics > > - [No Subject] <#127b91d593367ca3_group_thread_0> [10 Updates] > - how to convert a BST into a sorted doubly linked > list.<#127b91d593367ca3_group_thread_1>[2 Updates] > - Implementation of Algorithms <#127b91d593367ca3_group_thread_2> [5 > Updates] > > Topic: [No > Subject]<http://groups.google.com/group/algogeeks/t/a93bb1feac751245> > > BlackdiamonD <[email protected]> Mar 31 11:54AM +0530 > ^<#127b91d593367ca3_digest_top> > > is the list is sorted...or in some order... > i feel unless the point in the list in some order eg: sorted, > it will be difficult to get soluiton less than O(n).... > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > > > > abhijith reddy <[email protected]> Mar 31 01:23PM +0530 > ^<#127b91d593367ca3_digest_top> > > I guess she was asking that the per query complexity should be better > that > O(n). > > If that is the case then you can use any of these > Simple RMQ O(sqrt(n)) > Segment/Interval Trees O(lgn) > Binary Indexed Trees O(lgn) > > On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf > > > > > Ashim Kapoor <[email protected]> Mar 31 01:07PM +0530 > ^<#127b91d593367ca3_digest_top> > > I think it can be done in logn time ( I assume the list is sorted, is > there > an order log n sorting algo, then i can even sort it in log n time ? ( > I am > new to algorithms ) ). > > 1. binary search for low=x1. > 2. binary search for high=x2. > > both will take log n time. Print all values between them then in > O(x2-x1) > time. > > Is this correct? > On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf > > > > > BlackdiamonD <[email protected]> Mar 31 11:55AM +0530 > ^<#127b91d593367ca3_digest_top> > > ok...sorry u asked the data structure...... > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > > > > BlackdiamonD <[email protected]> Mar 31 12:48PM +0530 > ^<#127b91d593367ca3_digest_top> > > what if your sort the element.first time.. > applying binary search on list for x1 (getting minimum index ) > applying binary search on list for x2(getting maximum index) > element between this index will be the answer. > complexity:O(log(N)) for getting the range. (not considering the > sorting) > > > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > > > > Anil Kishore <[email protected]> Mar 31 12:48PM +0530 > ^<#127b91d593367ca3_digest_top> > > What do you mean by points ? .. Are you referring to the integer values > stored ? > . > 1.) If the question is, given N integers.. and given x1 and x2, report > all > integers x (x1<=x<=x2), you can't do better than O(N), as going through > input itself takes O(N). > . > 2.) if the question is, given N integers and Q queries, each query is > as > ques1, then you may sort it initially and answer each query. It will be > O( N > log N ) + Q . O ( logN + (x2-x1) ). > > - AK > > > -- > Anil Kishore > > > > > ANUJ KUMAR <[email protected]> Mar 31 05:51PM +0530 > ^<#127b91d593367ca3_digest_top> > > We can make a query tree and then each query will take O(log n+k) time. > > > > > > Priyanka Chatterjee <[email protected]> Mar 31 08:26PM +0530 > ^<#127b91d593367ca3_digest_top> > > The list of N integers is not sorted. > The solution is asked for a particular query. > > @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or > *Segment > Interval trees*. May be you opted for the correct data structure. > Please > give the algorithm. > > @All: Doing a sorting for O(n logn) and then binary search for x1 and > x2 in > O(logn) will be less efficient than the simple solution of O(n). Think > on > the data structure that can optimize it. > Is it possible in time complexity < O(n)? > > > -- > Thanks & Regards, > Priyanka Chatterjee > Third Year Undergraduate Student, > Computer Science & Engineering, > National Institute Of Technology,Durgapur > India > http://priyanka-nit.blogspot.com/ > > > > > abhijith reddy <[email protected]> Mar 31 09:58PM +0530 > ^<#127b91d593367ca3_digest_top> > > > O(logn) will be less efficient than the simple solution of O(n). > Think on > > the data structure that can optimize it. > > Is it possible in time complexity < O(n)? > > If you want to do the operation just once then it cannot be done faster > than > O(n) time. > Even the mentioned data structures require atleast O(n) amount of > preprocessing. > > All the mentioned algorithms are available here > http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static > > Hope it helps > > On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee < > [email protected]>wrote: > > > > > > BlackdiamonD <[email protected]> Mar 31 11:54PM +0530 > ^<#127b91d593367ca3_digest_top> > > *Binary Indexed Trees* or *Segment Interval trees*. building them also > it > will take O(n log(n)) > ..i feel for a particular query it will be difficult less than O(n) > .because > .u must know all the element. > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > > > Topic: how to convert a BST into a sorted doubly linked > list.<http://groups.google.com/group/algogeeks/t/11bc66650caa8fad> > > web-hav <[email protected]> Mar 31 03:08AM -0700 > ^<#127b91d593367ca3_digest_top> > > Algorithm : > > 1 Do inorder traversal and at the time of reading data from tree, add > data to doubly link list. > (Inorder traversal will give you sorted order data and it can be > added to DLL. Thus, we can get sorted DLL.) > > > Code : > > > struct node > { > struct node *left; > int data; > struct node *right; > }; > > struct dllist { > int number; > struct dllist *next; > struct dllist *prev; > }; > > struct dllist *head, *tail, *listnode; > > void bstToDLL(struct node *treenode) { > > treeTraverse(treenode); > > for(listnode = head; listnode != NULL; listnode = listnode->next) { > printf("%d\n", listnode->number); > } > > } > > > > void treeTraverse(struct node *treenode) > { > > if(treenode!=NULL) > { > treeTraverse(treenode->left); > listnode = (struct dllist *)malloc(sizeof(struct dllist)); > listnode->number = treenode->data; > appendToDoublyLinkList(listnode); > treeTraverse(treenode->right); > } > else > return; > } > > > > void appendToDoublyLinkList(struct dllist *listnode) { > > if(head == NULL) { > head = listnode; > listnode->prev = NULL; > } > else { > tail->next = listnode; > listnode->prev = tail; > } > > tail = listnode; > listnode->next = NULL; > } > > > > > > > > > > SHRISH MISHRA <[email protected]> Mar 31 07:33PM +0530 > ^<#127b91d593367ca3_digest_top> > > @web-hav > > *I think the actual problem is in place changing a bst into a > DLL(Doubly > linked list) without using extra space .* > If you are allowed to use extra space then problem is pretty simple and > your > code solves its purpose. > > Shrish Chandra Mishra > CSE NIT,Allahabad > > > > > > Topic: Implementation of > Algorithms<http://groups.google.com/group/algogeeks/t/e6a42a8c7a3d2b1e> > > BlackdiamonD <[email protected]> Mar 31 01:10PM +0530 > ^<#127b91d593367ca3_digest_top> > > you can go through this.: > http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static > and you can follow: Art of Uva online judge > for getting started in this contest... > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > > > > abhijith reddy <[email protected]> Mar 31 01:20PM +0530 > ^<#127b91d593367ca3_digest_top> > > First learn a language of your choice and then you can start solving > over > there > > > > > > naga vinod kumar <[email protected]> Mar 31 05:42PM +0530 > ^<#127b91d593367ca3_digest_top> > > Hii, > > what is Art of Uva online judge ???? Does it contain some > training material like USACO .... > > > > > Umer Farooq <[email protected]> Mar 31 06:01PM +0500 > ^<#127b91d593367ca3_digest_top> > > How much time to u have? If you have got more than a month and u don't > know > any language; then I'll suggest you to learn a programming language > like C++ > or Java. > > In my opinion, C++ is the best language for these kind of problems :) > > Regards > Umer. > > On Wed, Mar 31, 2010 at 5:12 PM, naga vinod kumar > > > > > BlackdiamonD <[email protected]> Mar 31 05:59PM +0530 > ^<#127b91d593367ca3_digest_top> > > ok i previously i written wrong it is > :*Art-of-Programming*-Contest-SE-for- > *Uva > book for basic of programming and some of the solving methods for > problems. > here is the Link > Art_of_Programming_Contest_SE_for_uva.pdf< > http://online-judge.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf> > * > > > On Wed, Mar 31, 2010 at 5:42 PM, naga vinod kumar > > -- > ~~~~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 [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. > -- 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.
