¿Cómo se puede representar un nodo de árbol B?

Question

Estamos aprendiendo B-trees en clase y se nos ha pedido que los implementemos en código. El docente nos ha dejado la elección del lenguaje de programación y quiero intentarlo en C#. Mi problema es que la estructura siguiente es ilegal en C#,

unsafe struct BtreeNode 
     { 
      int key_num;  // The number of keys in a node 
      int[] key;   // Array of keys 
      bool leaf;   // Is it a leaf node or not? 
      BtreeNode*[] c;  // Pointers to next nodes 
     } 

En concreto, no se le permite crear un puntero para apuntar a la estructura misma. ¿Hay algún enfoque alternativo o enfoque alternativo que pueda usar? Estoy bastante seguro de que DEBE haber una manera de hacer esto dentro del código administrado, pero no puedo resolverlo.

EDIT: respuesta de Eric me señaló en la dirección correcta. Esto es lo que terminé usando,

class BtreeNode 
{ 
     public List<BtreeNode> children;  // The child nodes 
     public static int MinDeg;    // The Minimum Degree of the tree 
     public bool IsLeaf { get; set; }  // Is the current node a leaf or not? 
     public List<int> key;     // The list of keys 
... 
} 

Answer 1

Casualmente, acabo de implementar un btree en C#, para un proyecto personal. Fue divertido. Construí un btree de teclas de tamaño variable ordenadas lexicográficamente (hasta 64 bytes) que presentaban una serie de desafíos, particularmente en torno a averiguar cuándo una página de almacenamiento estaba demasiado llena o demasiado vacía.

Mi consejo, habiendo hecho eso, es la construcción de una capa de abstracción que capta sólo los algoritmos btree en su forma más abstracta, como una clase base abstracta. Una vez que obtuve todas las reglas de btree capturadas en esa forma, especialicé la clase base de varias maneras diferentes: como un btree regular de tamaño de clave fija de 2-3, como uno de mis btrees de fantasía de clave de tamaño variable, y así sucesivamente. .

Para empezar, en ningún caso debe usted hacer esto con punteros. El código inseguro rara vez es necesario y nunca es fácil. Solo los programadores C# más avanzados deben desconectar el sistema de seguridad; cuando lo hace, se responsabiliza por el tipo y la seguridad de la memoria del programa. Si no está dispuesto a hacerlo, deje el sistema de seguridad encendido.

En segundo lugar, no hay ninguna razón para hacer de esto una estructura. Las estructuras se copian por valor en C#; un nodo btree no es un valor .

En tercer lugar, no es necesario para mantener el número de llaves en un nodo; la matriz de teclas sabe cuántas teclas contiene.

En cuarto lugar, me gustaría utilizar un List<T> en lugar de una matriz; ellos son mas flexibles

En quinto lugar, tiene que decidir si las vidas clave en el nodoo en la matriz . De cualquier manera puede funcionar; Mi preferencia es la clave para vivir en el nodo, porque veo que la clave está asociada con el nodo.

En sexto lugar, es útil saber si un nodo bt es la raíz o no; podrías considerar tener dos bools, uno "¿esta es una hoja?" y uno "¿es esta la raíz?" Por supuesto, un btree con un solo elemento en él tiene un único nodo que es tanto de hoja como de raíz.

Séptimo, probablemente va a construir esto para que sea mutable; normalmente uno no hace públicos campos mutables en una clase C#. Puede considerar hacerles propiedades. Además, la lista de los niños puede ser cultiva y encogido, pero su identidad no cambia, por lo que sea referencialmente de sólo lectura:

así que probablemente estructurar mi nodo básico como:

class Node 
{ 
    public int Key { get; set; } 
    public bool IsRoot { get; set; } 
    public bool IsLeaf { get; set; } 
    private List<Node> children = new List<Node>(); 
    public List<Node> Children { get { return this.children; } } 
} 

¿Tiene sentido?

Answer 2

Utilice una clase en lugar de un stuct. Y tira los punteros.

class BtreeNode 
{ 
    int key_num;  // The number of keys in a node 
    int[] key;   // Array of keys 
    bool leaf;   // Is it a leaf node or not? 
    BtreeNode[] c;  // Pointers to next nodes 
} 

Cuando se declara una variable de un tipo de clase, es implícitamente una referencia (muy similar a un puntero en c), ya que cada clase es un tipo de referencia.

Answer 3

Todo lo que necesita para darse cuenta de que un puntero en C es "algo similar" a una referencia en C#. (Hay varias diferencias, pero para los fines de esta pregunta puede concentrarse en las similitudes.) Ambos permiten un nivel de indirección: el valor no son los datos en sí mismos, es una forma de llegar a los datos.

El equivalente de lo anterior sería algo así como:

class BtreeNode 
{ 
    private int keyNumber; 
    private int[] keys; 
    private bool leaf; 
    private BtreeNode[] subNodes; 

    // Members (constructors etc) 
} 

(no me acuerdo mucho de los árboles B, pero si la matriz "claves" que aquí se corresponde con el valor "keyNumber" de cada subnodo, es posible que no desee la variable keys en absoluto.)