Toby Eggitt

Ranch Hand

Posts: 58

1

posted 2 weeks ago

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

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

Ranch Hand

Posts: 103

17

posted 2 weeks ago

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.

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

Toby Eggitt

Ranch Hand

Posts: 58

1

Pierre-Yves Saumont

Author

Ranch Hand

Ranch Hand

Posts: 103

17

posted 2 weeks ago

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?

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

posted 2 weeks ago

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.

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

posted 1 week ago

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

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. |