如何B-树节点进行重新presented？ [英] How can a B-tree node be represented?

问题描述

我们正在学习B树类，并已要求执行这些code。老师留下选择的编程语言，给我们，我想尝试做它在C＃。我的问题是，以下结构是非法在C＃，

 不安全结构BtreeNode
        {
            INT KEY_NUM; //键中的一个节点的数目
            INT []键; //按键阵列
            布尔叶; //它是一个叶子结点或没有？
            BtreeNode * []℃; //指针到下一个节点
        }
 

具体而言，一种是不允许创建一个指针指向该结构本身。有一些解决方法或另一种方法，我可以用？我相当肯定，必须有办法中的管理code做到这一点，但我不能弄明白。

编辑： Eric的回答我指出了正确的方向。这里是我结束了使用，

 类BtreeNode
{
        公开名单＆LT; BtreeNode＆GT;儿童; //子节点
        公共静态INT MinDeg; //度最小的树
        公共BOOL传递isLeaf {获得;组; } //是对当前节点叶或不？
        公开名单＆LT; INT＆GT;键; //键列表
...
}
 

解决方案

无独有偶其实我只是没有落实在C＃B树，对于一个个人项目。好玩。我建了一个B树字典顺序有序变量的大小（最多64个字节）按键，presented一些挑战，特别是围绕搞清楚当存储的页面太满或过空。

我的建议，刚刚做到这一点，是要建立一个抽象层，刚捕获的B树算法的最抽象的形式，作为一个抽象基类。一旦我得到了所有的这种形式捕获的B树的规则，我专门在几个不同的方式的基类：作为常规固定密钥大小2-3 B树，因为我的一个花哨的可变尺寸键B树，等

首先，在任何情况下，你应该用指针来这样做。不安全code是很少必要的，绝非易事。只有最先进的C＃程序员应该关闭安全系统;当你这样做，您正在为程序的类型和存储安全责任。如果你不愿意这样做，离开安全系统开启。

二，没有任何理由使这个结构。结构是由C＃值复制; B树节点不是的值的。

三，则不需要保持一个节点关键字的数目;键的阵列知道多少键是在它

四，我会用名单，其中，T＆GT; ，而不是一个数组;他们更灵活。

五，你需要决定是否在关键的生命在节点的或在父的。无论哪种方式能正常工作;我的preference是住在该节点的关键，因为我看到的主要为与节点相关联。

第六，是有帮助的知道B树节点是否是根与否;你可能会考虑有两个布尔变量，一是这是叶？和一个这是根？当然，在一个单一的项目B树有一个节点，既叶和根。

第七，你可能要建立这个东西是可变的;通常一个不做出一个C＃类的公共可变域。你可能会考虑让他们的属性。此外，孩子们的名单可以的长大和缩水的，但它的的身份的没有改变，所以使它指称只读：

所以，我可能会构造我的基本节点：

 类节点
{
    公众诠释键{获得;组; }
    公共BOOL IsRoot {获得;组; }
    公共BOOL传递isLeaf {获得;组; }
    私人列表＆LT;节点＆GT;孩子=新的名单，其中，节点＆GT;（）;
    公开名单＆LT;节点＆GT;儿童{{返回this.children; }}
}
 

有意义吗？

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

解决方案

Coincidentally I actually just did implement a btree in C#, for a personal project. It was fun. I built a btree of lexicographically ordered variable size (up to 64 byte) keys which presented a number of challenges, particularly around figuring out when a page of storage was too full or too empty.

My advice, having just done that, is to build an abstraction layer that captures just the btree algorithms in their most abstract form, as an abstract base class. Once I got all the btree rules captured in that form, I specialized the base class in several different ways: as a regular fixed-key-size 2-3 btree, as one of my fancy variable-size-key btrees, and so on.

To start with, under no circumstances should you be doing this with pointers. Unsafe code is seldom necessary and never easy. Only the most advanced C# programmers should be turning off the safety system; when you do that, you are taking responsibility for the type and memory safety of the program. If you're not willing to do that, leave the safety system turned on.

Second, there's no reason to make this a struct. Structs are copied by value in C#; a btree node is not a value.

Third, you don't need to keep the number of keys in a node; the array of keys knows how many keys are in it.

Fourth, I would use a List<T> rather than an array; they are more flexible.

Fifth, you need to decide whether the key lives in the node or in the parent. Either way can work; my preference is for the key to live in the node, because I see the key as being associated with the node.

Sixth, it is helpful to know whether a btree node is the root or not; you might consider having two bools, one "is this a leaf?" and one "is this the root?" Of course a btree with a single item in it has a single node that is both leaf and root.

Seventh, you are probably going to build this thing to be mutable; normally one does not make public mutable fields on a C# class. You might consider making them properties. Also, the list of children can be grown and shrunk, but its identity does not change, so make it referentially read-only:

So I would probably structure my basic node as:

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

Make sense?

这篇关于如何B-树节点进行重新presented？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！