search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[QZ4] #117

Closed mihirpatil001 closed 3 years ago

mihirpatil001 commented 3 years ago

Do we need to balance the height of the tree as it's done in AVL trees when doing the balance method implementation for this quiz? The quiz description in Exercises 4.4 doesn’t mention adjusting for the height of the tree as its done in AVL, but some of the answers to the GitHub issues are starting to confuse me as saying otherwise. One reply in #106 says we don’t need to do the balancing when the three conditions in the assignment description aren’t met, but then in #114 the reply says that we do need to make sure the output tree is a balanced tree as done with AVL. Can more clarification be provided on this, please?

lujiaying commented 3 years ago

Sorry for the confusion. I think I might say something wrong.

I am now forwarding the concern to Dr. Choi.

My logic is 1) the input tree must be a balance one. 2) Then after rotation, such a balanced tree is still balanced. 3) If a input balance tree not met the condition list in quiz04, no rotation action is required.

Balance here means the height difference is less or equal to 1.

lujiaying commented 3 years ago

In case I mess up anything. I would not add my comments but just refer Dr. Choi's reply.

As it builds the tree, if the conditions are met, it will perform the balancing which may or may not end up generating a balanced tree

mihirpatil001 commented 3 years ago

Ok, thank you for following up on this, I really appreciate it!