How to rotate nodes in balanced search binary trees

Let's call the rotated nodes of (a) and (b). In addition, the pointer (P) is the root pointer, (Q) is the left pointer of (b), (R) is the right pointer of (a) and the precedence relation of nodes values is as follows: A <= a <= B <= b <= C . The following image shows how the piece of the tree where it rotates (a) and (b) in both directions begins and ends.

It can also be considered that the node at the top, pointed to by (P), is not necessarily root (it may have a parent node above it) and that A, B, and C may not only be nodes but sub- may even be empty subtrees).

Look at the blue and red markings (which show two pieces of the tree that remain the same) and the yellow hands (these, as well as the knot (B), out of the two immutable pieces). Notice that to rotate (a) and (b) it is only necessary to change the yellow pointers (P), (Q) and (R).

To make the rotation of the left tree to the right tree, just make the new value of (P) equal to the old value of (Q), the new value of (Q) is equal to the old value of (R) and the new value of (R) is equal to the old value of (P). That is, something like (Temporário)=(P) followed by (P)=(Q) followed by (Q)=(R) and finally (R)=(Temporário) .

To make the rotation of the right tree to the left tree, just the opposite process, just make the new value of (P) equal to the old value of (R), the new value of (R) equals to the old value of (Q) and the new value of (Q) is equal to the old value of (P). That is, something like (Temporário)=(P) followed by (P)=(R) followed by (R)=(Q) and finally (Q)=(Temporário) .