C# problema de referencia

Question

Estoy tomando un curso de algoritmo en la universidad, y para uno de mis proyectos quiero implementar un árbol rojo-negro en C# (la implementación en sí no es el proyecto, sin embargo, algo decidí elige ayudarme).

Mi árbol rojo-negro debe contener claves de cadena, y el objeto que he creado para cada nodo tiene este aspecto:

class sRbTreeNode 
{ 
    public sRbTreeNode Parent = null; 
    public sRbTreeNode Right = null; 
    public sRbTreeNode Left = null; 
    public String Color; 
    public String Key; 

    public sRbTreeNode() 
    { 
    } 

    public sRbTreeNode(String key) 
    { 
     Key = key; 
    } 
} 

ya he añadido algunos métodos generales para imprimir el árbol, la búsqueda de la raíz, min/tecla máx (por alfabeto), etc ...

Tengo problemas para insertar nodos (por lo tanto, construir el árbol). Quien esté familiarizado con los árboles rojo-negro sabe que al agregar un nodo a un lado, podría haber cambiado el equilibrio del árbol. Para solucionar esto, debe "rotar" alrededor de los nodos en el árbol para equilibrar el árbol.

Escribí un método RightRotate y LeftRotate en pseudocódigo, y luego cuando traté de implementarlo en C#, me encontré con un montón de problemas de referencia con el objeto sRbTreeNode que creé.

Este es el pseudo-código que escribí para el método LeftRotate:

LeftRotate(root, node) 
    y <- node.Right; 
    node.Right <- y.Left; 
    if (y.Left != null) 
     y.Left.Parent <- node; 
    y.Parent <- node.Parent; 
    if (node.Parent = null) 
     root <- y; 
    else 
     if (node = node.Parent.Left) 
      node.Parent.Left = y; 
     else 
      node.Parent.Right = y; 
    y.Left <- node; 
    node.Parent <- y 

he recibido una sugerencia para ponerlo en práctica en línea recta, pero sin utilizar la palabra clave 'ref', que he intentado en un principio. Esto es cómo lo hice:

public static void LeftRotate(sRbTreeNode root, sRbTreeNode node) 
    { 
     sRbTreeNode y = node.Right; 
     node.Right = y.Left; 
     if (y.Left != null) 
      y.Left.Parent = node; 
     y.Parent = node.Parent; 
     if (node.Parent == null) 
      root = y; 
     else 
      if (node == node.Parent.Left) 
       node.Parent.Left = y; 
      else 
       node.Parent.Right = y; 
     y.Left = node; 
     node.Parent = y; 
    } 

Ahora, cuando puedo depurar, veo que funciona bien, pero los objetos que pase a este método sólo se rotan dentro del alcance del método. Cuando deja este método, parece que no hubo ningún cambio en los nodos reales. Es por eso que pensé en usar las palabras clave 'ref' en primer lugar.

¿Qué estoy haciendo mal?

Answer 1

Debido a que en el cuerpo de su método de hacer esto:

root = y; 

que necesita para pasar root con un modificador ref. node no necesita uno, porque node nunca se actualiza para apuntar a un ndoe diferente. .

Answer 2

No veo por qué debería haber tenido problemas con las referencias: los nodos izquierdo/derecho/principal se pueden copiar igual que en este pseudocódigo.

Debería poder expandirlo a C# sin demasiado alboroto, a menos que esté usando la palabra clave 'ref', en cuyo caso podría obtener resultados impredecibles.

Quizás si pudiera mostrar el código que ha escrito hasta ahora, y podemos ayudar a depurar eso.

Answer 3

Mis recomendaciones:

• no incluyen punteros de padres. No son esenciales para los algoritmos de inserción o eliminación y harán que su código sea más complejo. Por ejemplo, LeftRotate se puede escribir con solo un parámetro y será aproximadamente la mitad de largo si no utiliza punteros primarios.
• Utilice enum para la propiedad Color en lugar de string, e inicialícela en el constructor.
• Lea this article si no lo ha hecho ya.