@Yan Wang: Thanks a lot !! On Wed, Aug 25, 2010 at 12:19 AM, Yan Wang <[email protected]>wrote:
> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 > >> > <[email protected]>wrote: > >> > > >> > > Actually, a linear data structure like a linked list is also a > >> > > specific kind of tree structure. > >> > > >> > > 2010/8/23 Raj N <[email protected]>: > >> > > > 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 [email protected]. > >> > > > To unsubscribe from this group, send email to > >> > > > >> > > [email protected]<algogeeks%[email protected]> > <algogeeks%[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]<algogeeks%[email protected]> > <algogeeks%[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]<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]<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]<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.
