Как можно представить узел B-дерева?

Question

Мы изучаем B-деревья в классе и попросили их реализовать в коде. Учитель оставил нам выбор языка программирования, и я хочу попробовать и сделать это на C#. Моя проблема заключается в том, что следующая структура является незаконным в 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 
     } 

В частности, один не может создать указатель, чтобы указать на саму структуру. Есть ли какой-нибудь подход или альтернативный подход, который я мог бы использовать? Я абсолютно уверен, что ДОЛЖЕН быть способ сделать это в управляемом коде, но я не могу понять это.

EDIT: Ответ Эрика указал мне в правильном направлении. Вот что я в итоге использовал,

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

Кстати, на самом деле я действительно реализовал btree в C# для личного проекта. Это было весело. Я построил btree из лексикографически упорядоченного ключа с переменным размером (до 64 байт), который представлял ряд проблем, особенно в том, что касается выяснения, когда страница хранилища слишком заполнена или слишком пуста.

Мой совет, только что сделал это, состоит в том, чтобы построить слой абстракции, который захватывает только алгоритмы btree в их самой абстрактной форме, как абстрактный базовый класс. После того, как я получил все правила btree, записанные в этой форме, я специализировал базовый класс несколькими различными способами: как обычный 2-3-битный размер с фиксированным ключом, как один из моих причудливых btrees с переменным размером и т. Д. ,

Для начала, ни при каких обстоятельствах не следует делать это с помощью указателей. Небезопасный код редко необходим и никогда не бывает легким. Только самые продвинутые программисты на C# должны отключать систему безопасности; когда вы это делаете, вы берете на себя ответственность за тип и безопасность памяти программы. Если вы не хотите этого делать, оставьте систему безопасности включенной.

Во-вторых, нет причин для создания этой структуры. Структуры копируются по значению в C#; узел btree не является значением .

В-третьих, вам не нужно хранить количество ключей в узле; массив ключей знает, сколько ключей в нем.

В-четвертых, я бы использовал List<T>, а не массив; они более гибкие.

В-пятых, вы должны решить, являются ли ключевые жизни в узле или в родителя. В любом случае это может работать; я предпочитаю, чтобы ключ находился в узле, потому что я вижу ключ как связанный с узлом.

В-шестых, полезно знать, является ли узел btree корнем или нет; вы можете подумать, что у вас есть два дурака, один - это лист? и один «это корень?» Конечно, btree с одним элементом в нем имеет единственный узел, который является как листом, так и корнем.

В-седьмых, вы, вероятно, собираетесь построить эту вещь для изменения; обычно один класс не делает общедоступными изменяемые поля в классе C#. Вы можете подумать о том, чтобы сделать их свойствами. Кроме того, список детей можно выращены и сократилась, но его идентичность не меняется, так что это референциально только для чтения:

Так что я, вероятно, структурировать мой основной узел, как:

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

Имеют смысл?

Answer 2

Используйте класс вместо столбца. И выбросьте указатели.

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 
} 

При объявлении переменной типа класса, то неявно ссылка (очень похож на указатель в C), так как каждый класс является ссылочным типом.

Answer 3

Все, что вам нужно, чтобы понять, что указатель в C «несколько похож» на ссылку в C#. (Существуют разные различия, но для целей этого вопроса вы можете сосредоточиться на сходствах.) Оба позволяют уровень косвенности: значение не является самими данными, это способ получить данные.

Эквивалент выше было бы что-то вроде:

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

    // Members (constructors etc) 
} 

(я не помню много о B-деревьев, но если «ключи» массив здесь соответствует значению «keyNumber» каждого subNode, вы можете не хотеть переменную keys.)