MHB How to Efficiently Merge a Sorted List and a Pre-Order Sorted Tree?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Sets
AI Thread Summary
The discussion centers on implementing a Merge() operation for two sets, S1 and S2, where S1 is a sorted list and S2 is a pre-order sorted tree. The goal is to achieve a time complexity of O(n1 + n2), with n1 and n2 representing the number of elements in S1 and S2, respectively. The provided pseudocode attempts to merge the two structures by iterating through both sets, comparing their elements, and creating a new merged list. Key points include the need for proper traversal of the tree structure and handling of the linked list to ensure all elements are included in the final merged output. The pseudocode has some logical flaws, particularly in the traversal of S2 and the initialization of the merged list, which may need refinement to meet the desired complexity and functionality.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hi! (Smile)

We are given two sets $S_1$ and $S_2$.
We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree.
I have to write a pseudocode, that implements the operation Merge() of the sets $S_1$ and $S_2$.
The time complexity of the algorithm should be $O(n_1+n_2)$, where $n_1$ is the number of elements of $S_1$ and $n_2$ is the number of elements of $S_2$.Could you give me a hint, how we could do this? (Thinking)
 
Technology news on Phys.org
Is it maybe like that?

Code:
SetMerge(LNODE *S1, TNODE *S2)
      LNODE *p1=S1
      TNODE *p2=S2
      LNODE *S, slast, new
      while(p1 != NULL p2 != NULL)
           new=newcell(NODE)
           if(p2->data < p1->data)
                 new->data=p2->data
                 if(p2 != NULL)
                     p2=p2->LC
                 else
                     p2=p2->RC
           else
                 new->data=p1->data
                 p1=p1->next
      new->next=NULL
      if(S==NULL)
         S=new
         slast=new
      else
         slast->next=new
         slast=new
      while(p1 != NULL)
         new=newcell(NODE)
         new->data=p1->data
         new->next=NULL
         if(S==NULL)
            S=new
            slast=new
         else
            slast->next=new
            slast=new

Or have I done something wrong? (Thinking)
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top