@Dave n Harshi, thanks for your answer. I am still not clear very much . May be u can help in elucidating your replies.
If such a tree is degenerate, then the complexity of search is O(n), but if it is a well-balanced tree, where some nodes may have 'k' children and some nodes may have 'm' children , (where 'k' and 'm' are more than 2 and may not be necessarily equal) , then what would be the comlexity of searching? Would it of the order of log_2(n) or some other order like log_k(n) ? Or, Is it that the base of the logarithm is not at all important here? I hope I have made my doubt clear. ~Himanshu Aggarwal On Sun, Apr 11, 2010 at 9:01 AM, Dave <[email protected]> wrote: > Your statement about the complexity of searching a binary search tree > applies only if the tree is balanced. In a degenerate tree, e.g., > where each node has only one son, so that the tree is essentialy a > linked list, the complexity of searching is O(n). > > Dave > > On Apr 10, 10:56 am, Himanshu Aggarwal <[email protected]> > wrote: > > Hi, > > > > The book on data structures by Langsam and Tanenbaum gives an alternate > > representation of trees as : > > > > struct treenode { > > int data; > > struct treenode * son; > > struct treenode * sibling; > > > > }; > > > > Such type of nodes can be used to make trees in which each node can have > any > > number of siblings. > > > > I am unable to understand the algorithmic complexity of searching for a > node > > in such a tree? > > > > While a simple binary search tree gives search complexity as log_2(n), > where > > 'n' are the number of nodes in the tree, does such a tree also gives > > logarithmic complexity? In case it gives a logarithmic complexity, what > > would be the base of logarithm in this case. Would it be 2 or some number > > 'k' where 'k' might be dependent on certain factors? > > > > Also, what might be the exact searching algo in this kind of a tree? Some > > pseudo code would be really appreciated. > > > > Thanks for your help in understanding this problem. > > > > With Regards, > > Himanshu > > -- > 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.
