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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
