Come può essere rappresentato un nodo B-tree?

Question

Stiamo imparando gli alberi B in classe e ci è stato chiesto di implementarli in codice. L'insegnante ha lasciato a noi la scelta del linguaggio di programmazione e voglio provare a farlo in C#. Il mio problema è che la seguente struttura è illegale in 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 
     } 

In particolare, non è consentito di creare un puntatore per puntare alla struttura stessa. C'è qualche approccio alternativo o alternativo che potrei usare? Sono abbastanza sicuro che ci debba essere un modo per farlo all'interno del codice gestito, ma non riesco a capirlo.

MODIFICA: La risposta di Eric mi ha indirizzato nella giusta direzione. Ecco cosa ho finito 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

Per coincidenza, in realtà ho appena implementato un btree in C#, per un progetto personale. È stato divertente. Ho creato un insieme di chiavi di dimensioni variabili (fino a 64 byte) con ordine lessicografico che hanno presentato una serie di difficoltà, in particolare per capire quando una pagina di archiviazione era troppo piena o troppo vuota.

Il mio consiglio, avendo appena finito, è di costruire un livello di astrazione che cattura solo gli algoritmi btree nella loro forma più astratta, come una classe base astratta. Una volta ottenute tutte le regole btree catturate in quella forma, ho specializzato la classe base in molti modi diversi: come un normale 2-3-size a dimensione fissa, come una delle mie fantasiose chiavi a dimensione variabile, e così via .

Per iniziare, in nessun caso si dovrebbe fare questo con i puntatori. Il codice non sicuro è raramente necessario e mai facile. Solo i programmatori C# più avanzati dovrebbero spegnere il sistema di sicurezza; quando lo fai, ti stai assumendo la responsabilità per il tipo e la sicurezza della memoria del programma. Se non si è disposti a farlo, lasciare il sistema di sicurezza acceso.

In secondo luogo, non c'è motivo di rendere questa struttura. Le strutture vengono copiate in base al valore in C#; un nodo btree non è un valore .

In terzo luogo, non è necessario mantenere il numero di chiavi in ​​un nodo; l'array di chiavi sa quante chiavi ci sono dentro.

In quarto luogo, vorrei usare un List<T> piuttosto che un array; sono più flessibili.

Quinto, è necessario decidere se la vita chiave del nodo o nella genitore. Ad ogni modo può funzionare; la mia preferenza è che la chiave viva nel nodo, perché vedo la chiave associata al nodo.

In sesto luogo, è utile sapere se un nodo btree è o meno root; potresti considerare di avere due bool, uno "è questa una foglia?" e uno "è questa la radice?" Ovviamente un btree con un singolo oggetto contiene un singolo nodo che è sia foglia che radice.

Settimo, probabilmente costruirai questa cosa per essere mutabile; normalmente non si rendono pubblici i campi mutabili su una classe C#. Potresti considerare di renderle proprietà. Inoltre, la lista dei figli può essere coltivato e ristretto, ma la sua identità non cambia, in modo da renderlo referenzialmente sola lettura:

Così ho probabilmente strutturare il mio nodo di base come:

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; } } 
} 

Ha senso?

Answer 2

Utilizzare una classe invece di una stuttura. E buttare via i puntatori.

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 
} 

Quando si dichiara una variabile di un tipo di classe, è implicitamente un riferimento (molto simile a un puntatore in C) dal momento che ogni classe è un tipo di riferimento.

Answer 3

Tutto ciò che serve per rendersi conto che un puntatore in C è "un po 'simile" a un riferimento in C#. (Ci sono varie differenze, ma ai fini di questa domanda ci si può concentrare sulle somiglianze.) Entrambe consentono un livello di riferimento indiretto: il valore non è il dato stesso, è un modo per accedere ai dati.

L'equivalente di quanto sopra sarebbe qualcosa di simile:

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

    // Members (constructors etc) 
} 

(non ricordo molto di B-alberi, ma se la matrice "chiavi" qui corrisponde al valore "chiave di accesso" di ogni subNode, potresti non volere la variabile keys.)