I know what you mean now. It's not very hard to implement your idea. First, construct a usual binary sorting tree based on the original linked list. Notice that I also use the inner nodes to store the elements in the linked list rather than only using the leaf nodes. And the quantity feature you mentioned is considered as an affiliated feature of each node in the tree and can be computed recursivly. Thus the data structure of every node will have two domains to store. One is the data domain which has the node's key and the other one is the feature domain which maintains the node's feature.
Then, compute the quantity feature of each node in the tree. According to your idea, the feature of a given node here is the number of nodes that the subtree, which roots in this given node, has. We denote this feature as f(n), where n represents the given node. Obviously, f(n) = f(n_lc) + f(n_rc) + 1, where n_lc represents the left child of node n and n_rc represents its right child. And if n is a leaf node, then f(n) = 1. This is clearly a recursive computational structure and just fits computing on a tree structure. For more detailed introduction, please refer to Chapter 14.2 "How to augment a data structure" of the book "Introduction to Algorithms, Second Edition, MIT Press". On Mon, Aug 23, 2010 at 6:50 PM, Raj N <rajn...@gmail.com> wrote: > I came across this example that the leaves of the tree can be the nodes of a > linked list and the inner nodes of the tree can be the number of left > subtrees. This kinda data structure can be used to find the kth element of a > linked list very easily. I was not able to implement such an idea.. Can > anyone help me doing that ? > > On Tue, Aug 24, 2010 at 5:54 AM, Adam <wangyanadam1...@gmail.com> wrote: >> >> What do you exactly mean? You want to represent a linear structure by >> using a tree structure? >> You can imagine a linked list as a tree with all its root and inner >> nodes only having one descendent/child node. >> >> On Aug 23, 10:50 am, Raj N <rajn...@gmail.com> wrote: >> > What will be the representation. How do you define left and right >> > pointers >> > of the tree for a linked list. >> > >> > On Mon, Aug 23, 2010 at 10:35 PM, Yan Wang >> > <wangyanadam1...@gmail.com>wrote: >> > >> > > Actually, a linear data structure like a linked list is also a >> > > specific kind of tree structure. >> > >> > > 2010/8/23 Raj N <rajn...@gmail.com>: >> > > > Hi, >> > > > Could anyone help me representing linked list in the form a binary >> > > > tree ? >> > >> > > > Thanks !! >> > >> > > > -- >> > > > 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. >> 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. > -- 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.
