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

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.

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;