It's called as Splaying, accessing any node results in that node becoming the root.
The main idea is that some node which is currently being accessed might get accessed again or sometime near in future. Hence, for better search times, splaying is a good idea. (AVL tree rotations will help you maintain BST property and making the node root) On Nov 1, 11:34 am, kumar raja <rajkumar.cs...@gmail.com> wrote: > @Dave : > Wonderful answer sir.. > > On 31 October 2011 12:50, Dave <dave_and_da...@juno.com> wrote: > > > > > > > > > > > @Ankuj: Your method would be O(n), where n is the number of nodes in > > the tree. However, it can be done with a sequence of tree rotations. > > If the desired node is not the root of the tree, rotate it with its > > parent. This preserves the BST property and makes the desired node one > > level closer to the root. A rotation can be done in constant time, so > > the work required is O(original level of the node), which would be > > O(log n) if the tree happened to be balanced. See > >http://en.wikipedia.org/wiki/Tree_rotation > > for algorithmic details. > > > Dave > > > On Oct 31, 11:43 am, Ankuj Gupta <ankuj2...@gmail.com> wrote: > > > Given a node of a BST, modify it in such a way that the given node > > > becomes the root. The tree should still be BST. One way I could get is > > > store the Inoder traversal of the tree. Find that node in the > > > traversal and recursively make the BST. > > > -- > > 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. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
