A question about RedBlackBST.

[YRFT]

https://github.com/nguyenqthai/Algs4Net/blob/master/Algs4Net/RedBlackBST.cs

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 in booksite. All the tests have been passed.

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

[nguyenqthai]

Thank you for pointing that out. I will look at this. Meanwhile, you could send a pull request as well.

[nguyenqthai]

Did you mean this balance(h) method? The case that goes to all steps is in the figure (copied here) from slide #32, of the 3.3 lecture.

` private Node balance(Node h) { Debug.Assert((h != null));

  if (isRed(h.right)) h = rotateLeft(h);
  if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
  if (isRed(h.left) && isRed(h.right)) flipColors(h);

  h.N = size(h.left) + size(h.right) + 1;
  return h;
}

`

[YRFT]

Thank you for your replay.

Yes, in my opinion, we should check the left child whether it is black to save some work. Just as we did in the put method.

    private Node balance(Node h)
    {
      Debug.Assert((h != null));

      if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
      if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
      if (isRed(h.left) && isRed(h.right)) flipColors(h);

      h.N = size(h.left) + size(h.right) + 1;
      return h;
    }

[YRFT]

I really appreciate your replay. It's very helpful to me.

I have just created a pull request to Kevin’s repo https://github.com/kevin-wayne/algs4/pull/101/commits/b2224bfc4ac8fa157addfbbbcfa64b99bfd926e2.

I will pay attention to the pull request and update this issue to reflect the result of the pull request to let you easy to know will the pull request be merged.

[nguyenqthai]

Hi, I saw your pull request. If they approves it, I'll update my C# copy as well. Thanks.

On Sunday, December 13, 2020, 08:27:24 PM CST, YRFT <notifications@github.com> wrote:  

Yes, in my opinion, we should check the left child whether it is black to save some work.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub, or unsubscribe.

[YRFT]

The balance method has been optimized in https://github.com/kevin-wayne/algs4/commit/5729bbb742f985ece102c2d3074421eb2d5e42c2.

I'll close this issue. Thanks again.

[nguyenqthai]

Great! I will update the C# code soon.