Problem scenario

To see how the TreeMap class removes red-black trees, start with the remove method, when seeing the deleteEntry(Entry

p) method:
,v>

These are the three lines of code highlighted in red:

p.key = s.key;

p.value = s.value;

p = s;

**** assign the key of the successor node to the key of the node to be deleted, assign the value of the successor node to the value of the node to be deleted, and point P to the successor node.

My doubts

The key and value have been assigned to the replacement node P to be deleted. Why point P to S? Here, I mistakenly thought that the p node pointed to the S node, and the position of the node to be deleted became S. In fact, my understanding is completely wrong.

The solution

I am confused because I do not fully understand variables, objects, method areas; The relationship between stack and heap. After a few hours of agonizing, I came to the following conclusion, which can be visually expressed in a picture:

P is a variable, stored in the stack, and objects created by new are stored in the heap; Variables in the stack point to objects in the heap through Pointers. The p.key = S.key statement changes the key of the object pointed to by the variable in the stack to the key of the object pointed to by the variable s in the stack; The p.value = s.value statement changes the value of the object pointed to by the p variable in the stack to the value of the object pointed to by the S variable in the stack; And then I’m going to point the p variable on the stack to the object that S points to. That’s a pretty standard explanation.

If the problem is placed in a red-black tree, p is a node to be deleted in the tree, and S is the successor node of P. To replace the key and value of P with the key and value of S, p points to S. It is difficult to understand if the understanding is centered on P, which is a wrong direction. The correct way to understand it: Use the stack s variable points to the object’s key values and the value assigned to the stack of p variable points to the key value and the value of p is pointing to the object is in the tree you want to delete the be replaced node, using the subsequent replaced node, and the assignment operation refers to the node, is in the replacement and its parent don’t have to in back, left and right subtrees assignment; And then you point the p variable in the stack to the object that S pointed to in the heap before. The object that p pointed to before is still in the heap, but not directly accessible through P.

One thing to summarize here: Variables in Java are just references to objects in the heap, not the actual objects themselves. A variable is just a reference to an object. A variable is just a reference to an object. A variable is just a reference to an object.