search

emory-courses / dsa-java

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

[QZ4] how far do we need to explain the balance() method? #105

Closed zche377 closed 3 years ago

zche377 commented 3 years ago

I'm working on the quiz question "Explain how the balance() methods in AVLTree and RedBlackTree keep the trees balanced (or fails to keep them balanced) after a removal." My question is, are we explaining why it's sufficient to start balancing from this certain node up to the root, or we need to explain from line to line how each balance() method reduces the level difference between its left and right child? Also, when we say "balanced" are we considering perfectly balanced for RedBlackTree? Thank you!

jdchoi77 commented 3 years ago

@zche377 the explanation doesn't have to be long but sufficient enough to show that the balancing works with the way it's written those methods. And yes, balancing means perfectly balanced.