• Post Reply Bookmark Topic Watch Topic
  • New Topic

Merge two immutable binary trees  RSS feed

 
Toby Eggitt
Ranch Hand
Posts: 58
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is "homework" so don't tell me what to do, but I'd really appreciate some hints on how to start thinking about this.

I need to merge two immutable binary trees. It seems simply traversing one tree and inserting every element into the original tree would likely be very inefficient. But I'm not sure how else to go about this. I pondered making an ordered list from the contents of both and building the new tree from that, but I'm not sure if that's better or not. Am I missing something obvious?

Thanks for any nudges,
Toby
 
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 103
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
An immutable binary tree will probably be implemented as a Tree interface or abstract class and two sub classes that I will call E (empty tree) and T (non empty).

The E implementation of a merge method is obvious.

For the T implementation, here is what you have to do (considering "this" means the Tree in which the merge method is defined and "parameter" means the tree to merge:

- If the parameter tree is empty, return this.

- If the root of the parameter is higher than this root, remove the left branch of
the parameter tree and merge the result with this right branch. Then merge
the result with the parameter’s left branch.

- If the root of the parameter is lower than this root, remove the right branch of
the parameter tree and merge the result with this left branch. Then merge the
result with the parameter’s right branch.

- If the root of the parameter is equal to this root, merge the left branch of the
parameter with this left branch and merge the right branch of the parameter
with this right branch.

I do not explain more since you want only hints and not the solution.

Note that this is explained in lot of details in chapter 10 section 4 of Functional Programming in Java (Manning Publications)

The implementation is less than 10 lines long.
 
Toby Eggitt
Ranch Hand
Posts: 58
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks, I'll go tinker with this and see where I get.

Appreciate the input!
 
Toby Eggitt
Ranch Hand
Posts: 58
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK, I believe I understand this now, thanks. And if confusion remains, I can go read your book.

Merci bien Pierre!
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 103
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome!

But note that implementing this algorithm is probably not the solution to your problem.

As you said this was homework, I assume you're asked for more than that.

This solution is theory only. It would not be acceptable for a professional project.

As a teacher, I would only rate this answer from 20% to 50% depending on the expected level.

What you should do is probably not implement a fully working solution, but ask the right questions about your simple solution, and provide the right answers.

If you intend to do this by yourself, you might want to stop reading here.

Otherwise, I'll give you some hints below in the form of questions you should be asking to yourself. Stop reading when you think you have enough to continue on your own. The answers to these questions are of course in my book, but if you need them, I can post them here.

You should think about the merge method as a function taking a pair of threes as its argument and returning a tree.

Is your solution a true function?

If you think it is, can you explicitly describe the domain and codomain of this function?

How long will it take for your implementation to compute the result?

Might it throw an exception?

Will it always terminate (either by returning a resulting tree or throwing an exception)?

What about the cardinality of the result compared to the cardinality or the arguments?

What may happen if you swap the two elements of the argument pair?

If by answering the above questions it appears that the solution is not optimal, what should you do to make it work?
 
Toby Eggitt
Ranch Hand
Posts: 58
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In my original post, you doubtless noticed my comment about "inefficient" So, yes, I think that your questions are exactly what I'm supposed to dive into, and I rather suspect I might not (educationally) up to it. But I'm also not ready to give up yet. All that said, I have a Safari account, so I have access to your book if/when I decide to take the PhD candidate's approach and "review the literature" ;)

Meanwhile, thanks for all your comments, they've been very helpful, and as requested, avoided giving the key secrets that I'm seeking away and thereby avoided spoiling the story.

Cheers,
Toby.

 
Toby Eggitt
Ranch Hand
Posts: 58
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, homework submitted successfully. Now I can take a more serious look at your book without feeling like I would have cheated.

What I did, in the end, was pretty much what I'd outlined in my original post.

1) I created a mechanism that created an ordered list from a tree. I made sure to build the list by pushing items onto the front of the list, so that every element in it was built only once, rather than building it from left to right, which I figured would force reconstructing the entire tail of the list with every addition, and be desperately inefficient.

2) I created a mechanism that merged two ordered lists into a single ordered list. Again, assembling from the right hand end backwards, ensures (I think, at least!) that this has a decent performance.

3) Finally a mechanism to build a (tolerably balanced) tree directly from an ordered list by repeated subdivision. Again, the result should be that every sub-tree is built only once.

The marking (it's an online course) is automatic, but the did warn us that poor implementations would time out and fail the test.

I'm pretty happy that this doesn't seem like a disastrously bad approach, and it's "entirely mine" rather than the (frankly more academically appropriate "read the book, implement the standard solution". Anyway, now I can go read the book properly and find out what would have been better, without risking losing the sense of achievement that came from banging my head against this for a dozen hours or more!

Thanks for the thought topics Pierre, also for not spoiling the story, and now thanks for the book which I'll delve into properly now.

Cheers,
Toby
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!