C＃generic B + tree

Question

私はC＃を使用してB +ツリーを実装しています。

私は理解しているように、ツリーノードは、レコードまたは他のノードへのポインタの順序番号、つまりリーフノードだけがレコードへの実際のポインタを保持するという、多数の（order - 1）キーを保持する必要があります。内部ノードは他のノードへのポインタを保持します。今私は、このような

などの値の配列にノードを配置しようとすると

class Node< K,V > 
{ 
    K [] keys ; 
    V [] values; 
} 

：

私はこの実装で持ってる問題は、Nodeクラスとして宣言されている

C＃のジェネリックであります

_root.Values[0] = left ; // left being of type Node<K,V> 

私は次のエラーを取得する：

Cannot implicitly convert type 'BTree_Library.Node' to 'V'

これを回避する方法を見つけようとしています。もう1つの方法は、ノードとレコード用に1つの配列を保持するように実装を変更することです。

ので、結論に：Cで

1. 私が使用しているだろう：私はC＃でその相当を探してい(void* values;) 。

2. 私は主題について話していますが、ノードのポインタとノードのレコードを入れ替え可能であることに関して、B +ツリーの構造は正しく と理解していますか？仮定_root.Values[0] = left

Answer 1

リーフノードと内部ノードが異なるように動作し、それらのノードを両方ともノードとして参照できるようにします。

abstract class Node<K, V> 
{ 
    public K[] Keys { get; protected set; } 
} 

class LeafNode<K, V> : Node<K, V> 
{ 
    public V[] Values { get; protected set; } 
} 

class InnerNode<K, V> : Node<K, V> 
{ 
    public Node<K, V> Children { get; protected set; } 
} 

別のオプションがobjectあるvoid*のC＃の同等のものを使用することであろうが、それはタイプセーフをされていないもうコードを意味するであろうと、あなたはどこでもキャストを持っている必要があります：それは、継承階層を示します。私はこれを行うことをお勧めしません。

それでは、なぜ自分のBツリーを作成しているのですか？これは、データをディスクではなくメモリに保存する場合にのみ有効です。連想配列しか持たないのであれば、すでに.NETを実装しているクラス（Dictionary<K,V>またはSortedDictionary<K,V>など）があり、それは完全にうまく動作します。

Answer 2

はクラス内から実行され、そのValuesはvaluesと同等の特性です。

Vは常にNodeの型になります場合は、これは、その行がエラーなしでコンパイルすることができますどの、BTree_Library.Nodeから派生するVを強制します

interface INode { 
} 

class Node<K, V> : INode where V : INode { 

} 

ような何かを試すことができます。

Vが常にNodeから派生するとは限りませんが、ジェネリックスがこれに取り組むには間違った方法かもしれないと思います。