Red-black Tree Rotation: When I have y = x.right; x.right = y.left. Is it the same to write y.left.p = x as x.right.p = x

Question

In CLRS, the authors introduce the rotation operation in red-black tree by following pseudocode:

LEFT-ROTATE(T, x)

    y = x.right        # Line 1
    x.right = y.left   # Line 2
    if y.left ≠ T.nil  # Line 3
        y.left.p = x   # Line 4
    y.p = x.p
    if x.p == T.nil
        T.root = y
    elseif x == x.p.left
        x.p.left = y
    else x.p.right = y
    y.left = x
    x.p = y

where attribute .left, .right, .p corresponding to its left, right child, and its parent. T is the tree.

My main questions lie in Line 3 and Line 4:

1. Why do I need to have the if condition of Line 3? The book says that NIL is actually a leaf of the red-black tree, so I assume that NIL can also have parent pointer. These codes should still work without Line 3.

2. With the Line 1 and Line 2, can I write Line 4 as x.right.p = x? If they are actually the same, is there a reason that the author chose to write it as y.left.p = x?

My instinct is that x.right.p = x is different from y.left.p = x. However, I cannot find a good explanation for this. I've checked out the definition of pointers, but it is still quite confusing after I googled a lot...

Answer 1

Note: I did not put parent relationship arrow on every diagram to eliminate some clutter.

The null node can not have parents, as the diagram shows. There is more in depth explanation in here

1. as diagram shows, the check on line 3 is not necessary, if y.left NEVER null. If this is not guaranteed, this check is to prevent "null pointer dereference" error".

2. the choice of use y.left.p = x is user preference. To me, it is a lot clearer. We are make the "y left subtree into x right subtree".

The example @HolderRoy showed will work, but it makes an additional allocation to possibly store the y.left pointer, foreach function call.

Answer 2

After reading last line of your description, I noticed that you didn't learn pointers, so it maybe hard for you to understand why we need to judge if something is T.nil. But I still try to answer your question, I hope i can explain it clearly.

1. In terms of data structure, surely you needn't Line 3, you need to adjust y.left.p in any case.

   However, for a given language, just use C/C++ as example, we use NULL or nullptr for leaf and root's parent, which means it's nothing. Just come to think of it, is it necessary to cost memory as many as tree nodes to save useless leaves? Of course not. So we mark it as NULL pointer, which means nothing, and alse has no p, left or right.

   Conclusion comes that it depends on your implementation whether you should judge T.nil at Line 3.

2. Yes, you can. after x.right = y.left, x.right and y.left is temporarily the same thing, so x.right.p and y.left.p is just the same.

   For line 2~4, you can also write like this:

beta = y.left;
x.right = beta; 
if beta != T.nil
    beta.p = x;