Deletion in Left Leaning Red Black Trees

Question

I am learning about Left Leaning Red Black Trees.

In the deletion algorithm peresented in the paper, if the key matches for a node and the right subtree is NULL for that node, then that node is deleted. But there may be a left subtree as well which is not considered.

I am not able to understand why would the left subtree be NULL as well. Similar thing is done when deleting the minimum or the maximum as well. Could anyone please guide me on this?

Answer 1

It seems you are speaking about this piece of code:

if (isRed(h.left))
  h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
  return null;

Here left descendant cannot be "red" because preceding code would rotate it to the right.

Also left descendant cannot be "black" because in this case there is a path to the left of h containing at least one "black" node while no path to the right of it has any "black" nodes. But in RB-tree the number of black nodes on every path must be the same.

This means there is no left descendant at all and node h is a leaf node.

In deleteMin function there is no need to check right sub-tree if left sub-tree is empty because no right sub-tree of LLRB tree can be greater than corresponding left sub-tree.