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

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

11 голосов
/ 03 февраля 2012

Мы изучаем 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 
...
}

Ответы [ 3 ]

27 голосов
/ 03 февраля 2012

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

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

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

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

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

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

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

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

В-седьмых, вы, вероятно, сделаете эту вещь изменчивой; обычно никто не делает общедоступными изменяемые поля в классе 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; } }
}

Имеет смысл?

14 голосов
/ 03 февраля 2012

Используйте класс вместо учебного. И выкинь указатели. 

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

8 голосов
/ 03 февраля 2012

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

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

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

    // Members (constructors etc)
}

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

...