How can a B-tree node be represented?

Asked 2012-02-03T17:37:33.677

We're learning B-trees in class and have been asked to implement them in code. The teacher has left choice of programming language to us and I want to try and do it in C#. My problem is that the following structure is illegal 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
        }

Specifically, one is not allowed to create a pointer to point to the structure itself. Is there some work-around or alternate approach I could use? I'm fairly certain that there MUST be a way to do this within the managed code, but I can't figure it out.

EDIT: Eric's answer pointed me in the right direction. Here's what I ended up using,

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

c# .net b-tree

Edit Report

2 Answers

Use a class instead of a stuct. And throw out the pointers.

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
}

When you declare a variable of a class type, it is implicitly a reference(very similar to a pointer in c) since every class is a reference type.

answered 2012-02-03T17:39:36.217

All you need to realize that a pointer in C is "somewhat similar" to a reference in C#. (There are various differences, but for the purposes of this question you can concentrate on the similarities.) Both allow a level of indirection: the value isn't the data itself, it's a way of getting to the data.

The equivalent of the above would be something like:

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

    // Members (constructors etc)
}

(I don't remember much about B-trees, but if the "keys" array here corresponds to the "keyNumber" value of each subNode, you may not want the keys variable at all.)

answered 2012-02-03T17:40:38.293

How can a B-tree node be represented?

2 Answers

Your Answer