why moveRedRight doesn't keep the tree left leaning?

Author: tiendo1011Created Apr 23, 2025Updated Apr 23, 2025

Here is the current code, with my comment about how it results in a right leaning red black tree

private Node moveRedRight(Node h) {
    flipColors(h);
    // here h is black, h.left & h.right are red
    if (isRed(h.left.left)) {
      h = rotateRight(h);
      // here h is black, h.left, h.right, h.right.right are red
      flipColors(h);
      // here h is red, h.left & h.right are black, h.right.right is red -> right sub-tree is a right leaning red black tree
    }
    return h;
  }

with a simple additional call, it will keep the right sub-tree under h as a left leaning red black tree

private Node moveRedRight(Node h) {
    flipColors(h);
    // here h is black, h.left & h.right are red
    if (isRed(h.left.left)) {
      h = rotateRight(h);
      // here h is black, h.left, h.right, h.right.right are red
      
      h.right = h.right.rotateLeft()  // <- additional call here
      // here h is black, h.left, h.right, h.right.left are red

      flipColors(h);
      // here h is red, h.left & h.right are black, h.right.left is red -> left leaning red black tree
    }
    return h;
  }

Keeping the right sub-tree left leaning, before passing it to delete or deleteMin makes it easier to reason about, i wonder why the code skips it

Source: kevin-wayne/algs4

View original on GitHub View discussion on GitHub