Update RedBlackBST.java

[YRFT]

There are two implementations of balance in RedBlackBST. One in put method and another in balance method.

In put method we perform "rotate left" only if the left child is black and the right child is red. That's ok because if both children are red, we do not need "rotate". We can just perform "color flip" to raise the middle node up.

But in balance method, we do "rotate left" if the right child is red and do not check the left child. I can't figure out why we don't check the left child. In the current implementation if both children are red, we will do some useless work, because "rotate left" then "rotate right" will not change the tree. In my opinion, we should check the left child as we did in put method to save some work.

I have modified the code in balance method to include the check for the left child and run some tests with the check method. All the tests have been passed.

Fill redBlackBST with n elements

while redBlackBST is not empty:
    asssert redBlackBST.check()
    redBlackBST.delete(redBlackBST.select(random(0, redBlackBST.size())))

I have been confused for several days and appreciate any feedback. Thank you.

[kevin-wayne]

Thanks! Yes, this code is an improvement that got made in insert() but not balance(). I will propagate the change to the codebase.