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

Мы изучаем B-деревья в классе и попросили их реализовать в коде. Учитель оставил нам выбор языка программирования, и я хочу попробовать и сделать это на С#. Моя проблема в том, что следующая структура является незаконной в С#,

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

Ответы

Ответ 1

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

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

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

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

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

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

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

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

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

Итак, я бы, вероятно, структурировал свой базовый node как:

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

Имеют смысл?

Ответ 2

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

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), поскольку каждый класс является ссылочным типом.

Ответ 3

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

Эквивалент выше будет примерно таким:

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

    // Members (constructors etc)
}

(Я мало помню о B-деревьях, но если массив "keys" здесь соответствует значению "keyNumber" для каждого поднабора, вам может вообще не понадобиться переменная keys.)