[Repaso de Materia] - Árboles Rojo-Negro

[maromero-21]

Estaba repasando la materia sobre árboles rojo-negro, en particular el código entregado para el caso general:

Al revisar el ejemplo de inserción (41, 38, 31, 12, 19, 8), me surgió una duda respecto a cómo se ejecuta la inserción del valor 31. Al inicio de dicha inserción, el árbol se encuentra así:

Según mi razonamiento, ocurre lo siguiente:

1. Se llama a FixBalance(x = 31).

2. El padre de x = 31 es x.padre = 38, que es de color rojo, por lo que entramos al while.

3. El tío de 31 es x.uncle = NULL, y por lo tanto se considera negro. En consecuencia, no entramos al if (t.color == rojo) y pasamos al else.

4. Luego, x = 31 es hijo izquierdo, por lo que no es hijo interior de su padre. En consecuencia, no se ejecutan ni Rotation(x.padre, x) ni x <- x.padre. Hasta este punto: x = 31 (ya que x <- x.padre NO SE EJECUTA), x.padre = 38 y x.padre.padre = 41.

5. Posteriormente, cambiamos el color del padre y del abuelo.

6. Mi duda surge en la llamada a Rotation(x.padre.padre, x), ya que en este punto estaríamos intentando rotar al abuelo con su nieto (Rotation(41, 31)), lo cual no parece tener sentido.

¿Hay algún error en mi razonamiento al analizar el árbol a partir del código? Conceptualmente entiendo que la rotación correcta se realiza entre los nodos 41 y 38 para lograr el balance, pero no comprendo por qué, al seguir el código paso a paso, se llega a la conclusión de que la rotación se efectúa entre 41 y 31, y no entre 41 y 38.
¡De antemano, muchas gracias!