@Himanshu. from what i think the complexity would be log(n) but the base would be the no. of siblings that the node has.
Check if this answer is correct. On Sun, Apr 11, 2010 at 2:08 PM, Himanshu Aggarwal <[email protected]>wrote: > @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]<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.
