@Dave: you mean need to generate an AVL tree instead. On Fri, Jun 25, 2010 at 12:24 PM, Dave <[email protected]> wrote:
> You'll have to create a balanced BST. Otherwise, depending on the > order of the dataset, it might degenerate into a linked list, which > doesn't make searching an O(log n) process. > > Dave > > On Jun 25, 12:07 pm, Anand <[email protected]> wrote: > > The most useful data structure would be BST. > > Each node will have data value and its count. count indicates the number > of > > times it is repeated in a sequence. Below is the algo to creat a binary > > search tree. > > > > insert_node(int data, node root) > > { > > if(root == NULL) > > { > > root = malloc(); > > root->right = NULL; > > root->left = NULL; > > root->data = data; > > root->count =1; > > } > > else if(root->data == data) > > { > > root->count++; > > } > > else if(data < root->data) > > root->left = insert_node(data, root->left); > > else > > root->right = insert_node(data, root->right); > > > > } > > > > creation of binary search tree will take O(logn) > > Take inorder traversal of above binary tree to get the sorted sequence in > > O(nlog(logn)) also while doing inorder traversal while printing the root > > value also check the count and repeat value that many time. > > On Fri, Jun 25, 2010 at 5:21 AM, sharad kumar <[email protected] > >wrote: > > > > > > > > > You are given an unordered sequence of n integers with many > duplications, > > > such that the number of distinct integers in the sequence is O(log n). > > > Design a sorting algorithm and its necessary data structure(s), which > can > > > sort the sequence using at most O(n log(log n)) time. > > > > > Give the detailed design. > > > > > -- > > > 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%2bunsubscr...@googlegroups.com> > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > > > - Show quoted text - > > -- > 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.
